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

递归

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

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

我们先看一个简单的示例,写程序求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

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

京ICP备13031296号-4