0基礎演算法基礎學演算法 第六彈 遞歸
- 2020 年 4 月 19 日
- 筆記
最近呢也是有很久沒有更新部落格了，主要是因為平時比較忙，畢竟等疫情徹底解封qj我也要小升初考試了，所以打算趕在今天更新點乾貨。
在各大oi賽事上，遞歸和遞推算是個基礎而重要的演算法，遞歸在熟練運用後可以實現dfs，dfs是深度優先搜索，以後會講到關於dfs的；而遞推是一種用若干步可重複運算來描述複雜問題的方法，比如斐波那契數列，上樓梯等都是可以通過遞推來進行實現的，而下一講即將會具體講述遞推，今天的主題是遞歸
現在切入正題
一.遞歸
遞歸函數其實在比賽中特別常見，很多人在比賽的時候遇到不會的題就直接打暴力，但是如果你會遞歸的話，你可以用一通pmn或者dfs直接爆搜（據有關人士稱，去年提高組如果pmn可以的200+。。。）那到底什麼是遞歸呢？遞歸函數，即是自己調用自己，理解遞歸最好是通過一個例子來理解，比如，超經典的基礎題，1+2+3+4+…+n-2+n-1+n=？遇到這個題，一般做法是利用for循環一個一個的累加，提供一個c++程式碼
#include<bits/stdc++.h>//萬能頭文件，建議比賽時使用 using namespace std; int s,i,n; int main() { S=0;
cin>>n; for(i=1;i<=n;i++) s=s+i; cout<<s; return 0; }
這是最簡單也最直觀的程式碼，如果使用遞歸實現雖然會看起來麻煩一點，但對遞歸的理解有好處。演算法的流程圖大概是是這樣的
#include <iostream> using namespace std; int dg(int n) //遞歸函數，n定義的是局部變數不衝突 { if(n==1) return 1; return (dg(n-1)+n);//進行遞歸 } int main() { int n; cin>>n; cout<<dg(n); return 0; }
大概就是這樣子的，遞歸的一個基本的主體框架有兩個部分，一個是反覆遞歸的過程，還有就是中止條件，不然你的程式停不下來可很悲催的一件事，相信我，程式死活不輸出你也找不到問題所在，只能瀏覽程式了，到了後期，這些細節要越發的注意，因為現在我寫程式碼都動不動65+行，比如高精度就要佔你數十行；
#include <iostream> using namespace std; int dg(int n) //遞歸函數，n定義的是局部變數不衝突 { if(終止條件) return 中止的返回值; dg(n-1);//進行遞歸 (舉例) //遞歸的形式需要根據需要而調整，比如有時候你也許會是是dg(n+1)+n; } int main() { dg(n); //調用遞歸函數 return 0; }
遞歸的基本模板👆；
重點是自己調用自己這一塊比較難理解，可以自己試圖去嘗試寫一些遞歸程式
這裡再和大家分享一道經典的題：
設有n個數已經按從大到小的順序排列，現在輸入x，判斷它是否在這n個數中，如果存在則輸出yes，否則輸出 no；
拿到題目先分析（這裡節省點位置，流程圖留給你們自己去畫吧🙂），這是一道比較簡單的數據查找的問題，一般使用順序查找，使用for循環，這個for循環也可以「遞歸化」；分別展示一下for做法和遞歸做法（其實還有一個做法會在未來講二分查找的時候講）
#include <bits/stdc++.h>//萬能頭可以省好多事 using namespace std; int main(){ int a[10];//用於錄入10個數 int n; for(int i=0;i<10;i++) cin>>a[i]; sort(a,a+10); //快速排序函數庫，加了萬能頭就不用加它的頭文件了 cin>>n; for(int i;i<10;i++) { if(a[i]=n) { cout<<"yes"; return 0; } } cout<<"no"; return 0; }
#include <bits/stdc++.h>//萬能頭可以省好多事 using namespace std; int a[10];//用於錄入10個數 bool b=false; void fun(int n,int k) { if(n==a[k]) { b=true; return; }//找到了，標記一下，直接跳出，不需要再找了 else if(k<0) return; //全部找完都沒找到，也不用找了 fun(n,k-1);//調用部分 } int main(){ int n; for(int i=0;i<10;i++) cin>>a[i]; sort(a,a+10); //快速排序函數庫，加了萬能頭就不用加它的頭文件了 cin>>n; int k=9;//下標從0開始 fun(n,k); if(b) cout<<"yes"; else cout<<"no"; return 0; }
注釋 上：for遍曆法 遞歸遍曆法 敬請期待二分查找（還不快關注。。。）
上面的做法都是可行的，運行結果一切正常
。
部落格留題！：
洛谷遞歸題單 //www.luogu.com.cn/training/109#problems
酌量練習，把握分度，不然會沉迷於洛谷這個花花綠綠的遊戲網站 （划去）
今天的內容就是這些了，下次會講遞推，還會分享一些資料，假如你有興趣，先點贊👍，關注➕走一波，關注後歡迎白嫖😀；
