What’s the 遞歸算法

定義：
程序直接或間接調用自身的編程技巧稱為遞歸算法（Recursion）。
一個過程或函數在其定義或說明中又直接或間接調用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復計算，大大地減少了程序的代碼量

特點：
任何一個可以用計算機求解的問題所需的計算時間都與其規模n有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。
分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
如果原問題可分割成k個子問題（1＜k≤n），且這些子問題都可解，并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。
由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。

注意事項：

遞歸算法運行效率較低

容易爆棧

一定要設置遞歸出口不然容易死鎖而且爆棧

Why we learn this？

遞歸是搜索、分治、回溯算法的

例題：

1. Fibonacci數列

我們之前寫過遞推的方法，這次我們寫遞歸的方法。
PS：矩陣快速冪和母函數是解決此類問題的最快方式，有興趣的可以去我博客里看看。

int fib(int n) {if (n<=1) return 1;return fib(n-1)+fib(n-2); } int main() {int n;cin>>n;cout<<fib(n)<<endl; }

2.集合全排列問題

排列組合的普遍復雜度就是N！

例如 給定N求 1-N的全排列問題
假設N=3 那么輸出 123 132 213 231 312 321

void Perm(int list[], int k, int m) {if(k==m) //構成了一次全排列，輸出結果{for(int i=0;i<=m;i++)cout<<list[i]<<" ";cout<<endl;}else//在數組list中，產生從元素k～m的全排列for(int j=k;j<=m;j++){swap(list[k],list[j]);Perm(list,k+1,m);swap(list[k],list[j]);} } int main() {int n;int a[10000];cin>>n;for(int i=0;i<n;i++)cin>>a[i];Perm(a,1,n); }

3.整數劃分問題

題目：將一個整數劃分為多個整數想加的形式，并輸出有所劃分方法的數量。 例：6的劃分： 6=5+1 6=4+2 6=4+1+1 6=3+3 6=3+2+1 6=3+1+1+1 6=2+2+2 6=2+2+1+1 6=2+1+1+1+1 6=1+1+1+1+1+1

遞歸轉移方程：

實現：

int split(int n,int m) {if(n==1||m==1) return 1;else if (n<m) return split(n,n);else if(n==m) return split(n,n-1)+1;else return split(n,m-1)+split(n-m,m); } int main() {int n;cin>>n;split(n,n); }

現在增大難度，輸出所有的劃分方式：

#include <bits/stdc++.h> using namespace std; stringstream ss; int split(int n, int m, string s) {if (m == 0){cout << s << endl;return 0;}for (int i = 1; i <= n && i <= m; i++){string s1;ss.clear();ss << i;ss>>s1;s1= s + (( s[s.size()-1]=='=')? ' ' : '+' )+s1;split(i, m - i, s1);} } int main() {int n;cin>>n;ss<<n;string s<<ss;split(n, 10, s+" ="); }

4. 階乘

遞歸思想：n! = n * (n-1)! (直接看公式吧)
首先分析數列的遞歸表達式：

#include <bits/stdc++.h> using namespace std; stringstream ss; int f(int n) {if (n == 1)return 1;elsereturn n * f(n - 1); } int main() {int n;cin >> n;cout << f(n); }

5.漢諾塔問題

數學描述就是：

有三根桿子X，Y，Z。X桿上有N個(N>1)穿孔圓盤，盤的尺寸由下到上依次變小。要求按下列規則將所有圓盤移至Y桿：

每次只能移動一個圓盤；

大盤不能疊在小盤上面。

遞歸思想：

將X桿上的n-1個圓盤都移到空閑的Z桿上，并且滿足上面的所有條件

將X桿上的第n個圓盤移到Y上

剩下問題就是將Z桿上的n-1個圓盤移動到Y上了

#include <iostream> #include <cstdio> using namespace std;int cnt;void move(int id, char from, char to) {printf ("step %d: move %d from %c->%c\n", ++cnt, id, from, to); }void hanoi(int n, char x, char y, char z) {if (n == 0)return;hanoi(n - 1, x, z, y);move(n, x, z);hanoi(n - 1, y, x, z); }int main() {int n;cnt = 0;scanf ("%d", &n);hanoi(n, 'A', 'B', 'C');return 0; }

寫在最后：
Name:風骨散人，喜歡碼代碼，碼字，目前是一名雙非在校大學生，預計考研，熱愛編程，熱愛技術，喜歡分享，知識無界，希望我的分享可以幫到你！名字的來源：我想有一天我能有能力隨心所欲不逾矩，不總是向生活低頭，有能力讓家人擁有富足的生活而不是為了生計而到處奔波。
文章主要內容：
Python,C++,C語言,JAVA,C#等語言的教程
ACM題解、模板、算法等，主要是數據結構，數學和圖論
設計模式，數據庫，計算機網絡，操作系統，計算機組成原理
Python爬蟲、深度學習、機器學習
計算機系408考研的所有專業課內容
一些程序猿常用的軟件或者黑科技什么的
目前還在更新中，先關注不迷路。微信公眾號，cnblogs（博客園），CSDN同名“風骨散人”

如果有什么想看的，可以私信我，如果在能力范圍內，我會發布相應的博文！
感謝大家的閱讀！😘你的點贊、收藏、關注是對我最大的鼓勵！

總結

以上是生活随笔為你收集整理的算法分析设计--递归算法的全部內容，希望文章能夠幫你解決所遇到的問題。

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