前言

一、什么是遞回？

首先讓我們來了解一下什么是遞回，它有什么條件，

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

遞回的兩個必要條件:

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

在寫遞回函式時需要切記這兩個條件，
遞回也要考慮堆疊溢位等問題，比如斐波那契數列數列的遞回實作，

二、漢諾塔問題

1.問題描述

傳說婆羅門廟里有一個塔臺,臺上有 3 根標號為 A,B,C的用鉆石做
成的柱子,在 A 柱上放著 64 個金盤,每一個都比下面的略小一點，把 A 柱上的金盤全部移到C柱上的那一天就是世界末日，移動的條件是：一次只能移動一個金盤,移動程序中大金盤不能放在小金盤上面，廟里的僧人一直在移個不停，因為全部的移動是2^63次,如果每秒移動一次的話,需要 500 億年，

動圖演示

2.問題分析

設最初的盤子總數為n

1. 用C 柱做過渡,將 A 柱上的(n-1)個盤子移到 B 柱上
2. 將 A 柱上最后一個盤子直接移到C 柱上
3. 用 A 柱做過渡,將 B 柱上的(n—1)個盤子移到 C 柱上

當n=3時：
看一下示例圖

利用這個解法，
將移動n 個盤子的漢諾塔問題歸結為移動(n-1)個盤子的漢諾塔問題，與此類似,移動(n-1)個盤子的漢諾塔問題又可歸結為移動(n-2)個盤子的漢諾塔問題……最后總可以歸結到只移動一個盤子的漢諾塔問題,這樣問題就解決，

3.代碼實作

#include<stdio.h>
void Hanoi(int n, char a ,char b ,char c)
{
	if (n == 1)
	{
		printf("%c->%c\n", a , c);//只有一個盤子，直接移動到C
	}
	else
	{
		Hanoi(n - 1,a ,c ,b );//將A上面n-1個盤子移動到B中
		printf("%c->%c\n", a ,c);//將A最后一個移動到C
		Hanoi(n - 1, b, a, c);//將B上的n-1個盤子移到C上
	}
}

int main()
{

	char a = 'A';
	char b = 'B';
	char c = 'C';
	Hanoi(3,a,b,c);
	return 0;
}

三、青蛙跳臺階問題

暫不考慮特別大的數使堆疊溢位，
對于青蛙跳臺階，由于步驟較多，難以畫圖，我們采用數學推理的方法，求得相關遞推公式，

問題一

1.問題描述

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

2.問題分析

當n = 1，只有一種跳法，那就是1
當n = 2，那么有兩種跳法，2，[1, 1]
當n = 3，那么有三種跳法，[1, 1, 1], , [1, 2], [2, 1]
當n = 4，那么有五種跳法，[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]
當n = 5，那么有八種跳法，[1, 1, 1, 1, 1], [1, 1, 1, 2], [1, 1, 2, 1], [1, 2, 1, 1], [2, 1, 1, 1], [2, 2, 1], [2, 1, 2], [1, 2, 2]
結果為1，2，3，5，8
有沒有感覺很眼熟
沒錯，這就是一個斐波那契數列，所以問題很快可以解決，

3.代碼實作

//遞回做法：

int RJump1(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	//n>2
	return RJump1(n - 1) + RJump1(n - 2);
}


//非遞回做法：

int  Jump1(int n)
{
	if (n == 0)
		return 0;
	if (n == 1)
		return 1;
	if (n == 2)
		return 2;
	int a1 = 1;
	int a2 = 2;
	int a3;
	for (int i = 3; i <= n; i++)
	{
		a3 = a1 + a2;
		a1 = a2;
		a2 = a3;
	}
	return a3;
}

問題二

1.問題描述

2. 一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上n級，求該青蛙跳上一個n級的臺階總共有多少種跳法，

2.問題分析

如果臺階級數為n的話，這時我們把n級臺階時的跳法看成n的函式，記函式關系為F，第一次跳的時候有n種不同的選擇：

• 若是第一次跳一級，此時跳法的數目等于后面剩下的n-1級臺階的跳法數目，即為F(n-1)，
• 若是第一次跳m(m<n)級，此時跳法的數目等于后面剩下的n-m級臺階的跳法數目，即為F(n-m)，
• 若是第一次跳n-1級，此時跳法的數目等于1，從0跳到n-1階，再從n-1到n，雖然跳了兩次，但是跳法為1，只有一種方法，此時F(n-n+1)=F(1)=1，
• 若是第一次跳n級，此時跳法的數目等于1，即F(n-n)=F(0)=1，

第三種情況比較難以想到，我也是想了很久才想明白，
所以當臺階為n時總次數為

F(n)=F(n-1)+F(n-2)……+F(1)+F(0)
令n=n-1
此時最多第一次跳n-1次
F(n-1)=F(n-2)……+F(0)
兩式相減即可得到
F(n)=2*F(n-1)

我們得到了遞推公式，以及F(1)=F(0)=1，
但是當n=1和n=0時不滿足遞推公式，所以當n=1或n=0時回傳1即可，
跳法為1，1，2，4，8……
其實可以由遞推公式看出是一個等比數列，可以算出它的和2^n-1，

3.代碼實作

int RJump2(int n)
{
	//因為遞推公式只需要找到它前一項，即F(n-1)的值就可以回傳，我們知道n=1和n=0是1種，是已經確定的值，到n=1或n=0即可結束
	if (n == 1||n == 0)
		return 1;
	//當階數大于1時可以用遞推公式
	return 2 * RJump2(n - 1);
}

直接使用公式即可，代碼簡單得讓人害怕，

問題三

1.問題描述

3. 一只青蛙一次可以跳上1級臺階，也可以跳上2級……它也可以跳上m級，求該青蛙跳上一個n級的臺階總共有多少種跳法，

2.問題分析

同樣我們采用問題2的方法，使用函式推理
當m<n時，即能跳的最大級數小于總臺階數
所以自變數最大只能到n-m，即函式為F(n-m)

F(n)=F(n-1)+F(n-2)……+F(n-(m-1)) +F(n-m)
令n=n-1
F(n-1)=F(n-2)……+F(n-m)+F(n-1-m)
解釋：因為n>m，即n-m>0，又因為他們是整數，所以n-m>=1，所以當n=n-1時，它能走的最大階數仍為m，所以有F(n-1-m)，
兩式相減即可得到
F(n)=2*F(n-1)-F(n-m)

這簡直就是在做數學，
當m>=n時，即能跳的最大級數大于等于總臺階數，這時我們采用解決問題二的公式即可，

3.代碼實作

//n為總階數，m為能跳的最大階數
int RJump3(int n, int m)
{
	//
	if (n == 1||n == 0)
		return 1;
	//當m小于n時可采用上述遞推公式
	if (m < n)
	{
		return 2 * RJump3(n - 1, m) - RJump3(n - 1 - m, m);
	}

	//當m大于等于n時可采用第二題的公式
	else
	{
		//注意此時傳參，青蛙能跳的階數最大只能為總的階數,即n
		return 2 * RJump3(n - 1, n);
	}
}


void test()
{
	printf("第一種的遞回：%d\n", RJump1(4));
	printf("第一種的非遞回：%d\n", Jump1(4));
	printf("第二種的遞回：%d\n", RJump2(4));
	printf("第三種的遞回，n>m：%d\n", RJump3(4, 3));
	printf("第三種的遞回, n<m：%d\n", RJump3(3, 4));
}

int main()
{
	test();
	return 0;
}

總結