摘要：前言相信大家在面試或者工作中偶爾會遇到遞歸算法的提問或者編程，我們今天來聊一聊從數(shù)學(xué)歸納法到理解遞歸算法。這種廣義的數(shù)學(xué)歸納法應(yīng)用于數(shù)學(xué)邏輯和計算機科學(xué)領(lǐng)域，稱作結(jié)構(gòu)歸納法。

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

相信大家在面試或者工作中偶爾會遇到遞歸算法的提問或者編程，我們今天來聊一聊從數(shù)學(xué)歸納法到理解遞歸算法。如有錯誤還請大家及時指出~

本文已同步至 GitHub/Gitee/公眾號，感興趣的同學(xué)幫忙點波關(guān)注~

來源百度百科

數(shù)學(xué)歸納法（Mathematical Induction, MI）是一種數(shù)學(xué)證明方法，通常被用于證明某個給定命題在整個（或者局部）自然數(shù)范圍內(nèi)成立。除了自然數(shù)以外，廣義上的數(shù)學(xué)歸納法也可以用于證明一般良基結(jié)構(gòu)，例如：集合論中的樹。這種廣義的數(shù)學(xué)歸納法應(yīng)用于數(shù)學(xué)邏輯和計算機科學(xué)領(lǐng)域，稱作結(jié)構(gòu)歸納法。在數(shù)論中，數(shù)學(xué)歸納法是以一種不同的方式來證明任意一個給定的情形都是正確的（第一個,第二個，第三個，一直下去概不例外）的數(shù)學(xué)定理。雖然數(shù)學(xué)歸納法名字中有“歸納”，但是數(shù)學(xué)歸納法并非不嚴(yán)謹(jǐn)?shù)臍w納推理法，它屬于完全嚴(yán)謹(jǐn)?shù)难堇[推理法。事實上，所有數(shù)學(xué)證明都是演繹法。

自然數(shù)是指表示物體個數(shù)的數(shù)，即由0開始，0，1，2，3，4，……一個接一個，組成一個無窮的集體，即指非負(fù)整數(shù)。

簡單了解數(shù)學(xué)歸納法的概念后，我們來看看數(shù)學(xué)歸納法的推演步驟。

我們知道數(shù)學(xué)歸納法用來證明任意一個給定的情形都是正確的，也就是說，第一個，第二個，一直到所有情形，概不例外。

其證明步驟如下：

證明基本情況（通常是N = 1 的時候）是否成立。

證明對于N=1成立。我們只需要先從最小的自然數(shù)開始證明。這一步通常非常簡單。關(guān)鍵是證明第二步。

證明N > 1 時，假設(shè) N - 1 成立，那么對于N成立（N為任意大于1的自然數(shù)）。

這一步并不是直接證明的，而是假設(shè)N-1成立，利用這個結(jié)論推出N是成立的。如果能夠推出的話，就可以說：對于所有的自然數(shù)都成立。因為證明了對1成立，那么對2成立，對3也成立。那么就證明了對所有自然數(shù)都成立。
我們會發(fā)現(xiàn)數(shù)學(xué)歸納法它很合適用來證明，例如常見的等差、等比、以及平方、立方數(shù)列的求和等等。

我們來舉一個小栗子，回顧下我們高中時期所學(xué)的數(shù)學(xué)歸納法是如何進(jìn)行證明。

例子：

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

我們來將上面 1.2 推演步驟 用起來。

第一步： 證明基本情況（通常是N = 1 的時候）是否成立。

我們把N=1同時代入等號左邊和右邊，得

1 = 1*(1+1)/2

成立！

第二步： 證明N > 1 時，假設(shè) N - 1 成立，那么對于N成立（N為任意大于1的自然數(shù)）。

這里我們需要分兩步。

① 假設(shè)對于N-1的情況下成立

我們依然將N-1同時代入等號的左邊和右邊，得：

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

② 將假設(shè)結(jié)論代入，同時加N

我們假設(shè)N-1是成立的，那么我們在等號左邊與右邊同時加N，肯定也是成立的,得：

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

化簡右邊得：n(n+1)/2，那么我們最后證明的結(jié)果就是成立的！

即：1+2+3+...+n = n(n+1)/2 成立。通過以上步驟，我們可以證明這個公式是成立的。

歸納法適用于想解決一個問題轉(zhuǎn)化為解決他的子問題，而他的子問題又變成子問題的子問題，而且我們發(fā)現(xiàn)這些問題其實都是一個模型，也就是說存在相同的邏輯歸納處理項。

接下來我們來看看，我們寫程序和數(shù)學(xué)歸納法的關(guān)聯(lián)。

說起遞歸算法，其實我們每個開發(fā)人員都肯定聽過或者寫過。記得我最開始接觸遞歸算法的時候，還是大一學(xué)習(xí)譚浩強老師寫的那本C語言時，里面介紹了遞歸算法。給我的印象就是：自己調(diào)用自己。后來在工作中，用到的地方也不多，印象中只有一次寫級聯(lián)菜單的時候用到了遞歸算法。（是不是我寫的代碼太水，大家也可以說說哪里用到過遞歸算法）本章就來通過數(shù)學(xué)歸納法來回顧下我們曾經(jīng)學(xué)過的遞歸算法。

遞歸的基本思想:以此類推

具體來講就是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會產(chǎn)生無限遞歸的情況了。仔細(xì)觀察遞歸，就會發(fā)現(xiàn)：遞歸的數(shù)學(xué)模型其實就是歸納法。

我們在使用遞歸的時候需要滿足一些基本條件，如果不滿足的話，就有可能出現(xiàn)無限遞歸，最后會導(dǎo)致堆棧溢出了。

滿足條件：

嚴(yán)格定義遞歸函數(shù)作用，包括參數(shù)，返回值，其他變量。

先一般情況，后特殊情況。

有退出條件。在一般情況下，能讓遞歸正常退出的條件。

每次調(diào)用必須縮小問題規(guī)模，且新問題與原問題有著相同的形式，即規(guī)律。

上面的條件一環(huán)扣一環(huán)，也可以縮減成兩個主要條件：有規(guī)律,有退出條件。我們以上面的條件，來結(jié)合案例進(jìn)行理解。

例題：

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

第一步： 嚴(yán)格定義遞歸函數(shù)作用，包括參數(shù)，返回值，其他變量。

我們初看題目，可以知道這是一個簡單的求和，即從1開始：1+2+3+...一直加到n。所以我們可以定義一個入?yún)閚,返回值類型為int的一個方法，既然是遞歸求和，我們的方法名就叫recursionSum。

public static int recursionSum(int n) { //為了方便調(diào)用，我用了static
    
    return 0;
}

System.out.println("公眾號：Coder編程：" + recursionSum(0));

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

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

我們先用一般的情況進(jìn)行求和計算，例如代入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));

第三步： 有退出條件。在一般情況下，能讓遞歸正常退出的條件。

其實，我們做完第二步，就會發(fā)現(xiàn)已經(jīng)把第三步做完了。即有了讓遞歸正常退出的條件！

第四步： 每次調(diào)用必須縮小問題規(guī)模，且新問題與原問題有著相同的形式，即規(guī)律。

這一步是最關(guān)鍵的，也是最核心的！我們需要找到其規(guī)律，并且能縮小問題的規(guī)模。我們會發(fā)現(xiàn)，當(dāng)我們需要求第N個數(shù)的和的時候，我們必須知道前N-1個數(shù)的和，即 sum(N-1)。前N個數(shù)的和就是sum(N-1)+N。找到這個規(guī)律后，我們就可以定義一個臨時變量sum來接收前N個數(shù)的和了。

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個數(shù)的和" + recursionSum(5));

輸出結(jié)果：15

我們優(yōu)化一下：

public static int recursionSum(int n) {

    if (n < 0){
       throw new Exception("參數(shù)不能為負(fù)！");
    }
    if(n == 1) {
        return 1;
    }
    
    return recursionSum(n-1)+n;
}

System.out.println("公眾號：Coder編程：前5個數(shù)的和" + recursionSum(5));

是不是突然發(fā)現(xiàn)遞歸其實也沒想的那么難？

接下來我們難度進(jìn)行升級！看大家能不能都理解了。我就不像上面求和那么啰嗦了！

2.3.2.1 求階乘

例題：求n的階乘（n>1，n是正整數(shù)）

階乘的遞推公式為：factorial(n)=n*factorial(n-1)，其中n為非負(fù)整數(shù),且0!=1,1!=1
這里就不做過多說明，跟求后過程一致，可以模仿求和的過程，大家可以先自己嘗試寫下，下面我直接貼代碼了：

public static int factorial(int n) throws Exception {
    if (n < 0){
        throw new Exception("參數(shù)不能為負(fù)！");
    }else if (n == 1 || n == 0) {
        return 1;
    }else {
        return n * factorial(n - 1);
    }
}

System.out.println("公眾號：Coder編程：3的階乘:" + factorial(3));

輸出結(jié)果： 公眾號：Coder編程：3的階乘:6

2.3.2.2 斐波那契數(shù)列

斐波那契數(shù)列 我想大家同樣熟悉了解，下面我們繼續(xù)回顧一下斐波那契數(shù)列到底是什么？

斐波那契數(shù)列: 1、1、2、3、5、8、13、21.....

可以看出從第三位起：第三項等于前兩項之和?？偨Y(jié)遞推公式：:Fib(n)=Fib(n-1)+Fib(n-2)。所以我們可以將前兩位作為退出遞歸的條件。即：if(n==1) retrun 1 if(n==2) return 1

因此我們可以直接用公式（規(guī)律）和退出條件，寫出編程代碼：

public static int fib(int n) throws Exception {
    if (n < 0) {
        throw new Exception("參數(shù)不能為負(fù)！");
    }else if (n == 0 || n == 1){
        return n;
    }else {
        return fib(n - 1) + fib(n - 2);
    }
}

System.out.println("公眾號：Coder編程：斐波那契數(shù)列:" + fib(3));

2.3.2.3 漢諾塔問題

相傳在古印度圣廟中，有一種被稱為漢諾塔(Hanoi)的游戲。該游戲是在一塊銅板裝置上，有三根桿(編號A、B、C)，在A桿自下而上、由大到小按順序放置不同個數(shù)的金盤(如下圖)。

游戲的目標(biāo)：把A桿上的金盤全部移到C桿上，并仍保持原有順序疊好。

操作規(guī)則：每次只能移動一個盤子，并且在移動過程中三根桿上都始終保持大盤在下，小盤在上，操作過程中盤子可以置于A、B、C任一桿上。

在總結(jié)規(guī)律和寫代碼之前，我們先來玩幾把簡單的（先一般后特殊）：

注：我們以數(shù)字的大小作為盤子的大小。

一個盤子的情況：

1.1 將A柱子的1號盤子直接移動到C柱子中。
1.2 結(jié)束。

兩個盤子的情況：

2.1 將A柱子的1號盤子移動到B柱子。
2.2 將A柱子的2號盤子移動到C柱子。
2.3 將B柱子的1號盤子移動到C柱子。
2.4 結(jié)束。

三個盤子的情況：

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 結(jié)束。

我們會發(fā)現(xiàn)，隨著盤子數(shù)量的增加，盤子移動的難度也開始加大。

這時候不要害怕，我們回過頭再來看這個問題：當(dāng)盤子的數(shù)量是4個、5個...N個的時候，我們該如何解決呢？我們是不是可以用數(shù)學(xué)歸納法的思想或者遞歸的思想去解決呢？答案是：肯定的。這時候我們需要去找到他們的規(guī)律在哪？

我們再觀察下上面在一般情況下移動盤子的規(guī)律在哪？

1.當(dāng)只有一個盤子的時候，可以將盤子直接移動到目標(biāo)柱子C中。即退出條件。

2.當(dāng)只有兩個盤子的時候，我們只需要將B柱子作為中介，將盤子1先放到中介柱子B上，然后將盤子2放到目標(biāo)柱子C上，最后將中介柱子B上的盤子放到目標(biāo)柱子C上即可。

第二點可以看成：當(dāng)我們有N個盤子的時候，第N個盤子看成一個盤子，(N-1)個盤子看做成一個盤子。需要將(N-1)個盤子放在中介柱子B上，N個盤子放在目標(biāo)柱子C即可。即規(guī)律。

當(dāng)我們有三個盤子的時候，我們會發(fā)現(xiàn)一個問題： 角色變化

將A塔座的第(N-1)~1個盤子看成是一個盤子，放到中柱子B上，然后將第N個盤子放到目標(biāo)柱子C上。這時候柱子A空了!柱子A成為中介柱子，柱子B成為起始柱子。

柱子B這時候有N-1個盤子，將第(N-2)~1個盤子看成是一個盤子，放到中介柱子A上，然后將柱子B的第(N-1)號盤子放到目標(biāo)柱子C上。這時候柱子B空了!柱子B又成為了中介柱子，A成為了起始柱子!

重復(fù)1、2步驟，直到所有盤子都放到目標(biāo)塔座C上結(jié)束。

總結(jié)一下：

從初始柱子A上移動包含n-1個盤子到中介柱子B上。

將初始柱子A上剩余的一個盤子（最大的一個盤子）放到目標(biāo)柱子C上。

將中介柱子B上n-1個盤子移動到目標(biāo)柱子C上。

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

/**
 * 漢諾塔問題
 * @param dish 盤子個數(shù)(也表示名稱)
 * @param from 初始柱子
 * @param temp 中介柱子
 * @param to   目標(biāo)柱子
 */
public static void move(int dish,String from,String temp,String to){
    if(dish == 1){
        System.out.println("將盤子"+dish+"從柱子"+from+"移動到目標(biāo)柱子"+to);
    }else{
        move(dish-1,from,to,temp);//A為初始柱子，B為目標(biāo)柱子，C為中介柱子
        System.out.println("將盤子"+dish+"從柱子"+from+"移動到目標(biāo)柱子"+to);
        move(dish-1,temp,from,to);//B為初始柱子，C為目標(biāo)柱子，A為中介柱子
    }
}

move(dish-1,from,to,temp);//A為初始柱子，B為目標(biāo)柱子，C為中介柱子

這里需要將n-1之前的盤子都放到B柱子上，最后第n個盤子放到C柱子。

move(dish-1,temp,from,to);//B為初始柱子，C為目標(biāo)柱子，A為中介柱子

這時候B變?yōu)榱顺跏贾?，A成為了目標(biāo)柱子。將之前n-1個盤子放到C目標(biāo)柱子中。

打印結(jié)果：

本章節(jié)主要簡單介紹了數(shù)學(xué)歸納法與遞歸算法的一些思想。希望對大家有所幫助！
今后我會在每張文章開頭增加 每章一點正能量 ，文末增加5個編程相關(guān)的英語單詞 學(xué)點英語。希望大家和我一樣每天都能積極向上，一起學(xué)習(xí)一同進(jìn)步！

JRE Java Runtime Environment（Java運行環(huán)境），運行 JAVA程序所必須的環(huán)境的集合，包含JVM標(biāo)準(zhǔn)實現(xiàn)及Java核心類庫。

JSDK Java Software Development Kit，和JDK以及J2SE 等同。

JDK Java Development Kit(Java開發(fā)工具包):包括運行環(huán)境 、編譯工具及其它工具、源代碼等，基本上和J2SE等同。

J2ME Java 2 Micro Edition（JAVA2精簡版）API規(guī)格基 于J2SE ，但是被修改為可以適合某種產(chǎn)品的單一要求。J2ME使JAVA程序可以很方便的應(yīng)用于電話卡、尋呼機等小型設(shè)備，它包括兩種類型的組件，即配置 （configuration）和描述（profile）。

歡迎關(guān)注公眾號：Coder編程
獲取最新原創(chuàng)技術(shù)文章和相關(guān)免費學(xué)習(xí)資料，隨時隨地學(xué)習(xí)技術(shù)知識！

參考文章：

https://www.cnblogs.com/ysoce...

http://www.nowamagic.net/libr...

一篇帶你讀懂TCP之“滑動窗口”協(xié)議

帶你了解數(shù)據(jù)庫中JOIN的用法

深入淺出了解“裝箱與拆箱”