递归函数背后的思维模式
我正在努力学习递归函数，但我似乎无法理解递归的概念。我看过关于递归的视频，也看过教程，但我想不出当我自己解决这些问题时所需要的递归。但是，我可以非常快地使用循环和迭代来解决这些问题。
例如，我看到了一个关于在一个数字中找到数字数的问题，答案是：
def digit(n):
if n < 10:
return 1
else:
return 1 + digit(n/10)我知道if是一个递归将停止的点，但即使在查看了答案之后，我也不明白else部分是如何工作的，也不知道为什么工作。
当使用递归函数时，我的思维过程应该是怎样的呢？
回答 5
Stack Overflow用户
发布于 2016-10-07 10:48:45
如果手头的问题也是递归的，递归是非常有用的。其中一个问题是遍历类似树的数据结构。正在编译的任何计算机程序都会产生这样一个结构，称为语法树。编译器遍历树并为它找到的分支生成代码。我知道这本身并不能帮助你理解递归，但它只是为了明确递归是一个非常实用的概念。只有给出的例子大多是人工的，因为“真实”的例子需要太多的先验知识。
至于你的例子，一些打印应该清楚地说明发生了什么：
def digit(n):
print ('Entering "digit" with n == {}'.format (n))
if n < 10:
print ('In the "if" now')
return 1
else:
print ('In the "else" now')
return 1 + digit(n/10)
print (digit (10000))修改后的代码使其更加清晰，请逐步跟踪执行：
def digit(n):
print ('\nCalling "digit" with n == {}'.format (n))
if n < 10:
print ('In the "if" now for n == {}'.format (n))
result = 1
print ('Exiting "digit" from the "if" with n == {}, result now is {}'.format (n, result))
return result
else:
print ('In the "else" now for n == {}'.format (n))
result = 1 + digit(n/10)
print ('Exiting "digit" with n == {}, result now is {}'.format (n, result))
return result
print ('Nr of digits is: {}'.format (digit (10000)))它打印：
D:\aaa>call C:\Python35\python.exe so.py
Calling "digit" with n == 10000
In the "else" now for n == 10000
Calling "digit" with n == 1000.0
In the "else" now for n == 1000.0
Calling "digit" with n == 100.0
In the "else" now for n == 100.0
Calling "digit" with n == 10.0
In the "else" now for n == 10.0
Calling "digit" with n == 1.0
In the "if" now for n == 1.0
Exiting "digit" from the "if" with n == 1.0, result now is 1
Exiting "digit" with n == 10.0, result now is 2
Exiting "digit" with n == 100.0, result now is 3
Exiting "digit" with n == 1000.0, result now is 4
Exiting "digit" with n == 10000, result now is 5
Nr of digits is: 5同样有帮助的是:在函数的每次调用中，一个新的本地数据块被堆在内存中的一个称为堆栈的东西上。在这种情况下，数据块只是参数n，作为局部变量存储。在调用的每个出口(因此在其中一个返回)中，这段数据将从堆栈中取出并丢弃。简洁地说:每个函数调用都有自己的堆栈框架。
拿几张纸，每次调用(见输出)时，在上面写n，然后把它放在堆栈上。然后在每个出口上扔掉上面的纸。虽然这不是一颗神奇的子弹，但它可以帮助你的想象力。
底线:你可能需要相当长的时间才能“点击”你的大脑。但这真的值得一段时间。如果需要一周或更长时间，不要感到惊讶。这是正常的，尽管并非所有的程序员都会承认这一点。试着一步一步地跟踪程序的执行，使用我的答案中的输出和一堆纸条。过了一会儿:点击..。如果你头晕，不要盯着这个问题超过四分之一，第二天再试一次(根据经验.)。
Python专家注意: Python中的“堆栈”模型只是概念上的，而在例如C++中，它是真实的。但是它是递归行为的一个很好的模型。
Stack Overflow用户
发布于 2016-10-07 11:12:32
递归的关键是通过使用同一问题的较小版本的解决方案来解决问题。
在您的例子中，您可以通过删除最后一个数字来计数数字，然后添加其余数字的计数。
digits(n) = 1 + digits(n/10)
digits(n) = 1 + (1 + digits((n/10)/10))
...在某种程度上，您必须有一个digits(n)的具体值，否则它将永远存在，因此您将基本大小写定义为一个已知值。当n < 10时，我们知道它只有一位数。
这是一个非常简单的例子，但是递归对于理解一个问题是非常强大的。
Stack Overflow用户
发布于 2016-10-07 10:51:46
此图像可能会帮助您更直观地理解：
每个分数都是对digit函数的另一个调用，最终停止的更改。然后，程序从下到上工作，计算它的“拆解”的指令栈。
它对于对上一次执行的结果执行相同的指令很有用。有时您可以更容易地使用迭代，有时您不能。它通常意味着存储更少的状态，然后需要更新。
https://stackoverflow.com/questions/39915330
复制相似问题
腾讯云开发者
