递归

#

线性递归

例子1：数组求和

int sum( int A[], int n) {        //数组求和算法：线性递归版
    if ( 1 > n )        //平凡情况，递归基
        return 0;        //直接计算
    else                //一般情况
        return sum(A, n-1) + A[n - 1];        //递归：前n-1项之和，再累计第n-1项
}

每一递归实例对自身的调用至多一次。于是，每一层次上至多只有一个实例，且它们构成一个线性的次序关系。此类递归模式称作“线性递归”，这是递归最基本形式。

递归算法必须设置递归基，且确保总能执行到。针对每一类可能出现的平凡情况，都需设置对应的递归基。递归基可能不止一个。

例子2：数组倒置

数组倒置算法的统一入口：

void reverse(int*, int, int);       //重载的倒置算法原型
void reverse(int* A, int n)        //数组倒置
{ reverse(A, 0, n-1); }            //由重载的入口启动递归或迭代算法
void reverse(int* A, int lo, int hi) {  //数组倒置(多递归基版)
    if（lo < hi) {
        swap( A[li], A[hi] );           //交换
        reverse(A, lo+1, hi-1 );        //递归倒置A(lo,hi)
    } //else隐含了两种递归基
}

尾递归及其消除

在线性递归算法中，若递归调用在递归实例中恰好以最后一步操作的形式出现，则称作尾递归。上述数组倒置算法就是典型的尾递归。

尾递归形式的算法，可以转换为等效的迭代版本：

void reverse(int* A, int lo, int hi) {  //数组倒置(迭代版)
next:   //算法起始位置添加跳转标志
    if (lo < hi) {
        swap( A[lo], A[hi] );       //交换
        lo ++; hi-- ;               //收缩待倒置区间
        goto next;                  //跳转至起始位置
    }  //else隐含了迭代的终止
}

goto语句最好尽力回避，所以进一步调整，消除goto语句

void reverse( int* A, int lo, int hi) {
    while(lo < hi)
        swap(A[lo++], A[hi--]);
}

二分递归

每一递归实例可能做多次递归，故称作”多路递归“。通常都是将原问题一分为二，故称作”二分递归”。

例子1：数组求和（二分递归版）

int sum(int A[], int lo, int hi) {  //数组求和算法：二分递归版
    if (lo == hi)  
        return A[lo];       //直接返回
    else {
        int mi = (lo + hi) >> 1;        //以居中单元为界，将原区间一分为二
        return sum(A,lo,mi) + sum(A,mi+1,hi);       //递归对各子数组求和，然后合计
    }
}

例子2：Fibonacci数：二分递归

考查Fibonacci数列第n项fib(n)的计算问题，该数列定义如下：

fib(n) = n; n <= 1

fib(n) = fib(n-1) + fib(n-2); n>= 2

二分递归版：

_int64 fib( int n ) { //计算Fibonacci数列的第n项
    return ( 2 > n ) ? 
        (_int64) n      //若到达递归基，直接取值
        : fib(n - 1) + fib(n - 2);      //否则，递归计算前两项，其和即为正解

这种算法虽然简洁，但是效率及其低下，这是指数复杂度算法，时间复杂度为O(2^n)。

优化策略：

借助一定量的辅助空间，在各子问题求解之后，及时记录下其对应的解答。

1.制表或记忆策略

线性递归版：

_int64 fib(int n, _int64& prev) {   //计算Fibonacci数列第n项:入口形式fib(n,prev)
    if ( n == 0)                    //若到达递归基
    { prev = 1; return 0; }         //直接取值:fib(-1) = 1, fib(0) = 0
    else {
        _int64 prevPrev; prev = fib(n-1,prevPrev);      //递归计算前两项
        return prevPrev + prev;     //其和即为正解
    }
}//用辅助变量记录前一项，返回数列的当前项，时间复杂度为O(n)

2.动态规划策略

在以上线性递归版fib()算法可见，其中所记录每一个子问题的解答，只会用到一次，在该算法抵达递归基之后的逐层返回过程中，每向上返回一层，以下各层的解答均不必继续保留。

迭代版：

_int64 fibI( int n ) {  //计算Fibonacci数列的第n项(迭代版):O(n)
    _int64 f = 1, g = 0;        //初始化：fib(-1),fib(0)
    while(n-- > 0)  { g += f; f = g - f; }      //依据原始定义，通过n次加法和减法计算fib(n)
    return g;
}