递归

引论

递归的定义是:A function defined in terms of itself is called recursive. 也就是说一个函数的定义需要用到这个函数的本身。递归是一个很奇妙的思想,从上面的定义看去,递归貌似一个死循环,这个当然是不对的,递归总会有一个结束的条件,也就是基准情况,这个基准情况规定了递归什么时候结束。下面来看一个例子:

计算阶乘n! = n(n-1)…*1.

如果利用递归思想的话,我们可以发现factorial(n) = n!=n*factorial(n-1);这就是一个递归的形式。

1
2
3
4
5
6
7
int factorial(int n)  
{
if(n==1)
return 1;
else
return n*factorial(n-1);
}

代码的第二行与第三行就是处理的基准情形。这是由于这个基准情形,使得程序不会变为死循环而不停的递归,直至耗尽内存空间。
当然上面的情形也可以用迭代的方法来解决

1
2
3
4
5
6
7
int factorial(int n)  
{
int element = 1;
int i;
for(i=2;i<n;i++)
element *=i;
}

递归和迭代这两种方法都可以解决上面的问题,而且在数学上的表示是一致的,那么这两者是否等价呢?答案肯定是不等价的。一般来说递归的时间与空间消耗要大于迭代,但是递归的形式非常简单,代码形式非常优美。迭代相当于一个从前向后的过程,而递归是一个从后向前再向后的过程。
递归和迭代一般情况下是可以相互转换的,但是有些情况下,用迭代来替代递归是相当痛苦的,比如说数据结构的定义等等。

递归一般有如下几点需要注意:

1) 基准情形:也就是递归停止的标志,这是递归所不能少的

2) 不断推进:每一次递归,都要使问题朝着基准情形前进,否则是无法结束递归的

3) 设计法则:假设所有的递归调用都能运行

4) 合成效益法则:在不同的递归调用中解决同一个问题,不应该复制已有的工作。