递归计算过程与迭代计算过程

编程需要了解的基础知识
服务器君一共花费了279.102 ms进行了5次数据库查询,努力地为您提供了这个页面。
试试阅读模式?希望听取您的建议

最近重新看SICP,写点感想。下面是关于递归与迭代计算的一些知识,SICP 1.2.1。

递归

递归是实现程序计算过程中的描述过程的基本模式之一,在讨论递归的问题前我们必须十分小心,因为递归包含两个方面的内容,一个是递归的计算过程,一个是递归过程,后者是语法上的事实而前者是概念上的计算过程,事实上在程序上我们也许是使用循环来实现的。

递归计算过程和我们常说的递归过程不是一回事。

  • 递归过程:“当我们说一个过程是递归的时候,论述的是一个语法形式上的事实,说明这个过程的定义中(直接或者间接地)引用了该过程本身。”
  • 递归计算过程:“在说某一计算过程具有某种模式时(例如,线性递归),我们说的是这一计算过程的进展方式, 而不是相应过程书写上的语法形式。”

一般在讨论递归的时候都喜欢用斐波那契数列来作为例子,斐波那契的算法也很简单,算法如下:

def Fib(n):  

    if (n < 1):  
        return 0  

    elif (n <= 2):  
        return 1  

    else:  
        return Fib(n-1)+Fib(n-2)

具体C语言的例子。

#include "stdio.h"
#include "math.h"

int factorial(int n);

int main(void)
{
    int i, n, rs;

    printf("请输入斐波那契数n:");
    scanf("%d",&n);

    for(i = 1; i <=n; i++)
    {
        rs = factorial(i);
        printf("%d ", rs);
    }

    return 0;
}

// 递归计算过程
int factorial(int n)
{
    if(n <= 2)
    {
        return 1;
    }
    else
    {
        return factorial(n-1) + factorial(n-2);
    }
}

程序运行:

请输入斐波那契数n:12
1 1 2 3 5 8 13 21 34 55 89 144

我们假设n=6,那么得到的计算过程就是,要计算Fib(6)就得计算Fib(5)和Fib(4),以此类推,如下图:

我们可以看到过程如同一棵倒置的树,这种方式被称之为树形递归,也被称之为线性递归。这种递归的方式非常的直白,很好理解其计算过程,一般很多人写递归都会下意识的采用这种方式。

但是缺点也是很明显的,从其计算过程可以看出,经过了很多冗余的计算,并且消耗了大量的调用堆栈,这个消耗是指数级增长的,经常有人说调用堆栈很容易在很短的递归过程就耗光了,多半就是采用了线性递归造成的。线性递归的过程可用下图描述,可以清晰的看到展开收拢的过程:

(factorial (6))
(6 * factorial (5))
(6 * (5 *  factorial (4)))
(6 * (5 * (4 * factorial (3))))
(6 * (5 * (4 * (3 * factorial (2)))))
(6 * (5 * (4 * (3 * (2 * factorial (1))))))
(6 * (5 * (4 * (3 * (2 * 1)))))
(6 * (5 * (4 * (3 * 2))))
(6 * (5 * (4 * 6)))
(6 * (5 * 24))
(6 * 120)
720

迭代

与递归计算过程相对应的,是迭代计算过程。

除了这种递归方式还有另外一种实现递归的方式,同样是上面的斐波那契数作为例子,这次我们不按照斐波那契的定义入手,我们从正常产生数列的过程入手来实现,0,1,的情况很简单可以直接返回,之后的计算过程就是累加,我们在递归的过程中要保持状态,这个状态要保持三个数,也就是上两个数和迭代的步数,所以我们定义的方法为:

def Fib(n,b1=1,b2=1,c=3):

    if n <= 2:
        return 1

    else:
        if n==c:
            return b1+b2

        else:
            return Fib(n,b1=b2,b2=b1+b2,c=c+1)

这种方法我们在每一次递归的过程中保持了上一次计算的状态,所以称之为“线性迭代过程”,也就是俗称的尾递归。由于每一步计算都保持了状态所以消除了冗余计算,所以这种方式的效率明显高于前一种,其计算过程如下:

fib(6)
fib  0,0,1
fib  0,1,2
fib  1,2,3
fib  2,3,4
fib  3,5,5
fib  5,8,6

这两种递归方式之间是可以转换的,凡是可以通过固定数量状态来描述中间计算过程的递归过程都可以通过线性迭代来表示。

“迭代计算过程是用固定数目的状态变量描述的计算过程,并存在着一套固定的规则,描述了计算过程从一个状态到下一状态转换时,这些变量的更新方式,还有一个(可能有的)结束检测,它描述这一计算过程应该中止的条件。”

以计算n的阶乘为例,其递归写为:

// 递归计算过程
function factorial(n){
     if(n == 1) {
          return 1;
     }
     return n * f(n-1);
}

同样是计算n的阶乘,还可以这样设计:

// 迭代计算过程
function factorial(n){
     return factIterator(1, 1, n);
}

function factIterator(result, counter, maxCount){
     if(counter > maxCount){
          return result;
     }
     return factIterator((counter * result), counter + 1, maxCount);
}

它的执行过程为:

(factorial (6))
(factIterator(1, 1, 6))
(factIterator(1, 2, 6))
(factIterator(2, 3, 6))
(factIterator(6, 4, 6))
(factIterator(24, 5, 6))
(factIterator(120, 6, 6))
(factIterator(720, 7, 6))

虽然factIterator方法调用了它自己,但从它的执行过程里,所需要的所有的东西就是result,counter,和maxCount。所以它是迭代计算过程。这个过程在继续调用自身时不需要增加存储,这样的过程叫尾递归。

尾递归还可以用循环来代替:

function fib(n){
     var a=0, b=1;
     for(var i=0;i<=n;i++){
          var temp = a+b;
          a = b;
          b = temp;
     }
     return b;
}

递归和迭代

递归计算过程更自然,更直截了当,可以帮助我们理解和设计程序。而要规划出一个迭代计算过程,则需设计出各个状态变量,找到迭代规律,并不是所有的递归计算过程都可以很容易的整理成迭代计算过程。

但递归计算过程会比迭代计算过程低效。

上面计算阶乘的递归计算过程属于线性递归,步骤数目的增长正比于输入n。也就是说,这个过程所需步骤的增长为O(n) ,空间需求的增长也为O(n) 。对于迭代的阶乘,步数还是O(n)而空间是O(1) ,也就是常数。

再来看斐波那契数列的递归与迭代的实现吧。

递归计算过程:

// 递归计算过程
function fib(n){
     if(n <= 1){
          return n;
     }
     return fib(n-1) + fib(n-2);
}

迭代计算过程、尾递归:

// 迭代计算过程、尾递归
function fib(n){
     return fibIterator(1, 0, n);
}

function fibIterator(a, b, counter){
     if(counter== 0){
          return b;
     }
     return fibIterator((a+b), a, counter-1)
}

斐波那契数列的递归计算过程属于树形递归,画一下它的展开方式就可以看到。它的步数是以指数方式增长的,这是一种非常夸张的增长方式,规模每增加1,都将导致所用的资源按照某个常数倍增长。而迭代计算过程的步骤增长依然是O(n),线性增长,也就是规模增长一倍,所用的资源也增加一倍。

有时候说要减少递归,就是要减少递归计算过程,用更高效的方法代替。

我们也发现,其实尾递归的过程和循环基本上是等价的,我们可以将尾递归的过程很方便到用循环来代替,所以很多的语言对尾递归提供了编译级别的优化,也就是将尾递归在编译期转化成循环的代码。不过对于没有提供尾递归优化的语言来说也是很有意义的,比如python的默认调用堆栈长度是1000,如果用线性递归很快就会消耗光,但是尾递归就不会,比如尾递归的Fib函数,用Fib(1001)调用没问题的而且跑得飞快,Fib(1002)的时候才堆栈溢出。但是如果是线性递归的方式计算n=30的时候就能明显感觉到速度变慢,40以上基本就挂了。

这里我无意对比两种方式的优劣,也许线性递归性能有差距但是它的可读性非常的强,几乎就等同于公式的直接描述,所以可以根据计算规模来合理选用。

延伸阅读

此文章所在专题列表如下:

  1. 漫谈递归:递归的思想
  2. 漫谈递归:递归需要满足的两个条件
  3. 漫谈递归:字符串回文现象的递归判断
  4. 漫谈递归:二分查找算法的递归实现
  5. 漫谈递归:递归的效率问题
  6. 漫谈递归:递归与循环
  7. 漫谈递归:循环与迭代是一回事吗?
  8. 递归计算过程与迭代计算过程
  9. 漫谈递归:从斐波那契开始了解尾递归
  10. 漫谈递归:尾递归与CPS
  11. 漫谈递归:补充一些Continuation的知识
  12. 漫谈递归:PHP里的尾递归及其优化
  13. 漫谈递归:从汇编看尾递归的优化

本文地址:http://www.nowamagic.net/librarys/veda/detail/2280,欢迎访问原出处。

不打个分吗?

转载随意,但请带上本文地址:

http://www.nowamagic.net/librarys/veda/detail/2280

如果你认为这篇文章值得更多人阅读,欢迎使用下面的分享功能。
小提示:您可以按快捷键 Ctrl + D,或点此 加入收藏

阅读一百本计算机著作吧,少年

很多人觉得自己技术进步很慢,学习效率低,我觉得一个重要原因是看的书少了。多少是多呢?起码得看3、4、5、6米吧。给个具体的数量,那就100本书吧。很多人知识结构不好而且不系统,因为在特定领域有一个足够量的知识量+足够良好的知识结构,系统化以后就足以应对大量未曾遇到过的问题。

奉劝自学者:构建特定领域的知识结构体系的路径中再也没有比学习该专业的专业课程更好的了。如果我的知识结构体系足以囊括面试官的大部分甚至吞并他的知识结构体系的话,读到他言语中的一个词我们就已经知道他要表达什么,我们可以让他坐“上位”毕竟他是面试官,但是在知识结构体系以及心理上我们就居高临下。

所以,阅读一百本计算机著作吧,少年!

《大话设计模式》 程杰 (作者)

《大话设计模式》通篇都是以情景对话的形式,用多个小故事或编程示例来组织讲解GoF(设计模式的经典名著——Design Patterns: Elements of Reusable Object-Oriented Software,中译本名为《设计模式——可复用面向对象软件的基础》的四位作者Erich Gamma、Richard Helm、Ralph Johnson,以及JohnVlissides,这四人常被称为GangofFour,即四人组,简称GoF)总结的23个设计模式。本书共分为29章。其中,第1、3、4、5章着重讲解了面向对象的意义、好处以及几个重要的设计原则;第2章,以及第6到第28章详细讲解了23个设计模式;第29章是对设计模式的全面总结。

更多计算机宝库...