# 遞迴
* [name=Ivy Lin]
* [回首頁](https://hackmd.io/Qu2e9pQNSHC-e58Vp3ObhQ)
## 【簡介】
* #### **簡單遞迴**
1. 構思函數的運作後簡化
2. 找到一般項(通式)化簡
3. 令基礎數值(也可以說停止點或是最後一次呼叫函數的數值)
* #### **雙函數遞迴**
1. 過程與簡單遞迴相似，但請注意雙函數呼叫型式
2. 時間複雜度會大幅上升(注意TLE)
3. 善用陣列
:::danger
注意
>雖然可以讓複雜的運算簡化，但由於不斷呼叫函數，時間複雜度會指數型上升。
>數字不大時可善用遞迴，若要呼叫多次則容易TLE。
:::
## 【經典題】
### 輾轉相除法
:::info
**敘述**
>又稱歐幾里得演算法，專門用來求大數的最大公因數。
* *A=qB+R*
>求(A,B)
輾轉相除法利用(A,B)=(B,R) 反覆取餘數得到結果
:::
* **思路**
>1. 大數除小數取餘數(A%B)
>2. 若餘數為0則回傳除數(B)
* **程式**
```clike=
//A=q*B+R
int gcd(int A,int B){
//呼叫函數時大數為A 小數為B
if(B==0) return A;
else return gcd(B,A%B);
}
```
### 河內塔
:::info
**敘述**
>有三根桿子，要將n個圓盤從第一根桿子移動到第三根(過程中大圓盤不得疊放在比它小的圓盤上)
>請問需要幾個步驟?
:::
* **思路**
>1. 重複做的地方=>
>(1) 將最大圓盤以上所有圓盤搬到桿子2
>(2) 將大圓盤移動到桿子3
>(3) 將其餘圓盤放到桿子3
>2. 遞迴=>搬運(n-1)個圓盤到2，搬運1個圓盤到3，搬運(n-1)個圓盤到3
>3. 最後呼叫=>只有一個圓盤時只需要搬一步
```clike=
#include<stdio.h>
int ans;
void change(int n){
if(n==1)
ans+=1;
else
{
//遞迴處!!!
//計算搬運到桿子2所需步數
change(n-1);
//搬最大的圓盤=>一步
change(1);
//計算搬運到桿子3所需步數
change(n-1);
}
}
int main(){
int n;
scanf("%d",&n);
change(n);
return 0;
}
```
:::danger
注意
>河內塔遞迴看似簡單，其實遞迴時所經歷的過程是不一樣的(移動到不同桿子)
:::
### 費氏數列
:::info
* **敘述**
>f(0)=0;
>f(1)=1;
>f(n+1)=f(n)+f(n-1);
:::
* **思路**
>1. 重複做的地方=>加法
>2. 停止點=>n=0或n=1
* **程式【寫法1】**
```clike=
//用陣列紀錄數值
#include <stdio.h>
int table[100];
int fa_sequence(int n)
{
if (n == 0 || n == 1)
return table[n];
if (table[n] != 0)
return table[n];
else
{
table[n] = fa_sequence(n - 1) + fa_sequence(n - 2);
return table[n];
}
}
int main()
{
table[0] = 0;
table[1] = 1;
int n;
scanf("%d", &n);
printf("%d\n", fa_sequence(n));
return 0;
}
```
* **程式【寫法2】**
```clike=
//尾遞迴(tail recursion)寫法
#include <stdio.h>
int fa_sequence(int n, int ans, int prev)
{
if (n == 0)
return prev;
else if (n == 1)
return ans;
else
//遞迴處!!!
//呼叫前一個數，遞迴過程不斷將基數往上加直到遞迴結束
return fa_sequence(n - 1, ans + prev, ans);
}
int main()
{
int n;
scanf("%d", &n);
printf("%d\n", fa_sequence(n,1,0));
return 0;
}
```
:::danger
注意
>費氏數列和河內塔一樣，數字呈指數型態成長，
>遞迴只適用於數字小的狀況
>第二個方法使用tail recursion寫法能最佳化運算過程，
>尾遞迴能使堆疊框(為了呼叫下一層函數所產生的記憶體格)有效減少，
>提高程式執行速度。
:::
### 進位轉換
:::info
* **敘述**
>轉換10進位=>2進位
:::
* **思路**
>1. 重複做的地方=>/2、%2
>2. 遞迴=>
>(1)將數字想成=>n/2的二進位表示(前)+n%2的值(後)
>(2)所以每次遞迴就是=>將數字拆兩份，前一份遞迴
>3. 停止點=>n/2=0
* **程式**
```clike=
#include <stdio.h>
void binary(int n)
{
if (n > 0)
{
//遞迴處!!!
binary(n / 2);
//注意是先遞迴後印數字
printf("%d", i % 2);
}
}
int main()
{
int n;
scanf("%d", &n);
binary(n);
return 0;
}
```
:::warning
進位變化題
>不同的進位轉換=>想法一樣
:::
### 找錢
:::info
* **敘述**
>輸入不同面值的銅板，然後輸入金額，將可能的找零方式列出
:::
* **思路**
>1. 重複做的地方=>要選擇幾個面值銅板(可以有很多種配法)
>2. 遞迴=>考慮兩種可能
>(1) 使用1元=>錢變成M-1元
>(2) 不使用1=>考慮剩下的5和10元來湊
>3. 停止遞迴=>手上剩下0元、手邊剩下小於0元、沒有辦法湊了
* **程式**
```clike=
#include <stdio.h>
int count[10];
int number[10];
void change(int money, int inde, int total)
{
// 檢查點1=>是否超過可用的面額種類
if (inde < total)
{
// 檢查點2=>完成題目條件(money=0)
if (money == 0)
show(total);
// 檢查點3=>money是否還可以找錢(小於0就爆掉QAQ)
else if (money > 0)
{
// 遞迴處!!!
// 第一種狀況=>使用大一個面額湊
change(money, inde + 1, total);
// 第二種狀況=>多使用一個同面額
number[inde] += 1;
change(money - count[inde], inde, total);
number[inde] -= 1;
// 記得要記得"拿起來"這個動作!!!
}
}
}
void show(int total)
{
printf("(%d", number[0]);
for (int i = 1; i < total; i++)
printf(",%d", number[i]);
printf(")\n");
}
int main()
{
// 輸入總共有幾種面額的銅板
int total;
scanf("%d", &total);
// 輸入面額為多少
for (int i = 0; i < total; i++)
scanf("%d", &count[i]);
// 輸入要找的錢
int money;
scanf("%d", &money);
change(money, 0, total);
return 0;
}
```
:::warning
找錢的應用題
>定每個硬幣的使用上限=>多檢查遞迴時是否超過使用上限
:::
### 八個皇后
:::info
* **敘述**
>皇后可以走米字，我們想在n*n的棋盤上擺上n個皇后
>請問有哪些擺法?
:::
* **思路**
>1. 和城堡的思路一樣(但在檢查的地方要額外檢查斜線)
>[城堡題](https://hackmd.io/WxIV_VYESouK3qdvuGHtGw?#%E6%93%BA%E7%9A%87%E5%90%8E%E8%A5%BF%E6%B4%8B%E6%A3%8B)
>2. 精簡紀錄的點=>不記錄行數，改成紀錄放置第幾格即可(可以有效簡化記錄的資料)
>3. 檢驗是否可放的函數記得要多檢查45度(斜上方的格子是否有被放置棋子)
* **程式**
```clike=
#include <stdio.h>
int board[20];
int ans;
// int place(int row, int size);
// int check(int row, int inde);
int place(int row, int size)
{
// check if the row is equal to the size of the board
//printf("place(row,size)=(%d,%d)\n", row, size);
if (row == size)
ans += 1;
else
{
// place the queen
for (int i = 0; i < size; i++)
{
// check (row,i) can place the queen or not
//printf("check(row,inde)=(%d,%d)\n", row, i);
if (check(row, i))
{
board[row] = i;
place(row + 1, size);
}
}
}
return ans;
}
int check(int row, int inde)
{
for (int i = 0; i < row; i++)
{
if (board[i] == inde || board[i] - inde == i - row || board[i] - inde == row - i)
{
//printf("can't put in (%d,%d)\n\n", row, inde);
return 0;
}
}
//printf("put in (%d,%d)\n\n", row, inde);
return 1;
}
int main()
{
int size;
scanf("%d", &size);
printf("%d\n", place(0, size));
return 0;
}
int main(void)
{
int size;
scanf("%d", &size);
place(0, size);
printf("%d\n",ans);
return 0;
}
```
* **程式2**
```clike=
#include<stdio.h>
int N;
int col[14], d1[27], d2[28];
int getans(int row)
{
if(row==N) return 1;
int res=0;
for(int i=0;i<N;i++)
{
if(col[i]) continue;
if(d1[row+i]) continue;
if(d2[row-i+14]) continue;
col[i]=1;
d1[row+i]=1;
d2[row-i+14]=1;
res+=getans(row+1);
col[i]=0;
d1[row+i]=0;
d2[row-i+14]=0;
}
return res;
}
int main()
{
scanf("%d",&N);
printf("%d",getans(0));
return 0;
}
```
* **程式3**
```clike=
#include<stdio.h>
int N;
int L,M,R;
int getans(int row)
{
if(row==N) return 1;
int res=0;
for(int i=0;i<N;i++)
{
if((L | M | R) & (1<<i)) continue;
int l=L,m=M,r=R;
L |= (1<<i);
M |= (1<<i);
R |= (1<<i);
L <<=1;
R >>=1;
res+=getans(row+1);
L=l,M=m,R=r;
}
return res;
}
int main()
{
scanf("%d",&N);
printf("%d",getans(0));
return 0;
}
```
## 【補充例題】
### Johnny Johnny
:::info
**敘述**
>*PaPa gave Johnny n numbers a1~an and a number k.
>PaPa asked Johnny to calculate how many ways he could pick some numbers from a1 to an in order to make their sum equal to k?*
* ***Input***
>*Contains two lines.
>First line contains two integer n (1≤n≤20), k (1≤k≤10^9)
>Second line contains n integer a1~an (1≤ai≤10^7)*
* ***Output***
>*Only contains one integer that is sum of available ways to pick numbers,
>witch summation is equal to k.
>(Remember to print \n at the end of output.)*
:::
* **思路**
>1. 數字總量只有20個(不多)=>可使用遞迴
>2. 遞迴使用=>決定是否要加上這個數
>3. 停止=>當sum=k或處理的數字量超過n
* **程式**
```clike=
#include <stdio.h>
int ans, n, k;
int input[21];
void count(int ind, int sum)
{
if (ind >= n || sum >= k)
{
if (sum == k)
ans++;
return;
}
count(ind + 1, sum); //不加
count(ind + 1, sum + input[ind]); //加
}
int main()
{
scanf("%d %d", &n, &k);
for (int i = 0; i < n; i++)
scanf("%d", &input[i]);
count(0, 0);
printf("%d\n", ans);
return 0;
}
```
### Yes papa
:::info
**敘述**
>*Johnny redefine string equivalence by new rules. Given two string ,a,b with equal length, Johnny compares two string, a,b by the following rules to determine if the two strings are equivalent :*
>
>1. *If the length of the string is odd, then he directly check if the two strings are the same.*
>2. *If the length of the string is even, then he divide each of the string into two substrings :*
>
>*then he check two cases:*
>
>1. *a1,b1 are equivalent and a2,b2 are equivalent*
>2. *a1,b2 are equivalent and a2,b1 are equivalent*
>
>*We say string a,b are equivalent if at least one of the cases is true
>And for each case, if he want to know whether two strings are equivalent, he need to compare the strings by the rules again.*
* **Input**
>*Contains two lines.
>First line is the string a.
>Second line is the string b.
>The length of the string are the same and form 1~10^3.*
* **Output**
>*Contains one line.
>Print "YES" if the string is equal in Johnny's rule,
>print "NO" otherwise.*
:::
**思路**
>1. 將字串切割(判斷長度為奇或偶數)
>2. 遞迴=>比較字串
>3. 停止=>字串長度為奇數
**程式**
```clike=
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char a[1005];
char b[1005];
//comp也可以用c語言函式庫裡的strcmp或strncmp來寫~
int comp(int al, int ar, int bl, int br)
{
for (int i = al, j = bl; i <= ar, j <= br; i++, j++)
{
if (a[i] != b[j])
return 0;
}
return 1;
}
int count(int al, int ar, int bl, int br)
{
if ((ar - al + 1) % 2)
return comp(al, ar, bl, br);
int am = (al + ar) / 2;
int bm = (bl + br) / 2;
// case1
int s1 = count(al, am, bl, bm);
int s2 = count(am + 1, ar, bm + 1, br);
// case2
int s3 = count(al, am, bm + 1, br);
int s4 = count(am + 1, ar, bl, bm);
if ((s1 && s2) || (s3 && s4))
return 1;
else
return 0;
}
int main()
{
scanf("%s %s", a, b);
int n = strlen(a);
if (count(0, n - 1, 0, n - 1))
printf("YES\n");
else
printf("NO\n");
return 0;
}
```
### 優先運算
:::info
* **敘述**
>將運算子往前移，該如何顯示運算結果
:::
* **思路**
>1. 看到運算子=>準備接收數值
>2. 停止點=>收到數值&return
* **程式**
```clike=
#include <stdio.h>
#include <ctype.h>
char c;
int a, op1, op2;
int read()
{
c = getchar();
if (c == ' ')
return read();
else if (isdigit(c))
{
//把收到的數值吐回到stdin(標準輸入)
ungetc(c, stdin);
scanf("%d", &a);
return a;
}
else if (c == '+')
{
//遞迴處!!!
//op1和op2分別接收接下來的兩個數字
op1 = read();
op2 = read();
return op1 + op2;
}
else if (c == '-')
{
op1 = read();
op2 = read();
return op1 - op2;
}
else if (c == '*')
{
op1 = read();
op2 = read();
return op1 * op2;
}
}
int main()
{
printf("%d\n", read());
return 0;
}
```
* **程式_改成標準寫法**
```clike=
#include <stdio.h>
#include <ctype.h>
int cal(void)
{
int ans, op1, op2;
char c = getchar();
if (c == ' ')
return cal();
// 直接收到數字(吐回去&直接印出來)
else if (isdigit(c))
{
ungetc(c, stdin);
scanf("%d", &ans);
printf("%d", ans);
return ans;
}
// 收到需要處理的值=>遞迴後印出運算
if (c != '*')
printf("(");
op1 = cal();
printf(" %c ", c);
op2 = cal();
if (c != '*')
printf(")");
// 運算最後解答
if (c == '+')
return op1 + op2;
else if (c == '-')
return op1 - op2;
else if (c == '*')
return op1 * op2;
}
int main(void)
{
printf(" = %d\n", cal());
return 0;
}
```
Sign in with Wallet
Connect another wallet