递归

递归

递归的价值在于：许多应用问题都可以简洁而准确地描述为递归形式。

以操作系统为例，多数文件系统的目录结构都是低规定以的，具体地，每个文件都有一个最顶层的目录，其中可以包含若干文件和下一层的子目录；而在每一个子目录中，也同样可能包含若干文件和在下一层的子目录；如此递推，直至不含任何下层的子目录。通过如此的递归定义，文件系统中的目录就可以根据使劲应用的需要嵌套人一多层（只要系统的存储资源足以支持）。
递归也是一种基本而典型的算法设计模式。这一模式可以对实际问题中反复出现的结构和形式做高度概括。从程序的结构角度，递归模式能够通统筹纷繁多变的具体情况，避免复杂的分支以及嵌套的循环，从而更为简明的描述和实现算法，减少代码量，提高算法的可读性。但是从效率而言，递归可能并不如迭代。
线性递归
例如，求数组中元素的和：
```
int sum(int A[],int n)
{
  if(1>n) //平凡情况，递归基
     return 0; //直接（非递归式）计算
  else
      return sum(A,n-1) + A[n-1]; //递归：前n-1项之和，在累计第n-1项
}
```
由上面的实例，可以看出保证递归计算法有穷性的基本技巧：首先判断并处理n=0之类的平凡情况，以避免饮无限递归而导致系统溢出，这类平凡情况统称为“递归基”（base case of recursion）

算法sum()可能朝着更深层进行自我调用，且每一递归实例对自身的调用至多一次。于是。每一层次上至多只有一个实例，且它们构成一个线性的关系。此类递归模式因而称作“线性递归”（liner recursion）。

这种形式中，应用问题总是可以分为两个独立的子问题：

其中一对对应于单独的某个元素，可直接求解（如：A[n-1]）；
另一个对应于剩余部分，且其结构与原问题相同。

另外，子问题的解经简单的合并（比如整数相加）之后，即可得到原问题的解。

减而治之

线性递归的模式，往往对英语所谓的“减而治之”（decrease-and-conquer）的算法策略：每深入一层，带求解问题的规模都缩减一个常数，直至最终蜕化为平凡的小（简单）的问题。

减而治之，如图所示，将其划分为两个子问题：
其中一个：平凡
另一个：规模缩减
**

递归分析

递归算法时间、空间复杂度的分析与常规算法不一样，有其自身的规律和特定的技巧。以下将介绍“递归跟踪”、“递归方程” 两种方式。

递归跟踪

递归跟踪（recursion trace）分析：

检查每个递归实例，累计所需时间（调用与剧本是，计入对应的子实例），其总和即算法执行时间。

具体地，就是按照以下原则，将递归算法的执行过程整理为图的形式：

// 下面的图对应的函数为：
int sum(int A[],int n)
{
    if(n>1)
        return 0;
    else
        return sum(A,n-1) + A[n-1] ;
}

说明：

整个算法所需的计算时间，应该等于所有递归实例的创建、执行和销毁所需的时间的总和。

其中，递归实例的创建、销毁均由操作系统负责完成，其对应的时间成本通常可以近似为常数，不会超过递归实例中实质计算步骤所需的时间成本，故可忽略不计。

所以，我们只需统计各递归实例中非递归调用部分所需的时间。

在，本例中，但各递归实例自身只需：时间。从而，其时间复杂度为：

递推方程

与递归跟踪相比，递推方程（recurrence equation）分析法不需要会出具体的调用过程，而是通过对递归模式的数学归纳，到处复杂度定界函数的对推方程（组）及其边界条件，从而将复杂度分析，转化为递归方程（组）的求解。

如：

// 下面的图对应的函数为：
int sum(int A[],int n)
{
    if(n>1)
        return 0;
    else
        return sum(A,n-1) + A[n-1] ;
}

将处理长度为n的数组所需时间成本记作 T(n)

接下来对递推方程求解：

递归模式

多基递归

为保证有穷性，递归算法都必须设置地轨迹，且确保总能执行到。为此，针对每一类可能出现的平凡情况，都需设置对应的递归基，股同意算法的递归基可能（显示或隐式地）不止一个。

多向递归

递归算法中，不仅递归基可能有多个，递归调用也可能有多种可供选择的分支。
如：

int power(int n)
{
    if(n==0)
        return 1; //递归基
    return (n>&1)? sqr(power(n>>1)<<1 : sqr(power(n>>1); //多向递归
}

递归消除

按照递归思想可使我们得以从宏观上理解和把握应用问题的实质，深入挖掘和洞悉算法过程的主要矛盾和一般性模式，最终编写出简洁的代码。

空间成本

从递归跟踪不难看出，递归算法所消耗的空间量主要取决于递归的深度。所以相较于同一算法的迭代版本，递归版往往需要消耗更多的看空间，进而影响实际的运行速度。
另外，就操作系统而言，为实现递归调用需要花费大量额外时间来创建、维护和销毁各递归实例，这也会令计算机的负担雪上加霜。
**

尾递归及其消除

再线性递归算法中，若递归调用在递归实例中恰好以最后一步操作的形式出现，则称为“尾递归（tail recursion）”。
如：

void reverse(int* A, int lo, int hi)
{
    if (lo < hi)
        swap(A[lo], A[hi]);
    reverse(A, lo + 1, hi - 1); //尾递归
}

消除尾递归：
将尾递归形式的算法，简捷的转换为迭代版本，即：**

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

注意：

尾递归的判断应依据对算法实际执行过程的分析，而不仅仅是算法外在的语法形式。严格地说：只有当该算法（除了平凡递归基外）任一实例都终止于这一递归调用时，才属于尾递归。

如,下面的就不是尾递归：

int sum(int A[],int n)
{
    if(n>1)
        return 0;
    else
        return sum(A,n-1) + A[n-1] ;
}

尽管从表面是看似乎最后一行是递归调用，但实际上却不是尾递归——实质的最后一次操作是加法运算。

二分递归

分而治之

“凡治众如治寡，分数是也”。
与减而治之策略一样，这里也要求队员问题重新表述，保证子问题与原问题在接口形式上的一致。既然每一递归实例都可做多次递归，故称作“多路递归（multi-way recursion）”。通常都是将原问题一分为二，故称作“二分递归（binary recursion）”。

注意，无论是分解为两个还是更大常数个子问题，对算法总体的渐进复杂度并无实质影响。

实例：数组求和

int sum(int A[], int lo, int hi)
{
    if (lo == hi)
        return A[lo];
    int mi = (lo + hi) >> 1; //以居中单元为界，将原区间一分为二
    return sum(A, lo, mi) + sum(A, mi+1, hi);
}

上面代码，就像下面表示的一样：

分析其复杂度：

1.递归跟踪分析方法
为此我们需要以某一个具体地数值为例，画出所以递归实例。（这里令n=8，即数组长度为8）

由“递归跟踪”这一小节可知，对于“递归实例的创建、销毁均由操作系统负责完成，所以这部分可以故可忽略不计”，也就是说，我们在考虑复杂度的时候，可以直接把这一部分划掉：

我们把递归调用本身的语句去掉，剩下的没有显式或隐式的迭代、递归。也就是说，每一个递归实例，无论它所对应的的有效区间或长或短，都是需要O(1)的时间。