算法小结之递归

发表于 分类于 阅读次数： 本文字数： 4k 阅读时长 ≈ 4 分钟

前言

初识汉诺塔，见其递归解法，舌挢不下，以为神技。

概念

递归(Recursion) 维基百科：

Recursion in computer science is a method of solving a problem where the solution depends on solutions to smaller instances of the same problem. Such problems can generally be solved by iteration, but this needs to identify and index the smaller instances at programming time. At the opposite, recursion solves such recursive problems by using functions that call themselves from within their own code. The approach can be applied to many types of problems, and recursion is one of the central ideas of computer science.

递归(Recursion) 百度百科：

递归算法（英语：recursion algorithm）在计算机科学中是指一种通过重复将问题分解为同类的子问题而解决问题的方法。递归式方法可以被用于解决很多的计算机科学问题，因此它是计算机科学中十分重要的一个概念。绝大多数编程语言支持函数的自调用，在这些语言中函数可以通过调用自身来进行递归。计算理论可以证明递归的作用可以完全取代循环，因此在很多函数编程语言（如 Scheme）中习惯用递归来实现循环。

随笔

从代码的角度来看，递归最显著的特征就是一个递归方法会在方法体内部调用自身。

犹记得在学习谭浩强老师的 C 语言程序设计时，第一次见到汉诺塔问题，当时苦苦思索也难以理解，甚至直接将代码背下来，当时还是太心急，忘记学习要循序渐进了。😅

如果对数学归纳法掌握得很熟练，那递归的概念也就很好理解了，如今递归算法写的也算是信手拈来了，对递归的学习过程也有了自己的理解，顺着以下三个问题来学习或回顾一下递归吧。

问题一：阶乘

一个正整数的阶乘（factorial）是所有小于及等于该数的正整数的积，并且 0 的阶乘为 1。

0! = 1
n! = 1 x 2 x 3 x … x (n - 1) x n , n > 0

根据阶乘的定义，结合数学归纳法的思路，来思考一个求 integer 阶乘的值的方法怎么写：

  1. 方法声明：BigInteger Factorial(BigInteger integer)，下面用 n 代表参数 integer

  2. 当 n = 1 时，命题成立，也就是说 Factorial(1) == 1 ，这个很容易写

    1
    2
    3
    4
    if (integer == 1)
    {
        return 1;
    }

  3. 假设对于任意 n = m, m 为大于 1 的正整数 时，命题成立，那么 Factorial(m) == m!

  4. 求证 n = m + 1 ，命题也成立，那么我们就需要证明 Factorial(m + 1) == (m + 1)!

  5. 根据阶乘的定义，易得 (m + 1)! = (m + 1) x m!

  6. 结合 3 和 4，也就是要证明 Factorial(m + 1) == (m + 1) x Factorial(m)

  7. 借鉴数学归纳法的思路结束，不需要真的去证明，根据第 3 点的假设，我们将 m = integer - 1 代入上式，可得 Factorial(integer) == integer x Factorial(integer - 1)

  8. 那么，对于任意大于 1 的分支也求解出来了

    1
    2
    3
    4
    if(integer > 1)
    {
        return integer * Factorial(integer - 1);
    }

  9. 再补充一个 0 的阶乘为 1 的分支

    1
    2
    3
    4
    if(integer == 0)
    {
        return 1;
    }

  10. 至此，阶乘的定义已经完全用代码表示出来了，完整的方法整合如下

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    BigInteger Factorial(BigInteger integer)
    {
        if (integer == 0)
        {
            return 1;
        }
        else if (integer == 1)
        {
            return 1;
        }
        else
        {
            return integer * Factorial(integer - 1);
        }
    }

或许你发现 integer == 1 这个分支不写，结果也是正确的，因为 Factorial(1) == 1 x Factorial(0) 恰好成立，但这只是一种巧合，这也就是规定 0! = 1 的理由。

阶乘的问题到这里就结束了，从这个思考过程中可以整理出递归算法的通用思路：

  1. 判断一个问题基于变量的不同，这些答案彼此关系是否独立，还是具有依赖关系？例如计算一个数的阶乘的答案是有依赖关系的，4! = 4 x 3!, 3! = 3 x 2!, 2! = 2 x 1!
  2. 将这种依赖关系表达出来，Factorial(integer) == integer x Factorial(integer - 1)
  3. 找到最简单的答案，Factorial(1) == 1
  4. 组合起来，加上 0! = 1 这个定义，就是完整的阶乘递归算法了。

问题二：斐波那契数列

斐波那契数列的定义：一个数列的前两项均是 1，这个数列从第 3 项开始，每一项都等于前两项之和。

斐波那契数列：1,1,2,3,5,8,13,21……

我们定义一个方法是求斐波那契数列第 index 项的值：BigInteger Fibonacci(BigInteger index)

递归算法的思路：

  1. 斐波那契数列第 index 项的值是依赖 index - 1 和 index - 2 项的值的，也就是
    Fibonacci(index) == Fibonacci(index - 1) + Fibonacci(index - 2)
  2. 找到最简单的答案，根据定义，Fibonacci(1) == Fibonacci(2) == 1

那么，整合一下就是

1
2
3
4
5
6
7
8
9
10
11
BigInteger Fibonacci(BigInteger index)
{
    if (index == 1 || index == 2)
    {
        return 1;
    }
    else
    {
        return Fibonacci(index - 1) + Fibonacci(index - 2);
    }
}

问题三：汉诺塔

汉诺塔（又称河内塔）问题是源于印度一个古老传说的益智玩具。大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着 64 片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。

查看演示

根据汉诺塔的规则，我们假设有名为 A，B，C 的三根柱子，其中 A 柱子上有从小到大依次摆放的 n 个圆盘，目标是将圆盘全部从 A 移动到 C 上，B 作为辅助。

同样，我们定义一个方法来解决汉诺塔问题,
void Hanoi(BigInteger count, string current, string transfer, string destination)
这个方法我们先认为，它就是将 count 个圆盘从 current 搬到 destination，transfer 作为辅助。

递归算法的思路：

  1. 将 n 个圆盘看作两部分，一部分是下面最大的 1 个圆盘，另一部分是除最大以外的 n-1 个圆盘，那么按照两个圆盘的玩法，我们很容易有这样的思路：先将 n-1 个圆盘从 A 搬到 B，C 为辅助；再将最大的圆盘从 A 搬到 C，B 为辅助；最后将 n-1 个圆盘从 B 搬到 C。根据上面的方法定义，用代码来翻译一下：
    1
    2
    3
    Hanoi(n - 1, A, C, B);
    Hanoi(1, A, B, C);
    Hanoi(n - 1, B, A, C);
  2. 找到最简单的答案，当然是 1 个圆盘的情况，直接从 A 搬到 C
    1
    2
    3
    4
    if (count == 1)
    {
        Console.WriteLine($"Move disc from {A} to {C}");
    }

那么，求解 n 个圆盘的调用就是 Hanoi(n, "A", "B", "C") ，整合一下就是

1
2
3
4
5
6
7
8
9
10
11
12
13
void Hanoi(BigInteger count, string current, string transfer, string destination)
{
    if (count == 1)
    {
        Console.WriteLine($"Move disc from {current} to {destination}");
    }
    else
    {
        Hanoi(count - 1, current, destination, transfer);
        Hanoi(1, current, transfer, destination);
        Hanoi(count - 1, transfer, current, destination);
    }
}

思维拓展：八皇后

在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

这个问题的思路在下一篇 动态规划 中再做讨论。

后记

三个递归问题的源码在HT.Algorithm的 Recursion 项目中。

复杂的的问题通过递归算法能够写出很符合思维的优雅代码，不过通常这种优雅伴随着难以接受的时间复杂度和空间复杂度，这就涉及到更多有意思的知识了，大家可以去LeetCodeCN-递归中自行探索。当然这些问题也能够用非递归的方式去解决，例如汉诺塔的非递归解法，有兴趣的朋友自行百度。