漫谈递归：递归需要满足的两个条件

很多人对递归的理解不太深刻。一直就停留在“自己调用自己”的程度上。这其实这只是递归的表象（严格来说连表象都概括得不全面，因为除了“自己调用自己”的递归外，还有交互调用的递归）。而递归的思想远不止这么简单。

递归，并不是简单的“自己调用自己”，也不是简单的“交互调用”。它是一种分析和解决问题的方法和思想。简单来说，递归的思想就是：把问题分解成为规模更小的、具有与原问题有着相同解法的问题。比如二分查找算法，就是不断地把问题的规模变小（变成原问题的一半），而新问题与原问题有着相同的解法。

有些问题使用传统的迭代算法是很难求解甚至无解的，而使用递归却可以很容易的解决。比如汉诺塔问题。但递归的使用也是有它的劣势的，因为它要进行多层函数调用，所以会消耗很多堆栈空间和函数调用时间。

既然递归的思想是把问题分解成为规模更小且与原问题有着相同解法的问题，那么是不是这样的问题都能用递归来解决呢？答案是否定的。并不是所有问题都能用递归来解决。那么什么样的问题可以用递归来解决呢？一般来讲，能用递归来解决的问题必须满足两个条件：

• 可以通过递归调用来缩小问题规模，且新问题与原问题有着相同的形式。
• 存在一种简单情境，可以使递归在简单情境下退出。

如果一个问题不满足以上两个条件，那么它就不能用递归来解决。

为了方便理解，还是拿斐波那契数列来说下：求斐波那契数列的第N项的值。

这是一个经典的问题，说到递归一定要提到这个问题。斐波那契数列这样定义：f(0) = 0, f(1) = 1, 对n > 1, f(n) = f(n-1) + f(n-2)

这是一个明显的可以用递归解决的问题。让我们来看看它是如何满足递归的两个条件的：

1. 对于一个n>2, 求f(n)只需求出f(n-1)和f(n-2)，也就是说规模为n的问题，转化成了规模更小的问题；
2. 对于n=0和n=1，存在着简单情境：f(0) = 0, f(1) = 1。

因此，我们可以很容易的写出计算费波纳契数列的第n项的递归程序：

1	int fib(n){

2	if(n == 0)

3

return 0;

4	else if(n == 1)

5

return 1;

6

else

7	return f(n-1) + f(n-2);

8

}

在编写递归调用的函数的时候，一定要把对简单情境的判断写在最前面，以保证函数调用在检查到简单情境的时候能够及时地中止递归，否则，你的函数可能会永不停息的在那里递归调用了。