编程基础：用递归把复杂的问题简化为简单的同类问题

递归

递归算法是编程中很重要的算法，能把很多问题化繁为简，而对新手程序员来说，比较难以理解和运用。

递归简单的理解就是自己定义自己，在程序中就是自己调用自己。

我们先看一个简单的示例，写程序求n的阶乘。

n! = n * (n - 1) * (n - 2) * ...* 2 * 1

最简单的代码如下：

int main(object me, string arg)
{
    int n = atoi(arg), res = 1;
    for (int i = 1; i <= n; i++)
    {
        res *= i;
    }
    printf("%d! = %d\n", n, res);

    return 1;
}

我们知道 n! = n (n - 1)!， (n - 1)! = (n - 1) (n - 1 - 1)!……，这其中包含了递归结构。

用递归函数自己调用自己来求解，代码如下：

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

int main(object me, string arg)
{
    int n = atoi(arg);

    printf("%d! = %d\n", n, fn(n));

    return 1;
}

只是从代码看，这个递归并没有让代码简单，反而看起来复杂了，这里重点是理解递归的思维：把复杂问题转换为较为简单的同类问题。对 n! 我们先求 (n-1)!的阶乘，一直递归到求 0!。 0! 也是递归的结束条件，这一点非常重要，否则会进入死循环。

下面我们再用另一个经典问题来理解递归，通过代码求汉诺塔（Tower of Hanoi）的解法。

汉诺塔（Tower of Hanoi）起点柱A、中转柱B、目标柱C，对1层汉诺塔，我们直接把圆盘从起点柱A移动到目标柱C，对2层汉诺塔，我们需要先把1层圆盘从起点柱A移动到中转柱B，再把2层圆盘从起点柱A移动到目标柱C，最后把1层圆盘从中转柱B移动到目标柱C。而对3层汉诺塔，可以先按2层汉诺塔的解法把前2层圆盘移动到中转柱B上，再然后把3层圆盘移动到目标柱C上，最后按2层汉诺塔的解法把前2层圆盘从中转柱B移动到目标柱C上。

对 n 层汉诺塔的解法：

  1. 先把 n - 1 层圆盘从A柱移动到B柱（解出 n-1 层）
  2. 再将第 n 层圆盘从A柱移动到C柱
  3. 最后将 n - 1 层圆盘从B柱移动到C柱（解出 n-1 层）

因为在解 n - 1 层时中转柱B相当于 n - 1 层解法的目标柱，就是在不同层的情况下，起点柱、中转柱、目标柱可能是不同的，不是固定的起点A、中转B、目标C，而是变量x、y、z。现在上代码：

void hanoi(int n, string x, string y, string z)
{
    if (n)
    {
        hanoi(n - 1, x, z, y);
        printf("移动圆盘 %d ：从 %s 到 %s\n", n, x, z);
        hanoi(n - 1, y, x, z);
    }
}

int main(object me, string arg)
{
    hanoi(atoi(arg), "A", "B", "C");

    return 1;
}

通过以上递归，很简单的代码就把任意层的汉诺塔解法写出。

> test/hanoi 1
移动圆盘 1 ：从 A 到 C
> test/hanoi 2
移动圆盘 1 ：从 A 到 B
移动圆盘 2 ：从 A 到 C
移动圆盘 1 ：从 B 到 C
> test/hanoi 3
移动圆盘 1 ：从 A 到 C
移动圆盘 2 ：从 A 到 B
移动圆盘 1 ：从 C 到 B
移动圆盘 3 ：从 A 到 C
移动圆盘 1 ：从 B 到 A
移动圆盘 2 ：从 B 到 C
移动圆盘 1 ：从 A 到 C

在编程中要活用递归，包括后面重要的排序算法中有很多算法都用了递归的方式完成排序。

递归算法的致命缺陷

需要注意的是，递归运算是有致命缺陷的，并不是能用递归的优先用递归，我们以计算斐波那契数为例，以下是LPC代码：

// 递归计算斐波那契数
int fib(int n)
{
    if (n <= 2)
    {
        return 1;
    }
    else
    {
        return fib(n - 1) + fib(n - 2);
    }
}

int main(object me, string arg)
{
    int n = to_int(arg);

    printf("fib(%d) = %d\n", n, fib(n));

    return 1;
}

当n很小时性能没什么影响，可当n超过30后运算时间明显变长，当n到40时已经快不行了。

因为递归函数内部嵌套了对自身的调用，除非等到最内层的函数调用结束，否则外层的所有函数都不会调用结束。通俗地讲，外层函数被卡主了，它要等待所有的内层函数调用完成后，它自己才能调用完成。而且每一层的递归调用都会在栈上分配一块内存，有多少层递归调用就分配多少块相似的内存，所有内存加起来的总和是相当恐怖的，很容易超过栈内存的大小限制，这个时候就会导致程序崩溃。另外，每次调用函数都会在栈上分配内存，函数调用结束后再释放这一部分内存，内存的分配和释放都是需要时间的，所有的这些时间加在一起是非常恐怖的。

递归函数的解决方案存在巨大的内存开销和时间开销，而且这还是函数实现原理层面的缺陷，无法优化。

迭代

好消息是，大部分能用递归解决的问题也能用迭代来解决。所谓迭代，就是循环。

许多问题是以递归的形式进行解释的，这只是因为它比非递归形式更为清晰。但是，这些问题的迭代实现往往比递归实现效率更高，虽然代码的可读性可能稍差一些。

与递归函数相比，迭代不但没有额外的内存开销，也没有额外的时间开销。

下面使用迭代的实现的代码：

//迭代计算斐波那契数
int fib(int n)
{
    int result;
    int previous_result;
    int next_older_result;
    result = previous_result = 1;
    while (n > 2)
    {
        n -= 1;
        next_older_result = previous_result;
        previous_result = result;
        result = previous_result + next_older_result;
    }
    return result;
}

int main(object me, string arg)
{
    int n = to_int(arg);

    printf("fib(%d) = %d\n", n, fib(n));

    return 1;
}

测试数据哪怕是n = 100 也是秒出结果，而用递归到40就卡半天了。提示：具体耗时可以使用time_expression这个efun获取，如：time_expression(fib(n))，这里不做演示。

所以在开发中，可以用递归做小数据的运算和减化问题的算法解释，而在代码实现时能用迭代的优先用迭代。

京ICP备13031296号-4