我在一定程度上理解递归的概念，但我无法理解递归调用中发生的所有步骤。
例如:
def fact(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact({}) = {} * fact({})'.format(n,n,n,n-1))
return n * fact(n-1)
answer = int (input('Enter some number: '))
print(fact(answer))
>> Enter some number: 5
5 is not 0, so fact(5) = 5 * fact(4)
4 is not 0, so fact(4) = 4 * fact(3)
3 is not 0, so fact(3) = 3 * fact(2)
2 is not 0, so fact(2) = 2 * fact(1)
1 is not 0, so fact(1) = 1 * fact(0)
120
虽然我理解它重复任务直到它到达 n == 0 的基数，但是 Python 如何存储前面的 5 * 4 * 3 ... 并在达到 based 时进行计算，我发现很难形象化整个过程。
另一个例子是当我传递一个可迭代对象时。
def getSum(piece):
if len(piece) == 0:
return 0
else:
print(piece)
return piece[0] + getSum(piece[1:])
print(getSum([1, 3, 4, 2, 5]))
>>
[1, 3, 4, 2, 5]
[3, 4, 2, 5]
[4, 2, 5]
[2, 5]
[5]
15
列表似乎从每次递归减少到 piece[n-1:] 并且最终返回的所有值再次相加。关于 Python 如何显式管理递归，有什么地方可以引用吗？
请您参考如下方法:
but then does Python automatically sum the amounts and does this for all cases?
Python 在这里不需要做任何特殊的事情。递归函数调用只是函数调用。函数调用没有什么神奇之处。
所有发生的事情是 函数调用的返回值用于乘法:
n * fact(n-1)
Python 执行了 fact(n-1)函数调用，函数返回，Python通过乘以n完成表达式返回值。
将此与您可以调用的任何其他函数进行比较。会 n * math.sin(n-1)更容易理解？您不必知道 math.sin() 的里面是什么，只是它返回一个值，然后用于乘法。
那个那个fact()函数调用与这里的函数完全相同实际上并不重要。 Python 不在乎。 Python 特别不关心，因为 Python 是如此动态。从一个时刻到下一个时刻，名字fact可以绑定(bind)到不同的东西，所以 Python 只是查找 fact在名称表中，并用 n-1 的结果调用它. fact这里没有特别考虑指向与当前正在执行的函数相同的函数。
为每个步骤创建单独的函数可能有助于理解:
def fact5(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact5({}) = {} * fact4({})'.format(n,n,n,n-1))
return n * fact4(n-1)
def fact4(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact4({}) = {} * fact3({})'.format(n,n,n,n-1))
return n * fact3(n-1)
def fact3(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact3({}) = {} * fact2({})'.format(n,n,n,n-1))
return n * fact2(n-1)
def fact2(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact2({}) = {} * fact1({})'.format(n,n,n,n-1))
return n * fact1(n-1)
def fact1(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact1({}) = {} * fact0({})'.format(n,n,n,n-1))
return n * fact0(n-1)
def fact0(n):
if n == 0:
return 1
else:
print('{} is not 0, so fact0({}) = {} * fact_minus1({})'.format(n,n,n,n-1))
return n * fact_minus1(n-1)
然后调用fact5(5)并得到
>>> fact5(5)
5 is not 0, so fact5(5) = 5 * fact4(4)
4 is not 0, so fact4(4) = 4 * fact3(3)
3 is not 0, so fact3(3) = 3 * fact2(2)
2 is not 0, so fact2(2) = 2 * fact1(1)
1 is not 0, so fact1(1) = 1 * fact0(0)
120
请注意，我没有费心定义 fact_minus1()函数，我们知道当您以 fact5(5) 开头时它不会被调用.
您还可以在可视化中添加更多信息。您不记录函数的返回值，您可以添加缩进以可视化您在调用结构中的深度:
def fact(n, _indent=''):
print(f"{_indent}-> fact({n}) called")
if n == 0:
print(f"{_indent}<- fact({n}) returns 1")
return 1
else:
print(f"{_indent} fact({n}) calls fact({n-1}) ->")
recursive_result = fact(n - 1, _indent+' ')
print(f"{_indent} fact({n}) <- received {recursive_result}, multiplying with {n}")
result = n * recursive_result
print(f"{_indent}<- fact({n}) returns {result}")
return result
产生:
-> fact(5) called
fact(5) calls fact(4) ->
-> fact(4) called
fact(4) calls fact(3) ->
-> fact(3) called
fact(3) calls fact(2) ->
-> fact(2) called
fact(2) calls fact(1) ->
-> fact(1) called
fact(1) calls fact(0) ->
-> fact(0) called
<- fact(0) returns 1
fact(1) <- received 1, multiplying with 1
<- fact(1) returns 1
fact(2) <- received 1, multiplying with 2
<- fact(2) returns 2
fact(3) <- received 2, multiplying with 3
<- fact(3) returns 6
fact(4) <- received 6, multiplying with 4
<- fact(4) returns 24
fact(5) <- received 24, multiplying with 5
<- fact(5) returns 120
120
这里的缩进显示函数是每个堆栈上的独立命名空间。当一个函数调用另一个函数时，当前函数被“暂停”，搁置，它包含的数据放在堆栈顶部，直到可以恢复。多个函数调用，所以所有这些都堆积起来，直到某些东西最终开始将结果返回给调用者，此时前一个函数可以从它们停止的地方恢复，等等。
