引言

你想买部新手机，于是你去问老爸要钱，老爸说：“找你老妈要去！”，然后你听了老爸的话，找到老妈，老妈说：“想要钱问你老爸要！”，于是你又听了老妈的话，结果你又去找老爸，无奈老爸的回答还和刚才一样，你又去找老妈，老妈的回答也还是刚才那样，然后。。。你就进入递归了！ 

递归定义

参见：递归定义

算法思想

看到上面的定义你也许会苦笑，这算什么定义？但是递归就是这样的一个思想，直接或者间接的调用自身的算法，就叫递归。使用递归算法，往往使函数的定义和算法的描述简洁且容易理解。

例题1（阶乘函数）

阶乘函数可递归的定义为：

$n! = \left\{ \matrix{ 1\matrix{ {} & {} & {\matrix{ {} & {n = 0} \cr } } \cr } \hfill \cr n \cdot (n - 1)\matrix{ {} & {n > 0} \cr } \hfill \cr} \right.$

图解

思想

阶乘函数的自变量n的定义域是非负整数。递归式的第一式给出这个函数的初始值，是非递归定义的，在递归函数中，必然存在非递归定义的初始值，用来结束递归，否则程序将一直递归下去，进入死循环中，递归式的第二式是根据阶乘的定义，利用较小的自变量的函数值来表示较大的自变量的函数值，定义式的左右两边都引用了阶乘记号，是一个递归定义式。

代码

int factorial(int n){
    if(0 == n)
        return 1;
    return n*factorial(n-1);　
}

例题2（欧几里得算法）

算法描述

欧几里德算法又称辗转相除法，用于计算两个整数a,b的最大公约数。

推理过程

已知整数x、y（x > y），欲求x、y的最大公约数z，我们用函数gcd(x,y)表示，那么我们知道，此时x、y均是z的倍数，并且x/z和y/z互质，那么我们可知gcd（x, y）= gcd(x-y, y)，因此可得gcd（y,  x%y）= gcd（x, y），那么此时我们按照上面的化简过程，我们可以化简到x%y=0，那么此时x即为最大公约数。

代码

int gcd(int x, int y){
    if(0 == y)
        return x;
    return gcd(y, x%y);　
}

递归的优劣

【优势】

使函数的定义和算法的描述简洁且容易理解。

【劣势】

函数递归的过程需要系统堆栈，所以空间消耗要比非递归代码要大很多。而且，如果递归深度太大，可能造成栈溢出。

递归与其他算法

递归在其他算法中也得到了广泛的使用，在深搜、并查集、树的遍历等过程中均有递归的影子，递归简单易懂的算法描述给其他算法再来了很大的便利，使其他算法也变得简单易懂。 

总结回顾

递归算法的实现类似于多个算法的嵌套调用，只是调用算法和被调用算法是同一个算法，因此，和每次调用相关的概念是递归调用算法的调用层次，如果调用一个递归算法的主函数为第0层时，那么从主算法调用递归算法为进入第一层调用，从第i层递归调用本算法为进入第i+1层调用。反之，退出第i层调用，则进入第i-1层调用。

例题推荐

hdu：1997、2064

poj：1664

本文由金磊提供，禁止转载。