递归——线性递归与二分递归

向右看齐 2022-05-21 04:41 339阅读 0赞

# 递归    #

##     ##

## 线性递归 ##

例子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;
    }

这里仅使用了两个中间变量f和g，记录当前的一对相邻的Fibonacci数。整个算法仅需线性步的迭代，时间复杂度为O(n)。