从“数学归纳法”到理解“递归算法”！

关注我

从“数学归纳法”到理解“递归算法”！

每章一点正能量：人的一生可能燃烧也可能腐朽。

前言

相信大家在面试或者工作中偶尔会遇到递归算法的提问或者编程，我们今天来聊一聊从数学归纳法到理解递归算法。如有错误还请大家及时指出~

本文已同步至 GitHub/Gitee/公众号，感兴趣的同学帮忙点波关注~

1. 数学归纳法

1.1 简介

来源百度百科

数学归纳法（Mathematical Induction, MI）是一种数学证明方法，通常被用于证明某个给定命题在整个（或者局部）自然数范围内成立。除了自然数以外，广义上的数学归纳法也可以用于证明一般良基结构，例如：集合论中的树。这种广义的数学归纳法应用于数学逻辑和计算机科学领域，称作结构归纳法。在数论中，数学归纳法是以一种不同的方式来证明任意一个给定的情形都是正确的（第一个,第二个，第三个，一直下去概不例外）的数学定理。虽然数学归纳法名字中有“归纳”，但是数学归纳法并非不严谨的归纳推理法，它属于完全严谨的演绎推理法。事实上，所有数学证明都是演绎法。

自然数是指表示物体个数的数，即由0开始，0，1，2，3，4，……一个接一个，组成一个无穷的集体，即指非负整数。

1.2 推演步骤

简单了解数学归纳法的概念后，我们来看看数学归纳法的推演步骤。

我们知道数学归纳法用来证明任意一个给定的情形都是正确的，也就是说，第一个，第二个，一直到所有情形，概不例外。

其证明步骤如下：

证明基本情况（通常是N = 1 的时候）是否成立。
证明对于N=1成立。我们只需要先从最小的自然数开始证明。这一步通常非常简单。关键是证明第二步。
证明N > 1 时，假设 N - 1 成立，那么对于N成立（N为任意大于1的自然数）。
这一步并不是直接证明的，而是假设N-1成立，利用这个结论推出N是成立的。如果能够推出的话，就可以说：对于所有的自然数都成立。因为证明了对1成立，那么对2成立，对3也成立。那么就证明了对所有自然数都成立。
我们会发现数学归纳法它很合适用来证明，例如常见的等差、等比、以及平方、立方数列的求和等等。

1.3 小栗子

我们来举一个小栗子，回顾下我们高中时期所学的数学归纳法是如何进行证明。

例子：


证明： 1+2+3+...+n = n(n+1)/2

我们来将上面 1.2 推演步骤 用起来。

第一步：证明基本情况（通常是N = 1 的时候）是否成立。

我们把N=1同时代入等号左边和右边，得


1 = 1*(1+1)/2

成立！

第二步：证明N > 1 时，假设 N - 1 成立，那么对于N成立（N为任意大于1的自然数）。

这里我们需要分两步。

① 假设对于N-1的情况下成立

我们依然将N-1同时代入等号的左边和右边，得：


1+2+3+...+(n-1) = (n-1)n/2

② 将假设结论代入，同时加N

我们假设N-1是成立的，那么我们在等号左边与右边同时加N，肯定也是成立的,得：


 1+2+3...+(n-1)+n = (n-1)n/2+n

化简右边得：n(n+1)/2，那么我们最后证明的结果就是成立的！

即：1+2+3+...+n = n(n+1)/2 成立。通过以上步骤，我们可以证明这个公式是成立的。

1.4 小结

归纳法适用于想解决一个问题转化为解决他的子问题，而他的子问题又变成子问题的子问题，而且我们发现这些问题其实都是一个模型，也就是说存在相同的逻辑归纳处理项。

接下来我们来看看，我们写程序和数学归纳法的关联。

2. 递归

说起递归算法，其实我们每个开发人员都肯定听过或者写过。记得我最开始接触递归算法的时候，还是大一学习谭浩强老师写的那本C语言时，里面介绍了递归算法。给我的印象就是：自己调用自己。后来在工作中，用到的地方也不多，印象中只有一次写级联菜单的时候用到了递归算法。（是不是我写的代码太水，大家也可以说说哪里用到过递归算法）本章就来通过数学归纳法来回顾下我们曾经学过的递归算法。

2.1 理解递归

递归的基本思想:以此类推

具体来讲就是把规模大的问题转化为规模小的相似的子问题来解决。在函数实现时，因为解决大问题的方法和解决小问题的方法往往是同一个方法，所以就产生了函数调用它自身的情况。另外这个解决问题的函数必须有明显的结束条件，这样就不会产生无限递归的情况了。仔细观察递归，就会发现：递归的数学模型其实就是归纳法。

2.2 递归条件

我们在使用递归的时候需要满足一些基本条件，如果不满足的话，就有可能出现无限递归，最后会导致堆栈溢出了。

满足条件：

严格定义递归函数作用，包括参数，返回值，其他变量。
先一般情况，后特殊情况。
有退出条件。在一般情况下，能让递归正常退出的条件。
每次调用必须缩小问题规模，且新问题与原问题有着相同的形式，即规律。

上面的条件一环扣一环，也可以缩减成两个主要条件：有规律,有退出条件。我们以上面的条件，来结合案例进行理解。

2.3 小栗子

2.3.1 递归求和

例题：


1+2+3+...+n=?

第一步： 严格定义递归函数作用，包括参数，返回值，其他变量。

我们初看题目，可以知道这是一个简单的求和，即从1开始：1+2+3+...一直加到n。所以我们可以定义一个入参为n,返回值类型为int的一个方法，既然是递归求和，我们的方法名就叫recursionSum。


public static int recursionSum(int n) { //为了方便调用，我用了static
    
    return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(0));

那么我们第一步就做完了。

第二步： 先一般情况，后特殊情况。

我们先用一般的情况进行求和计算，例如代入1,2,3这样的一般情况。即：


public static int recursionSum(int n) { 
    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return 1+2;
    }
    
    if(n == 3) {
        return 1+2+3;
    }
    return 0;
}

System.out.println("公众号：Coder编程：" + recursionSum(3));

第三步： 有退出条件。在一般情况下，能让递归正常退出的条件。

其实，我们做完第二步，就会发现已经把第三步做完了。即有了让递归正常退出的条件！

第四步： 每次调用必须缩小问题规模，且新问题与原问题有着相同的形式，即规律。

这一步是最关键的，也是最核心的！我们需要找到其规律，并且能缩小问题的规模。我们会发现，当我们需要求第N个数的和的时候，我们必须知道前N-1个数的和，即 sum(N-1)。前N个数的和就是sum(N-1)+N。找到这个规律后，我们就可以定义一个临时变量sum来接收前N个数的和了。


public static int recursionSum(int n) {

    if(n == 1) {
        return 1;
    }
    
    if(n == 2) {
        return 1+2;
    }
    
    if(n == 3) {
        return 1+2+3;
    }
    
    int sum = recursionSum(n-1)+n;
    return sum;
}

System.out.println("公众号：Coder编程：前5个数的和" + recursionSum(5));

输出结果：15

我们优化一下：


public static int recursionSum(int n) {

    if (n < 0){
       throw new Exception("参数不能为负！");
    }
    if(n == 1) {
        return 1;
    }
    
    return recursionSum(n-1)+n;
}

System.out.println("公众号：Coder编程：前5个数的和" + recursionSum(5));

是不是突然发现递归其实也没想的那么难？

2.3.2 举一反三？

接下来我们难度进行升级！看大家能不能都理解了。我就不像上面求和那么啰嗦了！

2.3.2.1 求阶乘

例题：求n的阶乘（n>1，n是正整数）

阶乘的递推公式为：factorial(n)=n*factorial(n-1)，其中n为非负整数,且0!=1,1!=1
这里就不做过多说明，跟求后过程一致，可以模仿求和的过程，大家可以先自己尝试写下，下面我直接贴代码了：


public static int factorial(int n) throws Exception {
    if (n < 0){
        throw new Exception("参数不能为负！");
    }else if (n == 1 || n == 0) {
        return 1;
    }else {
        return n * factorial(n - 1);
    }
}

System.out.println("公众号：Coder编程：3的阶乘:" + factorial(3));

输出结果：公众号：Coder编程：3的阶乘:6

2.3.2.2 斐波那契数列

斐波那契数列 我想大家同样熟悉了解，下面我们继续回顾一下斐波那契数列到底是什么？

斐波那契数列图

斐波那契数列: 1、1、2、3、5、8、13、21.....

可以看出从第三位起：第三项等于前两项之和。总结递推公式：:Fib(n)=Fib(n-1)+Fib(n-2)。所以我们可以将前两位作为退出递归的条件。即：if(n==1) retrun 1 if(n==2) return 1

因此我们可以直接用公式（规律）和退出条件，写出编程代码：


public static int fib(int n) throws Exception {
    if (n < 0) {
        throw new Exception("参数不能为负！");
    }else if (n == 0 || n == 1){
        return n;
    }else {
        return fib(n - 1) + fib(n - 2);
    }
}

System.out.println("公众号：Coder编程：斐波那契数列:" + fib(3));

2.3.2.3 汉诺塔问题

相传在古印度圣庙中，有一种被称为汉诺塔(Hanoi)的游戏。该游戏是在一块铜板装置上，有三根杆(编号A、B、C)，在A杆自下而上、由大到小按顺序放置不同个数的金盘(如下图)。

游戏的目标：把A杆上的金盘全部移到C杆上，并仍保持原有顺序叠好。

操作规则：每次只能移动一个盘子，并且在移动过程中三根杆上都始终保持大盘在下，小盘在上，操作过程中盘子可以置于A、B、C任一杆上。

汉诺塔图

在总结规律和写代码之前，我们先来玩几把简单的（先一般后特殊）：

注：我们以数字的大小作为盘子的大小。

一个盘子的情况：

1.1 将A柱子的1号盘子直接移动到C柱子中。
1.2 结束。

两个盘子的情况：

2.1 将A柱子的1号盘子移动到B柱子。
2.2 将A柱子的2号盘子移动到C柱子。
2.3 将B柱子的1号盘子移动到C柱子。
2.4 结束。
三个盘子的情况：

3.1 将A柱子的1号盘子移动到C柱子。
3.2 将A柱子的2号盘子移动到B柱子。
3.3 将C柱子的1号盘子移动到B柱子。
3.4 将A柱子的3号盘子移动到C柱子。
3.5 将B柱子的1号盘子移动到A柱子。
3.6 将B柱子的2号盘子移动到C柱子。
3.7 将A柱子的1号盘子移动到C柱子。
3.8 结束。

我们会发现，随着盘子数量的增加，盘子移动的难度也开始加大。

这时候不要害怕，我们回过头再来看这个问题：当盘子的数量是4个、5个...N个的时候，我们该如何解决呢？我们是不是可以用数学归纳法的思想或者递归的思想去解决呢？答案是：肯定的。这时候我们需要去找到他们的规律在哪？

我们再观察下上面在一般情况下移动盘子的规律在哪？

1.当只有一个盘子的时候，可以将盘子直接移动到目标柱子C中。即退出条件。
2.当只有两个盘子的时候，我们只需要将B柱子作为中介，将盘子1先放到中介柱子B上，然后将盘子2放到目标柱子C上，最后将中介柱子B上的盘子放到目标柱子C上即可。

第二点可以看成：当我们有N个盘子的时候，第N个盘子看成一个盘子，(N-1)个盘子看做成一个盘子。需要将(N-1)个盘子放在中介柱子B上，N个盘子放在目标柱子C即可。即规律。

当我们有三个盘子的时候，我们会发现一个问题： 角色变化

将A塔座的第(N-1)~1个盘子看成是一个盘子，放到中柱子B上，然后将第N个盘子放到目标柱子C上。这时候柱子A空了!柱子A成为中介柱子，柱子B成为起始柱子。
柱子B这时候有N-1个盘子，将第(N-2)~1个盘子看成是一个盘子，放到中介柱子A上，然后将柱子B的第(N-1)号盘子放到目标柱子C上。这时候柱子B空了!柱子B又成为了中介柱子，A成为了起始柱子!

重复1、2步骤，直到所有盘子都放到目标塔座C上结束。

总结一下：

从初始柱子A上移动包含n-1个盘子到中介柱子B上。
将初始柱子A上剩余的一个盘子（最大的一个盘子）放到目标柱子C上。
将中介柱子B上n-1个盘子移动到目标柱子C上。


move(3,"A","B","C");

/**
 * 汉诺塔问题
 * @param dish 盘子个数(也表示名称)
 * @param from 初始柱子
 * @param temp 中介柱子
 * @param to   目标柱子
 */
public static void move(int dish,String from,String temp,String to){
    if(dish == 1){
        System.out.println("将盘子"+dish+"从柱子"+from+"移动到目标柱子"+to);
    }else{
        move(dish-1,from,to,temp);//A为初始柱子，B为目标柱子，C为中介柱子
        System.out.println("将盘子"+dish+"从柱子"+from+"移动到目标柱子"+to);
        move(dish-1,temp,from,to);//B为初始柱子，C为目标柱子，A为中介柱子
    }
}

move(dish-1,from,to,temp);//A为初始柱子，B为目标柱子，C为中介柱子
这里需要将n-1之前的盘子都放到B柱子上，最后第n个盘子放到C柱子。
move(dish-1,temp,from,to);//B为初始柱子，C为目标柱子，A为中介柱子
这时候B变为了初始柱子，A成为了目标柱子。将之前n-1个盘子放到C目标柱子中。

打印结果：

打印结果

文末

本章节主要简单介绍了数学归纳法与递归算法的一些思想。希望对大家有所帮助！
今后我会在每张文章开头增加 每章一点正能量 ，文末增加5个编程相关的英语单词 学点英语。希望大家和我一样每天都能积极向上，一起学习一同进步！

学点英语

JRE Java Runtime Environment（Java运行环境），运行 JAVA程序所必须的环境的集合，包含JVM标准实现及Java核心类库。
JSDK Java Software Development Kit，和JDK以及J2SE 等同。
JDK Java Development Kit(Java开发工具包):包括运行环境、编译工具及其它工具、源代码等，基本上和J2SE等同。
J2ME Java 2 Micro Edition（JAVA2精简版）API规格基于J2SE ，但是被修改为可以适合某种产品的单一要求。J2ME使JAVA程序可以很方便的应用于电话卡、寻呼机等小型设备，它包括两种类型的组件，即配置（configuration）和描述（profile）。

欢迎关注公众号：Coder编程
获取最新原创技术文章和相关免费学习资料，随时随地学习技术知识！

参考文章：

https://www.cnblogs.com/ysocean/p/8005694.html

http://www.nowamagic.net/librarys/veda/detail/2314

微信公众号

从“数学归纳法”到理解“递归算法”！

从“数学归纳法”到理解“递归算法”！

前言

1. 数学归纳法

1.1 简介

1.2 推演步骤

1.3 小栗子

1.4 小结

2. 递归

2.1 理解递归

2.2 递归条件

2.3 小栗子

2.3.1 递归求和

2.3.2 举一反三？

2.3.2.1 求阶乘

2.3.2.2 斐波那契数列

2.3.2.3 汉诺塔问题

文末

学点英语

推荐阅读

推荐阅读更多精彩内容