递归的力量(一)

学C语言的时候老师说递归挺难的,但也是很好用的,同时还是一个合格的程序员必须要掌握的。

从学编程以来对递归的理解就不太深刻。一直就停留在“自己调用自己”的程度上。这其实这只是递归的表象(严格来说连表象都概括得不全面,因为除了“自己调用自己”的递归外,还有交互调用的递归)。而递归的思想远不止这么简单。前些日子看了一本叫《程序设计抽象思想》的书,里面很详细的论述了递归的思想。看后令我颇受启发。所以,我开始写这个关于递归的系列,希望能与同道们一同探讨一下递归的力量

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

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

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

  • 可以通过递归调用来缩小问题规模,且新问题与原问题有着相同的形式
  • 存在一种简单情境,可以使递归在简单情境下退出
如果一个问题不满足以上两个条件,那么它就不能用递归来解决。

举个例子:

费波纳契数列的第N项的值。
这是一个经典的问题,说到递归一定要提到这个问题。费波纳契数列这样定义:

f(0) = 0, f(1) = 1, 对 n > 1, f(n) = f(n-1) + f(n-2)

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

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

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

int fib(n){
    if(n == 0)
        return 0;
    else if(n == 1)
        return 1;
    else
        return f(n-1) + f(n-2);
}

注意:在编写递归调用的函数的时候,一定要把对简单情境的判断写在最前面,以保证函数调用在检查到简单情境的时候能够及时地中止递归,否则,你的函数可能会永不停息的在那里递归调用,你就成了造出第一个永动机的人了。

喜欢这篇文章?

欢迎订阅 PureWeber.com - 纯粹互联网。接收免费的更新提醒,以及订阅读者独家优质内容。

段 志岩

喜读书,未破一卷;好哲学,不求甚解。

讨论

  1. Well done!

  2. Pingback: About Recursion | majestyhao

加入讨论

电子邮件地址不会被公开。 必填项已用*标注