我不理解递归的使用方法

Question

我在阅读有关"反转"徽章的答案时，发现有一个关于递归的问题，其中OP没有在前期做好大部分作业。除了一些非常有趣的答案外，@machielo发布了一个使用Python编写的答案，我不得不在我的计算机上运行它才能理解。但我仍然没有理解它。

def recursive(x):
    if x > 10:
        print recursive(x/10)
    return x%10

>>> recursive(2678)
2
6
7
8

我尝试了第一个猜测，但我知道它是错误的。

>>> 2678/10
267
>>> 267/10
26
>>> 26/10
2
>>> 2%10
2

好的...这就是两个数了。那么这如何评估x中其他数字的输出？

编辑

我不理解这里的print语句。我将代码修改为：

>>> def recursive(x):
if x > 10:
    print x
    print recursive(x/10)
return x%10

>>> #I will comment the interpreter session here...
>>> recursive(2345)
2345 # first feed in...print the raw number `x`
234  # 2345/10 does equal 234...the 5 is being held back somewhere...
23   # and each pass through the recursive loop removes the last digit...
2    # but where was it being stored at, so that each evaluation of
3    # x > 10 finally started returning False
4    # and returns the number, exiting the function
5    # ...

我认为在每次运行时，对print recursive(x/10)的调用都会创建一个新的函数对象，每个对象都有自己全新的基本情况和输入......

还有其他提示吗？

最后

感谢大家。我现在觉得已经理解了...诀窍并不是print，而是x%10。2345%10 == 5...

>>> def recursive(x):
print "Raw `x`:", x
if x > 10:
    print "Recurse `x`:", x
    print recursive(x/10)
print "Last `x`:", x    
return x%10

>>> recursive(2345)
Raw `x`: 2345
Recurse `x`: 2345
Raw `x`: 234
Recurse `x`: 234
Raw `x`: 23
Recurse `x`: 23
Raw `x`: 2
Last `x`: 2
2
Last `x`: 23
3
Last `x`: 234
4
Last `x`: 2345
5

此外，要感谢那些更新了我之前链接的初始答案的人...我即将给你的评论点赞：

>>> def recursive(x):
if x >= 10:
    print recursive(x/10)    
return x%10

- yurisich

---

我认为我没有完全理解这个问题。你所说的“x中的每个数字”是什么意思？ - Ricardo Cárdenes

@joaquin，你能描述一下你的输出吗？Python 2.7.1。 - yurisich

输出是2、6、7。我需要调用“print recursive(2678)”才能获得帖子中给出的输出（2、6、7、8）。好的，我明白了：你在Python控制台中，而我在IDE中。 - joaquin

我在思考，在每次运行中，对print recursive(x/10)的调用会创建一个新的函数对象，每个对象都有自己全新的基本情况和输入...是的，这就是递归的精髓。这个特定的递归函数让人困惑的部分之一是它调用了递归函数，然后在之后做了更多的事情（而不是if-else！）。这意味着如果你不能立即看出它的作用，你真的必须拿出笔和纸来。 - Free Monica Cellio

@ChadMiller 我在下面评论了你的答案。我真的觉得它帮助我更好地理解了正在发生的事情。谢谢。 - yurisich

Answer 1

我认为添加一些print语句非常有帮助:

def recursive(x):
  print '[start] recursive({0})'.format(x)
  if x > 10:
    print recursive(x/10)
  print '[return] recursive({0}) = {1}'.format(x, x%10)
  return x%10

print recursive(2678)

输出结果为：

[start] recursive(2678)
[start] recursive(267)
[start] recursive(26)
[start] recursive(2)
[return] recursive(2) = 2
2
[return] recursive(26) = 6
6
[return] recursive(267) = 7
7
[return] recursive(2678) = 8
8

- jcollado

---

我复制了你的格式并稍微调整了一下，这样我就可以强迫自己从记忆中构建它。很好的例子！ - yurisich

@Droogans 谢谢。如果你想要得到更详细的输出，你也可以使用 traceback.print_stack。这将打印整个堆栈，特别是所有对 recursive 的调用都会一层叠一层地打印出来。 - jcollado

Answer 2

以下是伪代码示例的步骤（破折号数量表示递归深度）：

-call recursive(2678)
--2678 > 10, call recursive(267)
---267 > 10, call recursive(26)
----26 > 10, call recursive(2)
-----return 2%10 (which is 2)
----print 2, then return 26 % 10 (which is 6)
---print 6, then return 267 % 10 (which is 7)
--print 7, then return 2678 % 10 (which is 8)
-return 8

- Free Monica Cellio

---

那么你的意思是print语句在递归循环中直到很晚才被评估，即使在那时...它实际上也没有显示结果？这就是你所说的“打印2，然后返回26％10”的意思吗？你把最后一行写成了return 8，这就是我为什么这样想的原因。 - yurisich

@Droogans 我认为是正确的。控制台打印了最后8个字符。 - joaquin

并不是因为它没有被评估。打印语句无法解析，因为它不断地递归调用方法。在底部返回值之前，这些值无法解析，因此递归可以看作是答案冒泡上来的过程。 - Jordan

@Droogans：内部函数调用的情况是，它们被调用时带有print recursive(x/10)。当recursive(x/10)求值时，它会返回一个值，但默认情况下不会打印它...但由于它在print语句中被调用，所以一旦它返回，函数就会打印结果。如果只是说recursive(x/10)而没有print，它将不会打印任何内容。 - Free Monica Cellio

Answer 3

这个函数可以打印出一个数字的各个位数。

它的工作原理如下：

def recursive(x):
  if x > 10:
    # Divide x by 10 and round down. This chops off the last decimal place.
    # Now feed that new x without the last decimal place back into recursive()

  # return x's last digit

基本上，只有当x成为一位数字时才会打印任何内容。

你可能感到困惑的部分是它为什么按照那个顺序打印出每个小数位。这是因为在函数递归时，父函数仍在运行。

尝试将代码扩展到单个数字。

编辑：我也感到困惑。

您的代码在返回之前调用print，这意味着当最后一个递归级别完成时，倒数第二个递归级别打印出第一个数字。下一层也是如此。

- Blender

---

好的@Blender，我会写出我可怕的尝试模拟栈图。 - yurisich

Answer 4

在考虑递归时，请记住调用堆栈。递归调用会将所有recursive()函数调用推入堆栈，然后才会打印任何内容，因此您在堆栈上得到的结果是：

recursive(2) # end condition is met so returns 2%10
recursive(26)
recursive(267)
recursive(2678) # the initial call

一旦达到结束条件，2%10（2）将返回到上一个函数的打印语句并打印，然后该函数返回26%10（6），这样继续进行，直到堆栈上的所有递归函数调用都返回。结果是这一系列的打印调用：

print 2 
print 6
print 7
8

8 实际上并没有被打印出来；它只是从解释器中返回，这是可以的。如果你想确保它在例如 Python 脚本中被打印出来，你可以调用 print recursive(2678)

- philofinfinitejest