递归

递归---Recursion

在学习清华大学邓俊辉邓公的数据结构这门课中，邓公引用了这样一句话：

To iterate is human, to recurse, divine. （迭代乃人工，递归方神通。）

足见递归算法的重要性。

什么是递归？

程序调用自身的方式叫做递归，这里直接传送百度百科：递归。

递归基（Recursion-Base）

递归一般会有边界条件，也称递归基。一般是平凡问题，即能直接求解或给出答案的问题。

递归思路

递归算法的思路就是不断将复杂问题，或分而治之（Divide-And-Conquer），或减而治之（Decrease-And-Conquer），这是一个从上而下的过程，直到触碰到递归基后，再一步步自下而上，不断将子问题的答案合并，最终形成最终答案。

分而治之（Divide-And-Conquer）

分：即将一个复杂问题根据某个依据，分为两个同等规模（不一定完全相同）的两个子问题，然后不断分解下去，直到某个子问题退化为一个平凡问题（规模为0或1，或该子问题已有解等情况）。

治：代将平凡问题结果返回，两个平凡问题答案合并为一个子问题答案，并不断返回、合并，最后得到问题解。

应用：如著名的快速排序（Quick-Sort），即将规模为n的序列排序先分解为n/2的两个子问题，再逐自分解，最后再合并。

减而治之（Decrease-And-Conquer）

与“分”不同，“减”是将当前复杂问题划分为：一个平凡问题，一个规模缩减的子问题。子问题会不断缩减，直到退化为平凡问题，再逐步合并，得到答案。

递归算法复杂度分析

递归算法的复杂度分析也是一个重点、难点。这里介绍两种常用方法：

递归跟踪分析：检查每个递归实例，累计所需时间，调用语句本身计入对应子实例，其总和即算法执行时间；
递归方程：通过写出递推方程，逐步推出复杂度。

这里需要说明的是：

1，分析递归算法复杂度是个难点，需要一定的数学知识，通过不断练习、分析会逐步提高这方面能力；

2，我们要学会“封底估算”，这是一大技巧，重点在于我们要利用数学而不能依赖于数学，原因是很多时间我们并不需要得到一个很精确的数字来表明复杂度是多少，我们只要能大抵推算出与实际答案同一个数量级的答案即可，比如1000000与1，我们认为是相同的，因为都是常量。大多时候我们甚至能通过直觉、经验直接得出一个与精确答案相差无几的答案，而这种估算我们随便找张纸都能算出来。

递归算法好吗？

没有东西在任何时候都是最完美的，只有最合适的。递归算法也是这样。

不得不承认，递归算法很重要！很多复杂问题能够通过递归算法很简明的描述出来，而且应该很广泛，树、图等都有应用。

但递归算法对计算机栈的占用很大，每次调用一次自身，系统栈就得将自身函数的一些环境压入，直到算出答案才能弹出，有时候这是不能接受的。尤其是尾递归（在函数尾部返回），现在很多编译器会自动将尾递归改写。

而且递归并没有加快运行效率，它缩短了找到问题之前需要走步数，从而减少了运行时间，但这个前提是要合并编写这个递归函数，不然有时候子问题的重复计算会使运行时间更长，比如下面应用中要讲到的Fibonacci数。

递归应用

Fibonacci数

最大公约数

求进制数

参数：1，要转换的十进制数；2，保存结果的字符数组；3，要转换的进制。

返回值：字符数组有效字符个数。

int dectobase(int num, char* conversion, int base){
    if( num > 0 ){
        int cnt = dectobase( num/base, conversion, base) + 1;
        *(conversion + cnt - 1) = num%base + '0';
        return cnt;
    }  
    return 0;
}

HanoiTower

1 void hanota(int N, char s, char t, char g){
2     if( N > 0 ){
3         hanota( N-1, s, g, t);
4         printf("%c->%c
", s, g);
5         hanota( N-1, t, s, g);
6     }
7 }

整数分解为若干项和

排列组合

寻找中位数

两个有序序列的中位数

最长公共子序列

八皇后问题