說起遞歸，應該是讓我頭疼了很久的問題了，在各種問題里都能看見它，而且經常是代碼很簡單，楞是看不懂。。
　　關于遞歸的定義：一個函數自己調用自己，就是遞歸。對，和一個函數調用其他函數一樣，只不過遞歸是通過反復調用自己來實現的。
　　所以我們必須先要搞懂函數調用時做了什么。遞歸和普通函數一樣是通過棧實現的，調用函數時，棧內存會往上延深一層工作棧，里面會存放形參、局部變量和返回地址。為什么要放這三個東西呢，傳形參是為了讓計算機知道當前要處理什么數據，局部變量是執行函數過程需要用到的工具，返回地址是為了方法調用完成后讓計算機知道接下來應該執行哪里。函數調用完成前會把返回值存放到棧頂，返回棧頂元素也就是返回值，彈出工作棧，找到返回地址繼續執行。

　　使用遞歸需要注意的問題：
　　1.遞歸應向著問題規模減小的方向進行；
　　2.一定要有終止條件，不然會無限遞歸下去。

　　遞歸一般有三個作用：
　　1.解決本來就是用遞歸形式定義的問題；
　　2.將問題分解為規模更小的子問題進行求解；
　　3.代替多重循環。

　　下面我將舉三個例子分別說明遞歸的這三個作用：　　

　　1.解決本來就是用遞歸形式定義的問題：求n的階乘(n！)　　

　　階乘的定義是：一個正整數的階乘（factorial）是所有小于及等于該數的正整數的積，并且0的階乘為1。亦即n!=1×2×3×...×n。階乘亦可以遞歸方式定義：0!=1，n!=(n-1)!×n。（摘自百度百科）這個定義就很遞歸，程序很簡單就能寫出來。

1 int Factorial(int n) 2 { 3 if (n == 0)//終止條件 4 return 1; 5 else 6 return n * Factorial(n - 1);//問題規模減小 7 }

以求4的階乘為例，函數調用過程如下（從左到右依次是形參，返回地址用語句表示，返回值）：

　　2.將問題分解為規模更小的子問題進行求解：漢諾塔問題(Hanoi)　　

　　古代有一個梵塔， 塔內有三個座A、 B、 C， A座上有64個盤子， 盤子大小不等， 大的在下， 小的在上（ 如圖）。 有一個和尚想把這64個盤子從A座移到C座， 但每次只能允許移動一個盤子， 并且在移動過程中， 3個座上的盤子始終保持大盤在下， 小盤在上。 在移動過程中可以利用B座， 要求輸出移動的步驟。

這個問題看起來很復雜，需要注意的有兩點：
1.一次只能移動一個盤子
2.移動時大盤子在下，小盤子在上（其實也就是只能移動柱子的最上面那個盤子）

　　我們可以先假設兩種簡單的情況：　　

　　情況一：假設A柱子上只有一個盤子，很好，直接丟到C柱子上。　　

　　情況二：假設A柱子上有兩個盤子，先把A柱子上的小盤子移到B柱子，再把A柱子上的大盤子直接移到C柱子，最后把B柱子上的小盤子移到C柱子。　　

　　其實不管A柱子上有多少盤子，只要大于兩個，我們都可以看成是情況二，只不過中途需要借助其他柱子而已：假設A柱子上有n個盤子，把A柱子上的前n-1個盤子借助C柱子移到B柱子，再把A柱子上的大盤子直接移到C柱子，最后把B柱子上的n-1盤子借助A柱子移到C柱子。　　

　　至于如何把A柱子上的前n-1個盤子借助C柱子移到B柱子，和如何把B柱子上的n-1盤子借助A柱子移到C柱子，也可以以同樣的方法分成前面的n-2個小盤子和最后一個大盤子，只不過原柱子和目標柱子變了而已，方法是一樣的。就這樣我們把搬n個盤子的問題分解成了搬前n-1個盤子和第n個盤子的問題,把搬n-1個盤子分解成搬前n-2個盤子和第n-1個盤子的問題......

程序如下：

1 #include<bits/stdc++.h> 2 using namespace std; 3 //把n個盤子從src借助mid移到des 4 void f(int n,char src,char mid ,char des) 5 { 6 if(n==1)//終止條件：只有一個盤子的時候，直接移到目標柱子 7 { 8 cout << src<<"->"<<des<<endl; 9 return ; 10 } 11 //問題規模減小：否則先把src上的n-1個盤子通過des柱子移到mid，再把最后一個盤子直接移到src，再把mid上的n-1個盤子通過src移到des柱子。 12 f(n-1,src,des,mid); 13 f(1,src,mid,des); 14 f(n-1,mid,src,des); 15 } 16 int main() 17 { 18 f(3,'A','B','C');//把3個盤子從A借助B移到C 19 return 0; 20 }

程序輸入結果如下：

過程推導圖如下：

　　3.代替多重循環：n皇后問題

　　輸入整數n, 要求n個國際象棋的皇后，擺在n*n的棋盤上，互相不能攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，輸出全部方案。　　

?

　　比如我們要寫一個八皇后問題，暴力是可以做的，寫一個八重循環，每一重代表一行，再在循環寫出判定條件，如果列相等或行列絕對值相等（即在一個對角線上），就舍棄這個值，應該不難寫就不寫出代碼了，感興趣的童鞋可以自己寫著試試......下面講一講遞歸的做法。　　

　　我們要知道所有的循環理論上來說都是可以寫成遞歸的形式的，但是循環有一個致命的缺點，那就是必須要知道需要寫幾重循環，你無法寫出一個不知道大小的循環。就比如N皇后問題，我如果告訴你是四皇后問題，你可以寫出四重循環，我說是八皇后問題，你可以寫出八重循環，我說是N皇后問題呢？你能寫出N重循環去解決這個問題嗎？答案是不可以，但是我們可以用遞歸解決N皇后問題。解決的思路是這樣的：以四皇后舉例，我們先從第一行的皇后放起，每行從第1列到第4列依次嘗試，看看是否與前面各行的皇后沖突，如果都不沖突，將該行皇后放到這個不沖突的位置，再放下一行的皇后，如果第四行能找到與前面的皇后都不沖突的位置，則說明找到了該問題的一個解決方案。

　　放的過程中也許會有這樣的情況：前k-1行的皇后都放好了，但是第k行的皇后怎么都找不到合適的位置，這種情況說明第k-1行的皇后并沒有放在真正正確的位置，只保證了與前k-2行的皇后不沖突，但并沒有保證以后的皇后有合適的位置可以放置。那就倒回去把第k-1行的皇后再往后放，看有沒有其他合適的位置，如果找不到，就說明第k-2行的皇后也沒放對，再倒回去把第k-2行的皇后往后挪......這其實就是一個回溯的過程，體現在遞歸程序中就是一個方法調用完畢后，會回到當初調用這個方法的位置繼續執行。這也是為什么遞歸可以輸出全部方案的原因，遞歸會使得皇后能走的位置都走一遍，即所有行和列的組合都會遍歷到，由于是n行xn列，所以也相當于n重循環了（每重循環內部再循環n次）。

?

?

程序如下：

1 #include<iostream> 2 #include<cmath> 3 using namespace std; 4 int n;//N皇后問題 5 int queenPos[100];//下標代表第幾行的皇后，對應的值為該行皇后的列數 6 7 void f(int k) 8 { 9 if(k==n+1)//終止條件：k個皇后都擺放完畢 10 { 11 for(int i = 1;i<=n;++i)//輸出一個可行方案 12 { 13 cout <<queenPos[i]<<" "; 14 } 15 cout << endl; 16 return ; 17 } 18 for(int i = 1;i<=n;++i)//皇后可能放置的列數（該循環是程序能輸出全部方案的關鍵） 19 { 20 int j = 0; 21 for(j = 1;j<k;++j)//檢查是否與前k-1個皇后沖突 22 { 23 if(i==queenPos[j] || abs(i-queenPos[j])== abs(k-j))//是否在同一列或同一對角線上 24 { 25 break; 26 } 27 } 28 if(j==k)//當前位置i與前k-1個皇后都不沖突 29 { 30 queenPos[k] = i;//將第k個皇后放到第i列 31 f(k+1);//再放第k+1個皇后 32 } 33 }//for(int i = 1;i<=n;++i) 34 35 } 36 int main() 37 { 38 39 cin >>n; 40 f(1);//從第一行的皇后開始放 41 return 0; 42 }

　　輸出如下圖：

?

　　結束語：我覺得遞歸的難點在于它和我們平時的思維方式很不一樣，是一種計算機的思維。當我們習慣了這種計算機的思維后，遞歸應該也就不再困難了。

　　算法小白，理解多有不到之處，還請大家不吝嗇多多指教，有問題歡迎到評論區留言。

轉載于:https://www.cnblogs.com/knmxx/p/9467216.html

總結

以上是生活随笔為你收集整理的递归第一弹:初步理解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。