目錄

一、遞回是什么？

二、如何理解“遞回”？

1、遞回定義

2、遞回需要滿足的三個條件

3、遞回函式

三、怎么玩轉遞回

1、大招：遞回“三段論式”設計經驗

2、練習策略

四、精選練習題講解

1、求n的階乘

三段論：

代碼執行

2、遞回求1+2+...+10

三段論

代碼執行

3、回傳各位數字之和

三段論

代碼執行

4、按順序列印整數i~j

三段論

代碼執行

5、對陣列arr所有元素求和

三段論

代碼執行

五、思考題

六、藍橋結語：遇見藍橋遇見你，不負代碼不負卿

歡迎回到：遇見藍橋遇見你，不負代碼不負卿！

【宣告】：為了讓更多的鐵汁理解遞回，筆者在前面的引入部分贅述可能過長，請鐵汁們多點耐心哦，后面有大招，

【前言】：很多人都認為“遞回”是語言學習中最難理解的內容之一，當然筆者也是這么認為的，哈哈，但是既然筆者已經將文章發布出來了，自然是有了充分的準備，所以，鐵汁們不用緊張，看到最后你會發現，遞回其實是一個很自然的東西，

一、遞回是什么？

遞回是一種應用非常廣泛的演算法（或者編程技巧），之后我們要講的很多資料結構和演算法的編碼實作都要用到遞回，比如 DFS 深度優先搜索、前中后序二叉樹遍歷等等，所以，搞懂遞回非常重要，否則，后面復雜一些的資料結構和演算法學起來就會比較吃力，
不過，別看我說了這么多，遞回本身可是一點兒都不“高冷”，咱們生活中就有很多用到遞回的例子，說一個筆者小時候經常聽到的故事：從前有座山，山上有座廟，廟里有個老和尚在講故事，講的什么呢，從前有座山...哈哈，這不就是遞回嗎，只不過是一個無限遞回，原因是沒有設定終止條件，

舉個栗子：周末你帶著女朋友去電影院看電影，女朋友問你，咱們現在坐在第幾排啊？電影院里面太黑了，看不清，沒法數，現在你怎么辦？
別忘了你是程式員，這個可難不倒你，遞回就開始派上用場了，于是你就問前面一排的人他是第幾排，你想只要在他的數字上加一，就知道自己在哪一排了，但是，前面的人也看不清啊，所以他也問他前面的人，就這樣一排一排往前問，直到問到第一排的人，說他在第一排，然后再這樣一排一排再把數字傳回來，直到你前面的人告訴你他自己在哪一排，于是你就知道答案了，
這就是一個非常標準的遞回求解問題的分解程序，去的程序叫“遞”，回來的程序叫“歸”，基本上，所有的遞回問題都可以用遞推公式來表示，剛剛這個生活中的例子，我們用遞推公式將它表示出來就是這樣的：
f(n) = f(n-1) + 1 其中，f(1)=1
f(n) 表示你想知道自己在哪一排，f(n-1) 表示前面一排所在的排數，f(1)=1 表示第一排的人知道自己在第一排，

二、如何理解“遞回”？

1、遞回定義

劉汝佳老師的關于演算法競賽入門經典（紫書）中是這么定義的：

遞回：參見“遞回”

什么？這個定義什么也沒有說啊！好吧，改一下：

遞回：如果還是沒有明白遞回是什么意思，參見“遞回”，

奧，也許這次你明白了，原來遞回就是自己用到自己的意思，這個定義顯然比上一個好些，因為當你終于悟出其中到道理后，就不用繼續“參見”下去了，事實上，遞回的含義比這個要廣泛，

A經理：“這事不歸我管，去找B經理，” 于是你去找B經理，

B經理：“這事不歸我管，去找A經理，”于是你又回到了A經理這兒，

接下來發生的事就不難想到了，只要兩個經理的說辭不變，你有始終聽話，你將會永遠往返于兩個經理之間，這叫做“無限遞回”，盡管在這里，A經理并沒有讓你找他自己，但還是回到了他這兒，換句話說，“間接用到了自己” 也算遞回，

回憶一下，在小學的時候，正整數是如何定義的？正整數1,2,3......這些數，這樣的定義也許對于小學生來說是沒有任何問題的，但當你覺得這樣定義“不太嚴密”時，你或許會喜歡這樣的定義：

（1）1是正整數，

（2）如果n是正整數，那么n + 1也是正整數，

（3）只有通過（1）、（2）定義出來的才是正整數，（這里犧牲一點嚴密性，換來的是更通俗易懂的表達方式）

這樣的定義為什么說成是遞回呢，因為在“正整數“還沒有定義完時，就用到了”正整數”的定義，其實這和前面“參見遞回”在本質上是相同的，只是沒有它那么直接和明顯，

2、遞回需要滿足的三個條件

究竟什么樣的問題可以用遞回來解決呢？我總結了三個條件，只要同時滿足以下三個條件，就可以用遞回來解決，
1. 一個問題的解可以分解為幾個子問題的解
何為子問題？子問題就是資料規模更小的問題，比如，前面講的電影院的例子，你要知道，“自己在哪一排”的問題，可以分解為“前一排的人在哪一排”這樣一個子問題，
2. 這個問題與分解之后的子問題，除了資料規模不同，求解思路完全一樣
比如電影院那個例子，你求解“自己在哪一排”的思路，和前面一排人求解“自己在哪一排”的思路，是一模一樣的，
3. 存在遞回終止條件
把問題分解為子問題，把子問題再分解為子子問題，一層一層分解下去，不能存在無限回圈，這就需要有終止條件，

3、遞回函式

數學函式也可以遞回定義，例如，階乘函式f(x) = n! 用遞回法撰寫程式實作如下：

#include<stdio.h>

int factor(int n)
{
	if (n == 1)
	{
		return 1;
	}
	return n * factor(n - 1);
}

int main()
{
	int n = 5;

	int ret = factor(n);

	printf("%d\n", ret);

	return 0;
}

注意：本題就是簡單了解一下用遞回寫程式是什么樣，重點講解放在后面，

提示：C語言支持遞回，即函式可以直接或者間接的呼叫自己，但是要格外注意為遞回函式撰寫終止條件，否則將產生無限回圈，

總結一下：寫遞回代碼的關鍵就是找到如何將大問題分解為小問題的規律，并且基于此寫出遞推公式，然后再推敲終止條件，最后將遞推公式和終止條件翻譯成代碼，

雖然我講了這么多方法，但是作為初學者，現在是不是還是有種想不太清楚的感覺呢？這也是文章開頭我說遞回代碼比較難理解的原因所在，那怎么辦呢，請繼續看...

三、怎么玩轉遞回

在重復中找變化，在變化中找重復！

1、大招：遞回“三段論式”設計經驗

• 找重復-->找子問題
• 找變化-->找重復中的變化量作為引數
• 找邊界-->找引數變化趨勢設計出口

注意：

1. 對于遞回這種折磨人的知識，有人兩三天就會了，有人三五年也不會，主要看你悟不悟得透，能不能找到對于遞回的感覺，
2. 三段論中的找重復，這個步驟是最重要而且還是最需要感覺的，不過你要相信Practice makes prefect！踏踏實實，多做，多練，多敲，
3. 在找邊界設計出口時，最好寫在函式的開頭，

2、練習策略

• 回圈改遞回解題
• 經典遞回講解
• 大量練習，總結規律，掌握套路
• 找到感覺，挑戰高難度

四、精選練習題講解

1、求n的階乘

注意：為了方便大家伙的理解，本題沒有考慮n == 0的情況

三段論：

1. 找重復：n * (n - 1)的階乘，求(n - 1)的階乘是原問題的重復，規模更小，是原問題的子問題，
2. 找變化：找重復中的變化的量作為引數，本題中很明顯是n在變化，所以函式定義程序中的形參是n.
3. 找邊界：也就是出口的判斷，什么時候讓函式停止，顯然本題中當n == 1時結束，

代碼執行

#include<stdio.h>

//本題中的變化量是n，所以用作形式引數
int factor(int n)
{
	//出口的判斷，最好寫在函式的開頭，本題中當n == 1時就意味著到邊界了，應該終止程式
	if (n == 1)
	{
		return 1;
	}
	//(n - 1)的階乘是原問題的重復，是其子問題，規模更小
	return n * factor(n - 1);
}

int main()
{
	int n = 5;

	int ret = factor(5);

	printf("%d\n", ret);

	return 0;
}

注意：為了言簡意賅，本題中沒有考慮n == 0的情況，可能看到這里你還是不能完全理解遞回，那么我們應該先理解清楚“上面函式的執行程序”，尤其是，函式執行結束之后，回到呼叫位置繼續往下執行，

注意：建議上面的執行程序，請鐵汁們在下面的練習中每一個都畫出來，這樣你才能清楚地體會到“函式的執行程序”，明白遞回的奧秘，

如果仍然無法理解上面的遞回，可以作如下比喻，

皇帝（擁有main函式堆疊幀的男人）：宰相，你給我算一下f(5)，

宰相（擁有f(5)堆疊幀的男人）：大臣，你給我算一下f(4)，

大臣（擁有f(4)堆疊幀的男人）：知府，你給我算一下f(3)，

知府（擁有f(3)堆疊幀的男人）：縣令，你給我算一下f(2)，

縣令（擁有f(2)堆疊幀的男人）：師爺，你給我算一下f(1)，

師爺（擁有f(1)堆疊幀的男人）：回老爺，f(1) = 1，

縣令（心算f(2) = 2 * f(1) = 2）回知府大人，f(2) = 2，

知府（心算f(3) = 3 * f(2) = 6）回大人，f(3) = 6，

大臣（心算f(4) = 4 * f(3) = 24）回宰相大人，f(4) = 24，

宰相（心算f(5) = 5 * f(4) = 120）回陛下，f(5) = 120，

皇帝滿意極了，

雖然這個比喻不甚恰當，但也可以說明一些問題，函式呼叫時新建了一個堆疊幀，并且跳轉到了函式的開頭去執行，就好比皇帝找宰相、宰相找大臣這樣的程序，盡管同一時刻可以有多個堆疊幀（皇帝、宰相、大臣、縣令同時處于“等待下級回話”的狀態），但是當前代碼行只有一個，

鐵汁們如果理解了這個比喻，但是不理解呼叫堆疊，沒關系，它不是本文重點 ，在后面系列的博文中筆者會做詳細介紹，你只需要知道遞回為什么能正常作業即可，設計遞回程式的重點在于上級給下級安排作業，

此時此刻，是補充第一種解題思維——“切蛋糕思維”，最好的時機

如果一時不是很明白，沒有關系，后面還有大量的練習讓鐵汁們體會這個思維的美妙，

2、遞回求1+2+...+10

三段論

找重復：求1~(num - 1)是原問題的重復，規模更小，是原題的子問題

找變化：很顯然，num是不斷變化的，所以函式的形參是num

找邊界：num == 1是函式的邊界

代碼執行

//遞回求1+2+3+...+10
#include<stdio.h>
//很顯然num是不斷變化的，所以用作函式的形參
int sum(int num)
{
	//找邊界
	if (num == 1)
	{
		return 1;
	}
	//1~(num - 1)是原問題的重復，規模更小，是原問題的子問題
	return num + sum(num - 1);
}

int main()
{
	int n = 10;

	int ret = sum(n);

	printf("%d\n", ret);

	return 0;
}

3、回傳各位數字之和

題目描述：輸入一個非負整數，回傳組成它的數字之和，如輸入1729，應該回傳1+7+2+9的值，當然1+7+2+9 == 9+2+7+1，也就是19

三段論

找重復：求（num / 10）組成它的數字之和是原問題的重復，規模更小，是其子問題

找變化：num一直在變化

找邊界：num < 10

代碼執行

#include<stdio.h>
int sum(int num)
{
	if (num < 10)
	{
		return num;
	}
	return num % 10 + sum(num / 10);
}

int main()
{
	int num = 1729;
	
	printf("%d\n", sum(num));

	return 0;
}

4、按順序列印整數i~j

三段論

找重復：（i + 1）是原問題的重復，規模更小，是其子問題

找變化：i 和 j，i在變化不難看出，但為什么要加上j呢，j雖然沒有變化，但是i~j這個整體在變，‘i’ 到'j' 的距離不斷縮小，所以要加上j來衡量它們二者之間的變化

找邊界：當 i > j 時結束

代碼執行

#include<stdio.h>

void f2(int i, int j)
{
	if (i > j)
	{
		return;
	}
	printf("%d ", i);
	f2(i + 1, j);
}

int main()
{
	f2(2, 9);

	return 0;
}

5、對陣列arr所有元素求和

注意：前面內容為了方便更多的鐵汁理解，所以筆者選擇用C語言撰寫，但是講解了4題之后，相信大家對遞回都有了一定的認識，資料結構與演算法的講解主要講的是思路，跟編程語言無關，所以后面的題目筆者選用正在學習中的JAVA語言撰寫，大家主要聽思路，如果聽懂了，自己再用熟練的語言撰寫程式，那么將會事半功倍！

三段論

找重復：求下標begin + 1到arr.length - 1的元素之和是原問題的重復(將首元素的下邊設為begin,JAVA中對陣列arr求長度直接用arr.length即可)

找變化：begin和剩下的元素都是在變化的，那么如何衡量begin到陣列尾元素之間的變化，所以陣列名arr也得用作引數

找邊界：當begin == arr.legth - 1,也就是當走到尾時結束，

代碼執行

public class Recursion {

    public static int f3(int[] arr, int begin) {
        if(begin == arr.length - 1) {
            return arr[begin];
        }
        return arr[begin] + f3(arr, begin + 1);
    }
    public static void main(String[] args) {

        int[] arr = {1,3,4,6,7,8,9};
        int ret = f3(arr, 0);
        System.out.println(ret);
    }
}

注意：加引數也是設計遞回的一個難點，有時候我們就想不明白，為什么“切完“之后不知道怎么去寫了，比如這一題，如果形參你只給了begin，那么肯定很難用遞回去解本題，所以這個時候你就應該想想，是不是缺引數，當然，實在想不出來，可能就應該換種思維了，可能那題不適用”切蛋糕思維“，后面我們會一一介紹，

五、思考題

看過該系列博文的小伙伴都知道，筆者會在博文的最后布置一道思考題，并且講解上篇博文的思考題，

今天暫時不布置思考題了，但是有任務哦，就是將斐波那契數列和青蛙跳臺階看一下，下篇博文會詳細講解他們用到的另外一種思維，

在講解上篇思考題的時候，請大家再瀏覽一遍上篇博文的大致內容，復習鞏固一下，

https://blog.csdn.net/weixin_57544072/article/details/120798996utm_source=app&app_version=4.16.0

題：出現K次與出現1次

陣列中只有一個數出現1次，其他的數出現了K次，請輸出只出現1次的數，

如2,2,2,8,7,7,7,3,3,3

解這樣題目的時候，實在不行，就用暴力求解法--》計數即可

但是既然出現在上篇的博文中，那么一定就是讓我們使用位運算解決，

講思路之前，首先大家需要對一個知識點有所了解，那就是：

兩個相同的二進制數做不進位加法，結果為0；

十個相同的十進制數做不進位加法，結果為0；

所以有這么一個結論：K個相同的K進制數做不進位加法，結果為0

明白上面那條結論之后，就可以說解決本題的思路了：先將給定的十進制數轉化成K進制，再在每個位上做不進位加法，剩下的那個數就是只出現一次的數，不過暫時是K進制的形式，所以再將它還原成十進制數即可，

筆者在這里只給出思路，代碼怎么敲，請鐵汁們親自動手實踐，用來檢測上篇位運算掌握情況，

六、藍橋結語：遇見藍橋遇見你，不負代碼不負卿

為了讓更多的鐵汁們能看到這個系列的文章，筆者在這里請求大家動動小手，給筆者來個一鍵三連，你的支持就是筆者最大的動力，贈人玫瑰，手留余香哦，蟹蟹大家，