CODEWITHSUNDEEP
pythonrecursion
developer132i3278
developer132i3278

Reputation: 1

Is there an issue with this recursive combination generation algorithm (Python 3)?

Trying to generate all possible combinations of values within the list 'looper' to a user-specified maximum character length. To do this, I tried my hand at a recursive algorithm, and produced the below:

def generate_combinations(length, num_times, first_time):
    looper = ['1', '2', '3','4']
    if num_times == 0 and first_time:
        word_list = []
        word = ''
    elif num_times == 0:
        word = ''
    elif num_times == length and len(word_list) == 4 ** length:
        return word_list    
    else:
        for letter in looper:
            word += letter
            num_times +=1
            if num_times == length:
                word_list.append(word)
                generate_combinations(length, 0, False)
                
            else:
                generate_combinations(length, (num_times), False)

For some reason, it is returning a value of None whenever run.

I cannot identify the issue with my code, and, if anyone could, it would be much appreciated.

Upvotes: 0

Views: 27

Answers (2)

cdlane
cdlane

Reputation: 41903

You keep dismissing sound advice -- it's all about the return values of the recursive calls. You can't change variables in one recursive frame and assume they'll change in others. And if I understand the underlying problem correctly, you're making it harder than necessary:

def generate_combinations(length):
    looper = ['1', '2', '3', '4']

    if length == 1:
        return looper

    word_list = []

    if length == 0:
        return word_list

    for suffix in generate_combinations(length - 1):
        for letter in looper:
            word_list.append(letter + suffix)

    return word_list

print(generate_combinations(3))

Let the recursion do the work.

OUTPUT

% python3 test.py
['111', '211', '311', '411', '121', '221', '321', '421', '131', '231', '331', '431', '141', '241', '341', '441', '112', '212', '312', '412', '122', '222', '322', '422', '132', '232', '332', '432', '142', '242', '342', '442', '113', '213', '313', '413', '123', '223', '323', '423', '133', '233', '333', '433', '143', '243', '343', '443', '114', '214', '314', '414', '124', '224', '324', '424', '134', '234', '334', '434', '144', '244', '344', '444']
%

Upvotes: 1

Pedro Rodrigues
Pedro Rodrigues

Reputation: 2658

You are completly ignoring the return of the recursive calls.

Take the following fibonacci example:

def fib(n):
   if n <= 1:
       return n
   else:
       return fib(n-1) + fib(n-2)

Also if there is a condition that never reaches a return statement the function will return None. In the example above, if we remove the last return the function will return None for all values greater than 1.

A quick rundown

>>> fib(1)
1

Since 1 is less than or equal to 1. The function takes the first return.

>>> fib(2)
1

2 is greater that 1 so we must take the second path. Get fib of 1 (2 - 1) and, fib of 0 (2 - 2).

Since both calls are recursive, we need to repeat this rundown twice, one for 1 another for 0. (do that, thats the recursion)

When that is done, get back and add the results. The first result is 1, the second is 0. 1 + 0 = 1 return 1.

Upvotes: 0

Related Questions