用例子理解遞回

0.什么是遞回

在說什么是遞回之前，我想正在閱讀的你應該會使用回圈來解決一些問題了，那回圈又是什么呢？回圈是指在程式中需要反復執行某個功能而設定的一種程式結構，它由回圈體中的條件，判斷繼續執行某個功能還是退出回圈，

例如：1+2+3+4+……+10等于多少?（我們排除數學公式）

第一種解決方法就是可以使用回圈來解決，

第二種解決方法就是使用遞回來解決，

可以看到，回圈是反復執行某一段區域內的代碼，直到符合終止條件，如果不加控制，就會形成死回圈，而遞回是函式體中呼叫自己，在使用遞回的同時，一定要注意結束條件，如果不加控制，將無休止的呼叫自己，直到堆疊溢回出，因為函式每呼叫一次就會在堆疊上創建一個堆疊幀，函式呼叫結束后就會彈出該堆疊幀，而堆疊的大小不是無限的，所以遞回呼叫次數過多的話就會導致堆疊溢位，而遞回呼叫的特點是每遞回一次，就要創建一個新的堆疊幀，而且還要保留之前的環境（堆疊幀），直到遇到結束條件，所以遞回呼叫一定要明確好結束條件，不要出現死回圈，而且要避免堆疊太深，，

如果你去百度回圈和遞回的優缺點,可能有這樣的答案：

遞回演算法：
優點：代碼簡潔、清晰，并且容易驗證正確性，（如果你真的理解了演算法的話，否則你更暈）
缺點：它的運行需要較多次數的函式呼叫，如果呼叫層數比較深，需要增加額外的堆疊處理，比如引數傳遞需要壓堆疊等操作，會對執行效率有一定影響，但是，對于某些問題，如果不使用遞回，那將是極端難看的代碼，
回圈演算法：
優點：速度快，結構簡單，
缺點：并不能解決所有的問題，有的問題適合使用遞回而不是回圈，如果使用回圈并不困難的話，最好使用回圈，

我覺得這個優點和缺點是在大量接觸回圈和遞回而總結出來的，對于我們這種小白，基本上不需要糾結的，我們也體會不到，所以暫且我們不去想這些，就像上面說的，如果你真的理解了演算法的話，否則你更暈，

我們接著來看，對于上面1+2+3+4+……+10等于多少這種簡單的問題，回圈和遞回都可以解決，而用遞回也沒有顯現出它的代碼簡潔，清晰，所以我覺得不能單一的將回圈和遞回做比較，就拿順序結構，分支結構，回圈結構，模塊化結構，這四大結構來說，回圈一直是作為一個基礎內容，而遞回是為了解決特定問題而出現的演算法，本質上也屬于回圈的一種，對于上述問題，遞回演算法的優點非但沒有顯現出來，反而有點懷疑，所以解決一個問題時，要看這個問題的復雜程度，根據問題的復雜程度進而采取不同的演算法，而不是說，我學了遞回，我就應該使用它，因為書上說它的代碼簡潔，

然后想要運用遞回，最重重重要的口訣，要記住：

• 明確這個遞回函式的作用（不需要寫出具體代碼）
• 找到遞回結束條件
• 找出函式的等價關系式或最小遞回模型
• 不要試圖跟蹤遞回程序

下面通過運用口訣來解決由易到難的幾道題來理解遞回：

1.斐波那數列

斐波那契數列指的是這樣一個數列：

這個數列從第3項開始，每一項都等于前兩項之和，這個也是在遞回中常說的一道題，

第一步：
明確這個遞回函式的作用，這個函式的作用是什么？就是輸出第n項的值，

int fun(int n)
{

}

第二步：
找到遞回結束條件，當n小于等于1或者2的時候，就應該結束遞回，

int fun(int n)
{
	if(n<=2)
	{
		return 1;
	}
}

第三步：
尋找函式的等價關系式，上文中說明這個數列從第3項開始，每一項都等于前兩項之和，也就是f(n)=f(n-1)+f(fn-2)，

int fun(int n)
{
	if(n<=2)
	{
		return 1;
	}
	return fun(n-1)+fun(n-2);
}

2.小青蛙上臺階

一只青蛙一次可以跳上1級臺階，也可以跳上2級，求該青蛙跳上一個n階的臺階總共有多少種跳法，
第一步，確實遞回函式作用，求n級的臺階有多少種跳法，
第二步，確實結束條件，當臺階等于0，1，2，分別有0，1，2種方法，我們可以將這個結束條件進行整理，

int fun(int n)
{
	if(n<=2)
	{
		return n;
	}
}

第三步，確定等價關系式 ，當有n階臺階，選擇跳1階，就剩下fun(n-1)種方法，選擇跳2階，就剩下fun(n-2)種方法，兩種方法加起來就是總數，

int fun(int n)
{
	if(n<=2)
	{
		return n;
	}
	return fun(n-1)+fun(n-2);
}

3.漢塔塔

比較有名的就是漢諾塔（又稱河內塔）問題，漢諾塔源于印度一個古老傳說的益智玩具，大梵天創造世界的時候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤，大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上，并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤，還必須是最頂端的圓盤，這個題還是比較難的，我們來分析一下這個題，

A柱作為源，B柱作為輔助柱，C柱作為目標柱，
設N為盤數，當N等于1時，只需要一步：A——C 如下圖：

設N為盤數，當N等于2時，需要三步：A——B，A——C，B——C 如下圖：

設N為盤數，當N等于3時，需要7步：A——C，A——B，C——B，A——C，B——A，B——C，C——A如下圖：

當N越來越大時，需要的步驟也越來越多，當N等于64，假如每秒鐘正確移動一次，移完這些也需要5845.42億年以上，而地球存在至今不過45億年，這個數太大了！所以關于遞回，大家千萬不要跟蹤大型遞回的程序， 關鍵就是找出最小遞回模型或者是上面所說的遞回的等價關系式，

第一步，我們要在黑框框中顯示訊息，第幾步哪個盤子從哪個柱子移動到了哪個柱子上，
這個列印函式需要4個引數和一個全域變數用于步數的輸出，

void move(int id, char form, char to)
{
	cout << "第" << sum++ << "步：將" << id << "號盤子從" << form << "移動到" << to<<endl;
}

并且確定函式的目的：輸出第幾步哪個盤子從哪個柱子移動到了哪個柱子上，這個我們用move函式來輸出，

第二步，找出遞回結束條件，當n等于0時或者1（另一種寫法，沒有寫出），作為結束條件，

第三步，就是最小遞回模型的尋找，
我們有三個柱子和n個盤子，所以函式的定義應該是：void fun(int n, char a, char b, char c)，a,b,c分別對應三根柱子，我們尋找最小遞回模型：fun(n)上一步fun(n-1)怎么走，當n等于1時，直接將盤子從A柱移到B柱即可，當n等于2時，如上圖，需要三步，也是我們所尋找的最小遞回模型，當n=2時
fun(n - 1, a, c, b);表示標記為為n-1盤，從A柱通過輔助柱C移動到B柱
move(n, a, c);表示標記為n的盤，從A柱移動到C柱
fun(n - 1, b, a, c);表示標記為為n-1盤，從B柱通過輔助柱A移動到C柱

將n-1看成一個整體，n和n-1就固定的三步，完整代碼如下：

int sum=1;    //記錄步數
void move(int id, char form, char to)
{
	cout << "第" << sum++ << "步：將" << id << "號盤子從" << form << "移動到" << to<<endl;
}
void fun(int n, char a, char b, char c)
{
	if (n == 0)return; 
	fun(n - 1, a, c, b);
	move(n, a, c);
	fun(n - 1, b, a, c);
}
int main(int argc, char** argv) {
	while (1)
	{
		sum = 0;
		int x;
		cin >> x;
		fun(x, 'A', 'B', 'C');
	}
	return 0;
}
}

例子就舉到這里，慢慢學習，你會發現遞回是一個很神奇的東西，我這樣平平的一個人都可以理解，我覺得你們都可以理解，而學習遞回還有一個不得不提的一個名詞叫迭代，關于迭代，后面再說，