目錄

#前言

#一、什么是遞回

#二、遞回的必要條件

#三、遞回的步驟

#四、遞回的一些應用例題

熬夜早起肝博客！！沖！！

#前言

大家好，今天給大家帶來遞回初步學習的大總結，對剛接觸遞回的同學來講是一個非常不錯的鞏固與練習，希望大家有所識訓，

#一、什么是遞回

程式呼叫自身的編程技巧稱為遞回（ recursion），
遞回做為一種演算法在程式設計語言中廣泛應用， 一個程序或函式在其定義或說明中有直接或間接
呼叫自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞回策略只需少量的程式就可描述出解題程序所需要的多次重復計算，大大地減少了程式的代碼量，
遞回的核心思想（主要思考方式）是把大事化為小事

#二、遞回的必要條件

1.存在限制條件，當滿足這個限制條件的時候，遞回便不再繼續，
2.每次遞回呼叫之后越來越接近這個限制條件，

#三、遞回的步驟

1.函式遞回時，每次呼叫一次函式，計算機都會在記憶體堆疊區為函式開辟一個新的空間，也就是說
如果遞回層次過深，會導致堆疊區空間不足，也就是所謂的堆疊溢位（Stack Overflow），使用VS2019編譯器時若遞回層次過深則會發生報錯，在下面解釋斐波那契數列時也會在做說明
2.函式遞回結束函式開始回傳，開辟的空間開始釋放

切記！函式遞回呼叫函式時從外層一層一層進入內層，回傳函式時從內層一層一層回傳出外層！

#四、遞回的一些應用例題

下面的例題會貫徹上面的遞回思想（即把大事化小）

1.逐個列印一個多位數的各個位

先上代碼

#include <stdio.h>
void print(int num)
{
	if (num > 9)
	{
		print(num / 10);
	}
	printf("%d ", num%10);
}
int main()
{
	int ret = 0;
	scanf("%d",&ret);//1234,
	print(ret);
	return 0;
}

下面通過畫圖的方式對該題進行講解，我們假定輸入的值為1234

注意列印的順序，程式是按箭頭的順序開始執行！紅色箭頭執行完后開始執行藍色箭頭（回傳時深一層函式完全執行完后再回傳到淺一層函式，淺一層函式再開始執行下面陳述句），因此按順序列印后結果應該是1 2 3 4，程式運行結果：

這道題一定要好好體會函式遞回陳述句執行的順序，特別是函式回傳的時候

第一題的函式采用void定義，沒有向主函式回傳值，下面來一個有向主函式回傳值的

2.計算n的階乘

還是先上代碼！

#include <stdio.h>
int jc(int n)
{
	int ret = 0;
	if (n < 2)
	{
		return 1;
	}
	else
	{
		return n * jc(n - 1);
	}
}
int main()
{
	int n = 0;
	printf("請輸入一個值n\n");
	scanf("%d", &n);
	printf("%d的階乘=%d ",n,jc(n));
	return 0;
}

這里函式里面定義的ret沒用，手誤

還是采用畫圖的方式對本題進行詳細講解

這里我們假設n=4

這一道題可以更加深化理解函式遞回回傳時的步驟，從內到外開始回傳，下面貼上程式執行結果：

3.遞回模擬strlen測量陣列長度

代碼：

#include <stdio.h>
int _strlen(char *arr)
{
	if (*arr == '\0')
	{
		return 0;
	}
	else
	{
		return 1 + _strlen(arr + 1);
	}
}
int main()
{
	char arr[20]= {"abcdefg"};
	printf("長度=%d ", _strlen(arr));
	return 0;
}

注意！呼叫函式時函式引數arr代表的是arr[20]中首元素的地址，因此定義函式時接收引數的形參為指標變數，該題與上一題思路相同，不做贅述，只講一點，*是解義字符，arr是地址，那*arr即代表解地址，那就是字串中的元素，又字串的結束標志是\0，故函式部分如上圖呈現

下面是程式執行結果：

（此處也說明了字串結束標志并不算在長度里面）

怎么樣是不是忽然感覺用遞回很牛逼很牛逼哈哈哈哈哈哈，有沒有犯迷糊的地方呢

4.斐波那契數列

斐波那契數列（Fibonacci sequence），又稱黃金分割數列，因數學家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數列”，指的是這樣一個數列：0、1、1、2、3、5、8、13、21、34、……在數學上，斐波那契數列以如下被以遞推的方法定義：F(0)=0，F(1)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 2，n ∈ N*）——源自百度百科

簡單理解為數列下一項等于前兩項之和

先上代碼

#include <stdio.h>
int Fibon(int n)
{
	if (n <= 2)
		return 1;
	else
		return Fibon(n - 1) + Fibon(n - 2);
}
int main()
{
	int n = 0;
	int ret = 0;
	scanf("%d", &n);
	ret = Fibon(n);
	printf("ret=%d", ret);
	return 0;
}

有了上面的公式，這一段遞回很好理解，但這道題的重點不在這里，大家可以試運行一下n=50，在一分鐘之內電腦應該是不能給出結果的，在n<=35時計算機可以秒給出答案，那么這是為什么呢？我們來看下面的圖，假設n為50（此處Fib代指斐波那契）

可以發現只進行了幾次呼叫，計算機已經做了大量重復運算，那當n足夠大時，這個重復運算的量可謂相當龐大，因此大大減慢了代碼的運算速度，甚至導致堆疊溢位

因此這個題用迭代實作更好（用遞回能實作的都可以用迭代實作） ，代碼如下

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
int Fibon(int n)
{
	int a = 1;
	int b = 1;
	int c = 0;
	int i = 0;
	if (n <= 2)
	{
		return 1;
	}
	else
	{
		for (i = 0; i < (n - 2); i++)
		{
			c = a + b;
			a = b;
			b = c;
		}
		return c;
	}
}
int main()
{
	int n = 0;
	int ret = 0;
	scanf("%d", &n);
	ret = Fibon(n);
	printf("ret=%d", ret);
	return 0;
}

只需注意一點，for回圈中計算完前兩項的和（a+b）后，要將a賦值為b，b賦值為a+b的和，即將a，b均向后移一項，這樣才可以計算下下一項的和，

有公式是不是遞回變的例外簡單，反而迭代寫法還需要一些思考呢，所以是否使用遞回是需要根據情況選擇的

5.遞回實作字串逆序

即如果輸入的字串是abcdef，則輸出fedcba

本題也可用迭代寫出且較遞回更為簡潔明了，可以嘗試，這里不再給出代碼，下面講解迭代做法

代碼：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
void nixu(char* arr1)
{
	char linshi = *arr1;
	int n = strlen(arr1);//字串長度
	*arr1 = *(arr1 + n - 1);//n-1為最后一個元素的下標
	*(arr1 + n - 1) = '\0';
	if (strlen(arr1 + 1) >= 2)
	{
		nixu(arr1 + 1);
	}
	*(arr1 + n - 1) = linshi;
}
int main()
{
	char arr[] = { "abcdef" };
	nixu(arr);
	printf("%s", arr);
	return 0;
}

下面畫圖來細細理清這段代碼

逆序無非是讓字串中的元素一對一對的對調，注意接下來的思路！

遞回，把大事化小事

我們把abcdef的逆序拆為af的逆序加bcde的逆序，把bcde的逆序再拆為ce的逆序加cd的逆序，那遞回的思路不就出來了嗎，我們需要做的就是把第一層函式呼叫寫清楚，接下來只不過是計算機的重復運算罷了，接下來單獨分析函式部分

稍作解釋：*arr1表示字串中第一個元素*arr+n（字串長度）-1為字串最后一個元素

接下來做四步！：

第一步：把首元素的值賦給一個臨時儲存用的變數

這一步是為了存盤第一個元素，以便把最后一個元素放到第一個元素的位置

第二步：把最后一次元素放到第一個元素的位置

注意這里需要先求字串長度，因為字串最后一個元素下標為長度-1 （為了方便直接用了strlen函式，其實也可以用上面寫的代碼替換）

第三步：把字串最后一個元素換為/0

這一步非常重要，因為字串的結束標志是\0，只有這樣進行遞回時才能繼續進行，換完后現在如下圖

這里a還被存盤在外面

第五步：把新的字串進行逆序，即"bcde\0"

arr1+1表示陣列第二個元素，所以新的字串為 "bcde\0"，需要注意的是這個判斷條件，當新的字串長度大于等于2時，才繼續進行呼叫，若長度為0或1，如原始字串為"ab"（為0）、"abc"（為1）這些都是進行一次交換后已經完成逆序的，因此不需要再進行下面的逆序，逆序已經完成

第六步：當所有元素完成逆序后，把a放到最后一個元素

至此所有步驟完成

下面來重新理順：

1.將首元素單獨拿出，放到一個臨時變數存盤

2.將末元素放到首元素的位置

3.在末元素的位置上放\0以便進行下一次字串逆序

4.新的字串（即去除原本字串首元素和末元素的字串）進行逆序

5.在所有元素完成逆序后把首元素放到末元素的位置

注意其中第四步我們不需要去考慮是怎么實作的，這一步其實就是遞回思想的核心，把大事化小，我們只需要去做最小的那一件事，剩下的不需要我們管，

代碼運行結果：

6.遞回經典問題之漢諾塔問題 漢諾塔

7.遞回查找自定義陣列最大值 陣列

以上兩個問題在前兩次博客中已經做了詳細解釋，大家有需要可以點擊鏈接查看

最后來看一個非常有意思的題目，

青蛙跳臺階問題

首先來看普通青蛙跳臺階！

問題描述：一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n級的臺階總共有多少種跳法（先后次序不同算不同的結果）

先進行列舉

n=1時，1種，直接跳上去

n=2時，2種，直接跳上去或者一個一個跳

n=3時，3種，（1,1,1）（2,1）（1,2）

n=4時， 5種，（1,1,1,1）（1,1,2）（1,2,1）（2,1,1）（2,2）

n=5時， 8種，（1,1,1,1,1）（1,1,1,2）（1,1,2,1）（1,2,1,1）（2,1,1,1）（1,2,2）（2,1,2）（2,2,1）

是不是似曾相識啊，這不是剛剛講過的斐波那契數列嗎！如果我們再假定一個n=0時，青蛙只能不跳，那不也是一種嗎，

那這里怎么理解呢，青蛙跳3層臺階時，分為1層臺階+2層臺階，也就是說青蛙跳臺階的方法是跳1層臺階的方法+跳2層臺階的方法

跳4層臺階時，若青蛙某一次跳上1層臺階，則剩下3層臺階，若跳上2層臺階，則剩下2層臺階，所以跳4層臺階時的方法是跳3層臺階的方法+跳2層臺階的方法

跳5層臺階時，還是跳1或者跳2的問題，跳1那么接下來的4層就按4層臺階的方法來跳，跳2那么接下來的3層就按3層臺階的方法來跳，所以跳5層臺階的方法是跳4層臺階的方法+跳3層臺階的方法

以此類推

跳n層臺階的方法數量（n＞2）F（n）=F（n-1）+F（n-2）,還真和斐波那契數列運算式一樣，因此代碼省略，接下來我們來看看重量級的超人青蛙選手（有點難）

與普通青蛙不一樣的是，超人青蛙可以一次跳多個臺階，多多少呢？無數個，對就是這么離譜

先假設青蛙現在可以跳3節臺階了

n=1時，1種，直接跳上去

n=2時，2種，直接跳上去或者一個一個跳

n=3時，4種，（1,1,1）（2,1）（1,2）（3）

n=4時，7種，（1,1,1,1）（1,1,2）（1,2,1）（2,1,1）（2,2）（1,3）（3,1）

n=5時，13種，（1,1,1,1,1）（1,1,1,2）（1,1,2,1）（1,2,1,1）（2,1,1,1）（1,2,2）（2,1,2）（2,2,1）（1,1,3）（1,3,1）（3,1,1）（2,3）（3,2）

總結出規律：F（n）=F（n-1）+F（n-2）+F（n-3）

那么我們大膽推測，當可以跳N層臺階時

F（n）=F（n-1）+F（n-2）+F（n-3）+……+F（n-N+1）+F(n-N)共加了N項（n＞N）

代碼：

這里代碼我還沒想出來，對于現在的我還是過于復雜了，在未來的某一天我會重新回來補充的，哈哈哈哈哈哈哈哈哈

到此為止初識遞回就結束了，如果把這篇博客的每一個例題都吃透的話我相信一定會識訓頗豐，從剛接觸遞回的小白到能使用遞回可能只差幾遍代碼，關于遞回我一共寫了三篇博客，在一段時間內可能不會再更新關于遞回的內容，希望在未來的學習中不斷深化對遞回的理解、應用，有朝一日能寫出自己對遞回的更深理解！

如果覺得文章有用請給個小手加評論鼓勵哦！！！謝謝！！