java算法之递归算法

在数学与计算机科学中，递归（Recursion)）是指在函数的定义中使用函数自身的方法，直观上来看，就是某个函数自己调用自己。递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题。并且这些子问题可以用完全相同的解题思路来解决；递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点）。一旦原问题到达了这个临界点，就不用再往更小的问题上拆解了。最后，从这个临

weixin_43841461

1403人浏览 · 2024-08-06 07:00:00

weixin_43841461 · 2024-08-06 07:00:00 发布

一. 递归算法定义

在数学与计算机科学中，递归（Recursion)）是指在函数的定义中使用函数自身的方法，直观上来看，就是某个函数自己调用自己。

递归有两层含义：

递归问题必须可以分解为若干个规模较小、与原问题形式相同的子问题。并且这些子问题可以用完全相同的解题思路来解决；
递归问题的演化过程是一个对原问题从大到小进行拆解的过程，并且会有一个明确的终点（临界点）。一旦原问题到达了这个临界点，就不用再往更小的问题上拆解了。最后，从这个临界点开始，把小问题的答案按照原路返回，原问题便得以解决。

简而言之，递归的基本思想就是把规模大的问题转化为规模小的相同的子问题来解决。在函数实现时，因为大问题和小问题是一样的问题，因此大问题的解决方法和小问题的解决方法也是同一个方法。这就产生了函数调用它自身的情况，这也正是递归的定义所在。

格外重要的是，这个解决问题的函数必须有明确的结束条件，否则就会导致无限递归的情况。总结起来，递归的实现包含了两个部分，一个是递归主体，另一个是终止条件。

二. 递归的算法思想

递归的数学模型其实就是数学归纳法，这个证明方法是我们高中时期解决数列问题最常用的方法。接下来，我们通过一道题目简单回顾一下数学归纳法。
一个常见的题目是：证明当 n 等于任意一个自然数时某命题成立。
当采用数学归纳法时，证明分为以下 2 个步骤：

证明当 n = 1 时命题成立；
假设 n = m 时命题成立，那么尝试推导出在 n = m + 1 时命题也成立。

与数学归纳法类似，当采用递归算法解决问题时，我们也需要围绕这 2 个步骤去做文章：

当你面对一个大规模问题时，如何把它分解为几个小规模的同样的问题；
当你把问题通过多轮分解后，最终的结果，也就是终止条件如何定义。

所以当一个问题同时满足以下 2 个条件时，就可以使用递归的方法求解：

可以拆解为除了数据规模以外，求解思路完全相同的子问题；
存在终止条件。

三. 递归的案例

一. 汉诺塔问题

1. 起源

汉诺塔是一个发源于印度的益智游戏，也叫河内塔。相传它源于印度神话中的大梵天创造的三个金刚柱，一根柱子上叠着上下从小到大64个黄金圆盘。大梵天命令婆罗门将这些圆盘按从小到大的顺序移动到另一根柱子上，其中大圆盘不能放在小圆盘上面。当这64个圆盘移动完的时候，世界就将毁灭。

汉诺塔问题源于印度神话
那么好多人会问64个圆盘移动到底会花多少时间？那么古代印度距离现在已经很远，这64个圆盘还没移动完么？我们来通过计算来看看要完成这个任务到底要多少时间？
我们首先利用数学上的数列知识来看看F(n=1)=1,F(n=2)=3,F(n=3)=7,F(n=4)=15……F(n)=2F(n-1)+1;
我们使用数学归纳法可以得出通项式：F(n)=2^n-1。当n为64时F(n=64)=18446744073709551615。
我们假设移动一次圆盘为一秒，那么一年为31536000秒。那么18446744073709551615/31536000约等于584942417355天，换算成年为5845.54亿年。
目前太阳寿命约为50亿年，太阳的完整寿命大约100亿年。所以我们整个人类文明都等不到移动完整圆盘的那一天。

2. 递归算法思路

我们可以把这个问题抽象为一个数学问题。如下图所示，从左到右有 x、y、z 三根柱子，其中 x 柱子上面有从小叠到大的 n 个圆盘。现要求将 x 柱子上的圆盘移到 z 柱子上去。要求是，每次只能移动一个盘子，且大盘子不能被放在小盘子上面。求移动的步骤。

我们来分析一下这个问题。这是一个大规模的复杂问题，如果要采用递归方法去解决的话，就要先把问题化简。

我们的原问题是，把从小到大的 n 个盘子，从 x 移动到 z。

我们可以将这个大问题拆解为以下 3 个小问题：

把从小到大的 n-1 个盘子，从 x 移动到 y；
接着把最大的一个盘子，从 x 移动到 z；
再把从小到大的 n-1 个盘子，从 y 移动到 z。

首先，我们来判断它是否满足递归的第一个条件。其中，第 1 和第 3 个问题就是汉诺塔问题。这样我们就完成了一次把大问题缩小为完全一样的小规模问题。我们已经定义好了递归体，也就是满足来递归的第一个条件。如下图所示：

接下来我们来看判断它是否满足终止条件。随着递归体不断缩小范围，汉诺塔问题由原来“移动从小到大的 n 个盘子”，缩小为“移动从小到大的 n-1 个盘子”，直到缩小为“移动从小到大的 1 个盘子”。移动从小到大的 1 个盘子，就是移动最小的那个盘子。根据规则可以发现，最小的盘子是可以自由移动的。因此，递归的第二个条件，终止条件，也是满足的。

经过仔细分析可见，汉诺塔问题是完全可以用递归实现的。我们定义汉诺塔的递归函数为 hanio()。这个函数的输入参数包括了：

3 根柱子的标记 x、y、z；
待移动的盘子数量 n。

具体代码如下所示，在代码中，hanio(n, x, y, z)，代表了把 n 个盘子由 x 移动到 z。根据分析，我们知道递归体包含 3 个步骤：

把从小到大的 n-1 个盘子从 x 移动到 y，那么代码就是 hanio(n-1, x, z, y)；
再把最大的一个盘子从 x 移动到 z，那么直接完成一次移动的动作就可以了；
再把从小到大的 n-1 个盘子从 y 移动到 z，那么代码就是 hanio(n-1, y, x, z)。对于终止条件则需要判断 n 的大小。如果 n 等于 1，那么同样直接移动就可以了。

public static void main(String[] args) {
    String x = "x";
    String y = "y";
    String z = "z";
    hanio(3, x, y, z);
}
public void hanio(int n, String x, String y, String z) {
    if (n < 1) {
        System.out.println("汉诺塔的层数不能小于1");
    } else if (n == 1) {
        System.out.println("移动: " + x + " -> " + z);
        return;
    } else {
        hanio(n - 1, x, z, y);
        System.out.println("移动: " + x + " -> " + z);
        hanio(n - 1, y, x, z);
    }
}

我们以 n = 3 为例，执行一下这段代码：
在主函数中，执行了 hanio(3, "x", "y", "z")。我们发现 3 比 1 要大，则进入递归体。分别先后执行了 hanio(2, "x", "z", "y")、"移动: x->z"、hanio(2, "y", "x", "z")。
其中的 hanio(2, "x", "z", "y")，又先后执行了 hanio(1, "x", "y", "z")、"移动: x->y"、hanio(1, "z", "x", "y")。在这里，hanio(1, "x", "y", "z") 的执行结果是 "移动: x->z"，hanio(1, "z", "x", "y")的执行结果是"移动: z->y"。
另一边，hanio(2, "y", "x", "z") 则要先后执行 hanio(1, "y", "z", "x")、"移动: y->z"、hanio(1, "x", "y", "z")。在这里，hanio(1, "y", "z", "x") 的执行结果是"移动: y->x"，hanio(1, "x", "y", "z") 的执行结果是 "移动: x->z"。

最终梳理一下，代码执行的结果：

移动: x->z
移动: x->y
移动: z->y
移动: x->z
移动: y->x
移动: y->z
移动: x->z

二. 斐波那契数列

1. 起源

斐波那契数列起源于意大利数学家莱昂纳多·斐波那契（Leonardo Fibonacci）的作品。这位数学家生活在12世纪末至13世纪初，他的本名是莱昂纳多·比萨诺（Leonardo Pisano），而“斐波那契”实际上是“Filius Bonacci”的缩写，意为“邦纳奇之子”。

斐波那契数列首次被西方世界广泛认识是在斐波那契的著作《计算之书》（Liber Abaci）中，该书出版于1202年。在这本书里，他介绍了一个关于兔子繁殖的问题，这个问题导致了这个著名的数列的产生。

问题大致如下：假设有一对刚出生的兔子，一个月后这对兔子成熟并产下一对新的小兔子，此后每个月都会生一对新的小兔子。同时，新生的小兔子在出生后的第二个月也开始产仔。如果所有的兔子都不死亡，那么问一年之后会有多少对兔子？

解决这个问题的过程中，斐波那契发现了一系列数字：1, 1, 2, 3, 5, 8, 13, 21, 34, … 这个数列中的每个数字都是前两个数字的和。这就是斐波那契数列。

2. 递归算法思路

斐波那契数列：指的是这样一个数列：1、1、2、3、5、8、13、21、34、……。

题目：求该数列中第30个数据的值。

package com.zw.study.algorithm;
import java.util.HashMap;
import java.util.Map;
public class RecursionTest {
    private static int count = 0;   // 统计运算次数
    public static void main(String[] args) {
        int number = getBasicNumber(30);
    }
    // 基础递归算法
    private static int getBasicNumber(int num) {
        count++;
        if (num == 1 || num == 2) {
            return 1;
        }
        return getBasicNumber(num - 1) + getBasicNumber(num - 2);
    }
}

四. 递归算法问题

递归函数的优点是定义简单，逻辑清晰。理论上，所有的递归函数都可以写成循环的方式，但循环的逻辑不如递归清晰。

使用递归函数需要注意防止栈溢出。在计算机中，函数调用是通过栈（stack）这种数据结构实现的，每当进入一个函数调用，栈就会加一层栈帧，每当函数返回，栈就会减一层栈帧。由于栈的大小不是无限的，所以，递归调用的次数过多，会导致栈溢出。

因此对应递归算法的优化，主要就是减少递归调用的次数。

五. 递归算法优化

1.尾递归优化

尾递归优化主要解决递归调用栈溢出的问题，事实上尾递归和循环的效果是一样的，所以，把循环看成是一种特殊的尾递归函数也是可以的。

尾递归是指，在函数返回的时候，调用自身本身，并且，return语句不能包含表达式。这样，编译器或者解释器就可以把尾递归做优化，使递归本身无论调用多少次，都只占用一个栈帧，不会出现栈溢出的情况。

2.记忆模式优化

记忆模式也可以叫备忘录模式，主要思想就是借助临时空间，把已经运算过的结果存储到临时空间中，下一次发现为相同运算时，就不需要再次进行逻辑运算，只需要从临时空间中取出值即可。也是一种典型的以空间换时间的想法。

还是以斐波那契数列为例直接看代码：

package com.zw.study.algorithm;

import java.util.HashMap;
import java.util.Map;

public class RecursionTest {
    private static int count = 0;   // 统计运算次数
    private static Map<Integer, Integer> bookMap = new HashMap<>();   // 用于存储递归计算过的结果

    public static void main(String[] args) {
    
        long startTime = System.nanoTime();
        int number = getBasicNumber(30);
        long endTime = System.nanoTime();
        System.out.println("基础递归共耗时：" + (endTime - startTime) + "纳秒");
        System.out.println("基础递归共调用方法：" + count + "次");
        System.out.println("基础递归第30个数据的值是：" + number);
        System.out.println();

        count = 0;
        startTime = System.nanoTime();
        number = getBookNumber(30);
        endTime = System.nanoTime();
        System.out.println("备忘录递归共耗时：" + (endTime - startTime) + "纳秒");
        System.out.println("备忘录递归共调用方法：" + count + "次");
        System.out.println("备忘录递归第30个数据的值是：" + number);
    }

    // 基础递归算法
    private static int getBasicNumber(int num) {
        count++;
        if (num == 1 || num == 2) {
            return 1;
        }
        return getBasicNumber(num - 1) + getBasicNumber(num - 2);
    }

    // 备忘录算法
    private static int getBookNumber(int num) {
        count++;
        if (num == 1 || num == 2) {
            return 1;
        }
        if (bookMap.containsKey(num)) {
            return bookMap.get(num);
        } else {
            int bookNumber = getBookNumber(num - 1) + getBookNumber(num - 2);
            bookMap.put(num, bookNumber);
            return bookNumber;
        }
    }
}

如上的代码，getBasicNumber为基本递归的操作，getBookNumber是使用了备忘录算法的递归操作。
运算结果如下：