我遇到了一个内部有递归函数调用的循环,其中循环的起始范围按如下方式递增。该代码输出以下序列。但是,我无法概念化为什么会生成这个特定序列。有人可以对其工作原理有一些见解吗?以及将这个递归函数转换为输出相同序列的迭代函数有多可行。请帮忙。
代码:
def foo(step=0):
for i in range(step, 4):
print step
foo(step+1)
foo()
输出:
0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3 0 1 2 3 2 3 1 2 3 2 3 1 2 3 2 3
类似设计的代码来查找 Anagrams:
def find_anagrams(word, step=0):
print 'step->', step
if step == len(word):
print "".join(word)
for i in range(step, len(word)):
print step, i
word_ = list(word)
word_[step], word_[i] = word_[i], word_[step]
find_anagrams(word_, step+1)
最佳答案
让我试试:
从您的代码片段中,在每个函数调用中,即 foo(step+1) ,都有一个称为激活记录的结构或 创建框架是为了存储有关函数调用进度的信息。 因此,当函数的执行导致嵌套函数调用时,前一个调用的执行 被挂起,它的激活记录存储了源代码中控制流的位置 嵌套调用返回后应继续。
主要部分如下:
当step == 4,即range(4,4) ==空列表时,该时间迭代不会发生,因此它将返回 没有任何。然后它将移动到之前停止的帧并开始新的迭代和递归函数调用 直到范围(4,4)。
注意:递归基本情况仅当步骤 == 4 时,即时间范围(4,4)并返回 None 。
每个递归都需要一个基本情况,否则它将进入无限循环。
那么,让我们看看递归跟踪:我添加了 i
来区分 step
和迭代增量。
# 1 def foo(step=0):
# 2 for i in range(step, 4):
# 3 print 'i: %d, step: %d' % (i,step)
# 4 foo(step+1)
# 5 foo()
line 5
line 1 foo with step=0 which is default
line 2 range(0,4) Frame: A, 0 is over, next=1
line 3 step = 0 Output: i: 0, step: 0
line 4 calling foo(0 + 1)
line 1 foo with step=1
line 2 range(1,4) Frame: B, 1 is over, next=2
line 3 step = 1 Output: i: 1, step: 1
line 4 calling foo(1 + 1)
line 1 foo with step=2
line 2 range(2,4) Frame: C, 2 is over, next=3
line 3 step = 2 Output: i: 2, step: 2
line 4 calling foo(2 + 1)
line 1 foo with step=3
line 2 range(3,4) Frame: D, 3 is over, next=4
line 3 step = 3, Output: i: 3, step: 3
line 4 calling foo(3 + 1)
line 1 foo with step=4
line 2 range(4,4) Frame: E,
This is an empty list, so it won't come inside the loop, so return None.
Come back to previous Frame: D, i=3 was used, now increment to 4. So, again range(4,4)
line 2 range(4,4) Empty list, from Frame: D, return None
Come back to previous Frame C, now i=3, step was called with value 2
line 2 range(2,4)
line 3 step = 2 Output: i: 3, step: 2, why step == 2 because the function foo was called with step=2
line 4 calling foo(2 + 1)
line 1 foo with step=3
line 2 range(3,4)
line 3 step = 3, Output : i: 3, step: 3
line 4 calling foo(3 + 1)
line 1 foo with step=4
line 2 range(4,4) Empty list again, not going inside the list, return None
line 2 range(2,4) From Frame: B, step was == 1, because the function foo was called with step=1
line 3 step: 1 Output: i: 2, step: 1, here i ==2, because this is the second iteration of Frame B.
line 4 calling foo(1 + 1)
line 1 foo with step=2
line 2 range(2,4)
line 3 step: 2 Output: i: 2, step: 2
此后,它遵循相同的递归方式,直到迭代范围耗尽,即 range(4,4)
如果有帮助,请告诉我。
关于Python 循环内的递归调用。它是如何工作的?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21807174/