我理解递归到某个级别的概念,但我无法理解递归调用中发生的所有步骤.
例如:
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 ...并计算何时达到基础,我发现有点难以想象整个过程.
另一个例子是说我传递一个iterable.
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如何明确地管理递归吗？
但是,Python会自动对金额求和并在所有情况下执行此操作吗？
Python在这里不需要做任何特别的事情.递归函数调用只是函数调用.函数调用没有什么神奇之处.
所有这一切发生的是,返回值一个函数调用的乘法使用:
n * fact(n-1)
Python执行fact(n-1)函数调用,函数返回,Python通过乘以n返回值来完成表达式.
将此与您可以调用的任何其他功能进行比较.会n * math.sin(n-1)更容易遵循？你不必知道里面是什么math.sin(),只是它返回一个值,然后在乘法中使用.
该fact()函数调用与此处完全相同的函数实际上并不重要.Python并不关心.Python 特别不关心,因为Python是如此动态.从一个时刻到另一个时刻,名称fact可以绑定到不同的名称,因此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
这里的缩进表明函数是堆栈上的每个单独的命名空间.当一个函数调用另一个函数时,当前函数被"暂停",暂停,它包含的数据放在堆栈顶部,直到它可以恢复.多个函数调用因此全部堆积起来,直到某些东西最终开始将结果返回给调用者,此时前一个函数可以从它们停止的地方恢复,等等.