递归

分支转向是算法的灵魂，而递归则是允许函数和过程进行自我调用，这是实现分支转向的一种机制。
递归的价值在于，许多应用问题都可简洁而准确的描述为递归形式。
递归也是一种基本而典型的算法设计模式。这一模式可以对实际问题中反复出现的结构和形式做高度概括，并从本质层面加以描述和刻画，从而导出高效的算法。
递归思想可以使我们从宏观理解和把握应用问题的实质深入挖掘和洞悉算法过程的主要矛盾和一般性模式，并最终设计和编写出简洁而优雅的算法。

策略：减而治之-线性递归

介绍

减而治之：递归每深入一层，待求解问题的规模都缩减一个常数，直至最终退化为平凡的小问题。
线性递归：算法可能向更深一层进行自我调用，且每一递归实例对自己的调用至多一次。于是每一层次上至多只有一个实例，且他们构成一个线性的次序关系。

实例

举例1：数组求和-单递归基

//数组长度为n
int sum(int A[] ,int n)
{
    if(1 > n)   //递归基
        return 0;
    else
        return sum(A,n-1) + A[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[lo] , A[hi]);
        reverse(A , lo + 1, hi - 1）；// 递归调用在递归实例中的最后一步
    ｝
    //else中隐藏了其他的两种递归基， lo == hi ; lo > hi
｝

优化策略

相较于同一算法的迭代版，递归算法消耗的空间更多。所以要将其转换为迭代版。

线性递归中，若递归调用在递归实例中恰好以最后一步操作的形式出现，则称为尾递归。尾递归可以简洁的转换为等效的迭代版本

void reverse(int * A, int n)
{
    int lo = 0;
    int hi = n-1;
    while( lo < hi){      //可以看出 while循环和递归有一定联系，相互转换
        swap( A[lo] , A[hi]);
        lo++, hi--;
    }        
｝

策略：分而治之-二分递归

介绍

分而治之：将问题分解为若干规模更小的子问题，再通过递归机制分别求解。这种分解一直进行下去，直到子问题规模缩减到平凡情况。
二分递归：通常将原问题一分为二，需强调的是，无论是分解为两个还是更大常数个子问题，对算法总体的渐进复杂度并无实质影响。
对比线性递归：在线性递归中整个计算过程仅出现一次递归基，而在二分递归中递归基出现的相当频繁，总体而言有超过半数的递归实例都是递归基。
效率：为使分治策略真正有效，不仅要保证子问题划分和子解答合并要高效地实现，还必须保证子问题之间相互独立--各子问题可独立求解，而无需借助其他子问题的原始数据或中间结果。否则，要么子问题之间必须传递数据，要么子问题之间需要相互调用，无论如何都会导致时间和空间的复杂度无谓增加。

实例

举例1：

int fib (int n)
{
    return ( 2 > n) ?
        n : fib(n - 1) + fib( n - 2);
}

优化策略

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

如果递归算法中有大量重复的递归实例，那么就采用该策略，具体而言有两种行之有效的方法。一种称为制表策略，一种称为动态规划。下面对这两种策略进行实例说明

制表策略 --每遇到一个子问题都首先查验它是否已经计算过，以期通过直接调阅记录得到解答

//该实例实际将二分递归转成线性递归了
int fib( int n , int & prev)
{ 
    if( 0 == n){  // 若到达递归基
        prev = 1;   
        return 0;    // prev 对应的是 fib(-1) = 1 , return 0  对应 fib(0) = 0;
    }
    else{
        int prePrev;     // 定义一个未知的 fib(n-2)
        prev = fib( n-1 , prePrev);
        return prePrev + prev;  // return  fib(n-1) + fib(n-2)
    }
}        

int fib( int n)  //主入口
{
    int prev;  //定义一个未知的 fib(n-1)
    return fib( n , prev);
}    
    

动态规划：从递归基出发，自底而上递推得出各子问题的解，直至最终原问题的解

int  fib( int n )
{
    int f = 1 , g = 0;   //初始化 fib(-1) fib(0)
    while ( 0 < n -- ){
        g = g+ f;
        f = g - f;
    }
    return g;
}