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

作者：手机用户2602891751 | 来源：互联网 | 2014-05-16 13:35

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

最近重新看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以上基本就挂了。

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