试图理解为什么我的函数达到最大递归或无?

Question

这个问题已经被问了很多次了，但是在看了这些帖子和回答之后，我不明白为什么我的代码仍然不能工作

所有关于递归的帖子都说你需要包含一个返回语句来实际返回值，而不是None。但是当我这样做的时候，我得到了一个无限递归。我有了基本情况，以及collatz序列的另外两种情况。我想让它打印出这些数字，但这是一个无限递归。

#Maximum recursion
def find_collatz_nums(number):
if number == 1:
return find_collatz_nums(number)
if number % 2 == 0:
return find_collatz_nums(number/2)
return find_collatz_nums((3 * number) + 1)
print(find_collatz_nums(3))

那么如果我尝试在基准情况下做一个空白返回它会返回None。

#returns None
def find_collatz_nums(number):
if number == 1:
return  #will just return None. 
if number % 2 == 0:
return find_collatz_nums(number/2)
return find_collatz_nums((3 * number) + 1)
print(find_collatz_nums(3))

为什么在第一个代码片段中，return语句会导致无限递归?

我只是发现自己很困惑，因为这里有大量关于递归的帖子和答案说"你需要返回语句"，但我已经添加了它们，代码不起作用。

Answer 1

如果你遵循你的程序逻辑，这是函数调用的顺序:

find_collatz_nums (3) -> 
find_collatz_nums (10) -> 
find_collatz_nums (5) ->
find_collatz_nums (16) -> 
find_collatz_nums (8) -> 
find_collatz_nums (4) -> 
find_collatz_nums (2) -> 
find_collatz_nums (1) -> find_collatz_nums (1) -> find_collatz_nums (1).... &  so on

所以你看python没有办法停止这个调用&它被一次又一次地调用。这就是为什么你需要一个基本条件从它返回。

我猜你想打印出序列，你可以在每个return之前print

def find_collatz_nums(number):
if number == 1:
print(int(number))
return  
if number % 2 == 0:
print(int(number), end="->")
return find_collatz_nums(number/2)
print(int(number), end="->")
return find_collatz_nums((3 * number) + 1)
find_collatz_nums(3)
# 3->10->5->16->8->4->2->1

Answer 2

第一个代码片段导致无限循环，因为没有条件来转义递归，即显式打印或返回任何内容。

Answer 3

所有的分支都是递归的-即它们都再次调用函数。你实际上没有一个基本情况。基本情况是指你可以直接计算或返回一个值，而不是递归地计算一个值。

考虑另一个可以用递归解决的问题:找到列表中数字的和:

基本情况是当你有一个空列表，因为没有值，和只是0。

考虑递归的情况，你可以将列表切片:第一项是一个数字，列表的其余部分只是另一个列表。这种情况下的和是第一个元素加上列表其余元素的和:

>>> def find_sum(values):
...     if len(values) == 0:
...             return 0
...     else:
...             return values[0] + find_sum(values[1:])
... 
>>> find_sum([1, 2, 3])
6
>>>

我不知道Collatz序列是什么，所以我将留给其他人来评论递归应该如何寻找它。