如何学习递归呢？ 第1页

谢邀。

我们从小，就一直听着一个递归的故事长大：从前有座山，山里有座庙，庙里有个老和尚在讲故事，老和尚在讲：从前有座山，山里有座庙.......

关于递归的学习，有一个很经典的例子：在学习递归，首先，你应该学习一下，什么是递归。

递归是一种思考问题、描述问题的方法。一个基本的思想就是，把一个复杂问题化为一系列简单问题的重复。

我们以遍历树为例，遍历一棵树，首先先从根节点开始，首先先遍历根节点下的每一个子节点，然后，再把这些子节点，作为一个新的树的根节点，重复上述的遍历过程。伪代码如下

tree_travel( tree_node root )
{
foreach( node in root.children )
tree_travel( node );
}

通过这个例子，我们可以发现，递归还有一个特点，就是问题的规模和解决问题的方法没有关系，或者只是一个参数没有很大的影响。递归所做的，就是把复杂的问题一级一级的展开，使得每一级的处理方法都一模一样。我们在讲一下汉诺塔的例子，我们假设三个柱子分别是ABC，盘子由小到大分别用1、2、3...表示。

对于两个盘子的情况：

首先，先将1盘子从A移动到B，然后将2盘子从A移动到C，最后将1盘子从B移动到C。

三个盘子的情况：

首先，先将1、2盘子从A移动到B，然后将3盘子从A移动到C，最后将1、2盘子从B移动到C。

那么1、2两个盘子怎么样从A移动到B，再从B移动到C呢？其实，这个问题我们刚刚在举两个盘子的例子的时候已经解决过了。

那么，对于64个盘子的情况，我们也可以很容易解决。

首先，先将1，2，3......63盘子从A移动到B，然后将64盘子从A移动到C，最后将1，2，3......63盘子从B移动到C。

而对于1，2，3.....63这63个盘子怎么样从A移动到B，再从B移动到C，我们在解决63个盘子的情况的时候，已经处理过了。

关于递归，上面有几位讲得也比较好，我也就不赘述了。

关于另一个问题，为什么平时的项目中，很少见到递归。这个是因为，一个正经的程序，是应当尽量少或者尽可能不出现递归的程序。在程序中使用递归，除了能够少写几行代码，给程序员带来一点点方便以外，没有别的太多的好处，甚至有时候是有害的。

首先，你应当明确一点，所有的递归程序，都可以改写成非递归的方法，而在这个非递归的方法中，你不得不维护一个栈，来完成原来程序调用栈的能够，从而使得程序能达到跟递归一样的效果。为什么说递归是不好的呢，那是因为调用栈的大小是有限的，而递归的深度，有的时候是不好估计的。一旦递归的深度过大，使得调用栈溢出了，那么对程序的影响是非常大的。而在非递归的方法中，由于栈由自己维护，即使“递归”的深度过大，程序也在你的控制范围之内，可以自己中断“递归”过程并作相应的处理。

然后，递归使得程序书写的效率提高，但并不意味着执行的效率会提高，比如那个斐波那契数列的例子，你自己算一下就会发现有将近一般的计算式重复的，比如那个fibo(n-2)是会计算两次的，而越深的项重复次数就会越多。除了这个问题外，递归程序的执行效率一般也不必循环高，因为在栈上开辟新空间、分配局部变量的时间也是不小的。你可以自己尝试的写一下这样的程序，和@陈甫鸼 同学的那个程序一样，还是那个斐波那契数列的例子，也还是python，非递归的解法。数字不用很大，求斐波那契数列的第50项，递归的方法就已经很难在你能容忍的时间内完成了。

def fibo( n ):
if n <= 0:
raise Exception()
elif n == 1:
return 0
elif n == 2:
return 1
else:
a = 0
b = 1
s = 0
while n > 2:
s = b + a
a = b
b = s
n -= 1
return s

最后，关于递归的建议，一定要会递归的解决问题，但是要避免写递归的程序。