这种递归组合生成算法(Python3)有问题吗

Question

尝试在列表"looper"中生成所有可能的值组合，以达到用户指定的最大字符长度。为了做到这一点，我尝试了一种递归算法，并产生了以下结果：

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)

出于某种原因，无论何时运行，它都会返回值None。

我无法用我的代码识别问题，如果有人能，我将不胜感激。

Answer 1

您一直忽视声音建议——这都是关于递归调用的返回值。你不能在一个递归框架中更改变量，并假设它们会在其他框架中更改。如果我正确理解了潜在的问题，你会让它变得更加困难：

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))

让递归完成工作。

输出

% 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']
%

Answer 2

您完全忽略了递归调用的返回。

以下面的斐波那契为例：

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

此外，如果存在从未到达返回语句的条件，则函数将返回None。在上面的例子中，如果我们删除最后一个返回，那么对于所有大于1的值，函数将返回None。

简要介绍

>>> fib(1)
1

由于CCD_ 5小于或等于CCD_。函数获取第一个返回。

>>> fib(2)
1

2大于1，所以我们必须采用第二条路径。得到1的fib(2 - 1(和0的fib(2 - 2(。

由于这两个调用都是递归的，我们需要重复两次这个rundown，一次用于1，另一次用于0。(这样做，这就是递归(

完成后，返回并添加结果。第一个结果是1，第二个是0。CCD_ 19返回CCD_。