遞迴 === --- ### 遞迴 遞迴是指在函式呼叫自己的方法 暴力的遞迴可以解決一切問題，除了時間 ---- 遞迴是APCS很愛考的東西 也是一個很重要的程式結構 在未來教到圖論和DP時他還會出現 ---- 在寫遞迴時 我們需要考慮 __終止條件__ __轉移式__ 這兩樣東西 ---- 我們用計算次方來討論這兩項條件  這是把a^b寫成遞迴式的樣子 我們用程式寫看看 ---- ```c++= int pow(int a,int b){ if(b==0) return 1; //終止條件 return a*pow(a,b-1); //轉移式 } ``` --- 接下來我們來用遞迴寫寫看 __費氏數列__ ---- 我們先寫出他的邊界條件和轉移式 <span><!-- .element: class="fragment" data-fragment-index="1" -->f(0)=1 f(1)=1</span> <span><!-- .element: class="fragment" data-fragment-index="2" -->f(n)=f(n-2)+f(n-1) if(n>=2)</span> ---- 於是就能寫出這樣的程式碼 ```c++= int fibo(int n){ if(n==1 or n==0) return 1; return fibo(n-1)+fibo(n-2); } ``` ---- 但是用這個方法寫出來的時間複雜度非常差 將近O(2$^{n}$) n=6時執行狀況如下圖所示  ---- 根據上圖我們可以發現 有很多一樣的資料被重複算了 我們可以把已經算過的資料記下來 這就叫 __記憶化__ ---- 程式碼長這樣 ```c++= int memo[100005]={0}; int fibo(int n){ if(memo[n]) return memo[n]; if(n==1 or n==0) return memo[n]=1; return memo[n]=fibo(n-1)+fibo(n-2); } ``` ---- 用這個方法寫的話 複雜度就只剩下O(N) n=6的狀況會長這樣  ---- 搞懂的話就可以寫看看這題 [卡比採樹果](http://mdcpp.mingdao.edu.tw/contest/60/problem/P2) --- ### 經典應用 ---- 求解最大公因數(GCD) ---- 計算GCD我們有幾種方法 但用輾轉相除法是最快的 ---- ### 輾轉相除法：  ---- 假設我們要求a和b的GCD 如果a%b是0的話就代表最大公因數是b 否則就一直重複 a=b,b=原本的a%b 直到b能夠整除a ---- 用遞迴寫就是這樣 ```c++= int gcd(int a,int b){ if(a%b==0) return b; return gcd(b,a%b); } ``` ---- 但如果能用迴圈寫，就盡量不會去寫遞迴 因為遞迴在呼叫函數時會花額外的時間 ---- 參考程式 ```c++ int gcd(int a,int b){ int c; while(a%b!=0){ c=a; a=b; b=c%b; } return b; } ``` ---- 除次之外還可以直接用內建的函式 ```c++= int gcd(int a,int b){ return __gcd(a,b); } ``` ---- ## 爆搜 ---- 爆搜的概念很簡單 全部的可能跑一次就對了 拿[子集合的和](https://judge.tcirc.tw/ShowProblem?problemid=d007)這題來講解 ---- 這題要問所有組合中 小於等於p且最接近p的組合 那我們直接把所有組和找出來 一個一個看就知道答案了 ---- 參考code ```c++= #include<bits/stdc++.h> using namespace std; #define int long long int n,p,a[30],ans=0; void add(int sum,int index){ if(index==n+1){ if(sum<=p and sum>ans) ans=sum; return; } add(sum,index+1); add(sum+a[index],index+1); } signed main(){ cin>>n>>p; for(int i=1;i<=n;i++) cin>>a[i]; add(0,1); cout<<ans; return 0; } ``` ---- 當你這樣寫 你丟到一中的judge 你會拿到AC 但你丟到 [我們明道的judge](http://mdcpp.mingdao.edu.tw/problem/B022) 你會得到TLE ~~因為明道比較優秀~~ 可以去想看看測資有什麼不同 ---- ### 練習題 [APPLE](https://cses.fi/problemset/task/1623/) ---