使用 if case 理解 Python 中的递归

Question

在解决这个问题时 codewars challenge 我遇到了一个我不理解的递归示例。

挑战是给出接下来的第 n 个数字，给定一个初始的 3 个数字种子序列，其中第 n 个数字是通过添加序列的最后三个数字来确定的。

所以对于 [1,2,3] 的种子序列列表和给定的 n=5，你会 return 以下内容：

1 + 2 + 3 = 6
2 + 3 + 6 = 11

答案：
[1, 2, 3, 6, 11]

我用以下方法解决了这个问题：

def tribonacci(sequence,n):
if n <=3:
    return sequence[:n]
else:
    for i in range(n-3):
        sequence.append(sum(signature[-3:]))        
    return sequence

在查看其他解决方案时，我遇到了这个使用递归的非常优雅的解决方案：

def tribonacci(sequence,n):
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n)

我的问题是：为什么这不是无限地运行？我无法理解为什么这会在第 n 次迭代时终止。 'n' 的功能似乎没有在任何地方规定，除了 if 情况。

作为实验，我修改了代码以忽略小于或等于序列长度的情况，如下所示：

def tribonacci(sequence,n):
    return tribonacci(sequence + [sum(sequence[-3:])],n)

这会无限地运行并出现运行最大递归深度的时间错误。

显然 case 选项似乎控制了终止，但我不明白为什么。我自己在求解中使用了递归（例如在创建因式分解函数时），但在该示例中，您在迭代时减去 n-1，因此有一个终止过程。我在这里看不到这种情况。

我想我不完全理解 return 函数的工作原理。我读它是：

return n-item list if n is less/equal to sequence length

else

rerun the function

也许我应该把它读成：

return n-item list if n is less/equal to sequence length

else

return n-item list after iterating through the function enough times to fill a n-item list

Answer 1

在递归的每一级，序列由于连接而变长 (+)。最终它会变得足够长 n 变得小于长度。

Answer 2

你可以改写这个：

a = b if p else c

像这样：

if p:
    a = b
else:
    a = c

知道了，你可以看到这个：

def tribonacci(sequence,n):
    return sequence[:n] if n<=len(sequence) else tribonacci(sequence + [sum(sequence[-3:])],n)

等同于：

def tribonacci(sequence,n):
    if n <= len(sequence):
        return sequence[:n]
    else:
        return tribonacci(sequence + [sum(sequence[-3:])],n)

现在你应该能看到有一个条件控制递归不会一直进行下去。

使用 if case 理解 Python 中的递归

Understanding recursion in Python with if case

python

recursion

return

fibonacci

python-2.7