遞迴

在多數的程式語言裡，是允許函式呼叫自己，這樣的呼叫方式稱為遞迴 (recursion)。遞迴可以讓程式碼較精簡，也是APCS的很重要的考試內容之一。然而，對很多同學而言，遞迴是個不容易理解的概念，尤其是要透過遞迴去解決問題。

• Day21- 黑魔法，recursion，recursion depon (遞迴函數的介紹)
  • python
• Recursive Factorial
  • 計算n階乘的結果

#include <stdio.h>
int factorial(int n){
  if (n <=1)
    return 1;//一定要有不繼續遞迴的中止條件
  else
    return n * factorial(n-1);//呼叫自己
}
main(){
  int n;
  scanf("%d", &n);
  printf("%d", factorial(n));
}

• Recursive Reverse
  • 會用到字串 (陣列會介紹)
• Recursive N-Queens
  • Day22- project2 - 遞迴之經典八皇后問題
  • 你一定會的 N-Queen Problems
  • 會用陣列
• 遞迴/迴圈 求解 最大公因數

觀念題

int f (int n) { int sum=0; if (n<2) { return 0; } for (int i=1; i<=n; i=i+1) { sum = sum + i; } sum = sum + f(2*n/3); return sum; }

函數f 定義如上，如果呼叫f(1000)，指令sum=sum+i 被執行的次數最接近下列何者？ (A) 1000 (B) 3000 (C) 5000 (D) 10000

105年3月 第5題

f(1000) = 1000次 呼叫 f(666) f(666) = 666次 呼叫 f(444) f(444) = 444次 呼叫 f(296) 其實就是1000 + 1000*(2/3) + 1000*(2/3)$^2$ + 1000*(2/3)$^3$…+0 查一下等比級數的公式

void foo (int i) { if (i <= 5) { printf ("foo: %d\n", i); } else { bar(i - 10); } } void bar (int i) { if (i <= 10) { printf ("bar: %d\n", i); } else { foo(i - 5); } } void main() { foo(15106); bar(3091); foo(6693); }

上述程式輸出為何？ (A) bar: 6 bar: 1 bar: 8 (B) bar: 6 foo: 1 bar: 3 (C) bar: 1 foo: 1 bar: 8 (D) bar: 6 foo: 1 foo: 3

105年3月 第14題

• 當數字很大的時候，不太可能真的去算，怎麼辦? 其實呼叫foo也會呼叫bar，呼叫bar也會呼叫foo每一輪會少15，所以 foo(15106) = foo (15*1006 +16) = foo(16)

1. int fun (int n) {
2. int fac = 1;
3. if (n >= 0) {

4. fac = n * fun(n - 1);
   

5. }
6. return fac;
7. }

右側為一個計算n 階層的函式，請問該如何修改才會得到正確的結果？ (A) 第2 行，改為 int fac = n; (B) 第3 行，改為if (n > 0) { (C) 第4 行，改為fac = n * fun(n+1); (D) 第4 行，改為fac = fac * fun(n-1);

105年3月 第20題

解題:

假設n為3，以上程式結果會是? n = 3 fac = 1 fac = 3* fun(2) → 3*0

n = 2 fac = 1 fac = 2fun(1) → 20

n = 1 fac = 1 fac = 1fun(0) → 10

n = 0 fac = 1 fac = 0func(-1) → 01

n = -1 fac = 1 return 1

問題在哪?

int Mystery (int x) { if (x <= 1) { return x; } else { return ____________ ; } } 上述Mystery()函式else 部分運算式應為何，才能使得 Mystery(9) 的回傳值為34。 (A) x + Mystery(x-1) (B) x * Mystery(x-1) (C) Mystery(x-2) + Mystery(x+2) (D) Mystery(x-2) + Mystery(x-1)

105年3月 第25題 解題: (A) 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 45 (B) 9 階乘 (一定大於34) (C) 會沒完沒了 (D) Mystery(7)+Mystery(8)

Mystery(0) = 0 Mystery(1) = 1 Mystery(2) = (0+1) Mystery(3) = (1+1) Mystery(4) = (1+2) Mystery(5) = (2+3)= 5 Mystery(6) = (3+5)= 8 Mystery(7) = (5+8)= 13 Mystery(8) = (8+13)= 21

int a(int n, int m) { if (n < 10) { if (m < 10) { return n + m ; } else { return a(n, m-2) + m ; } } else { return a(n-1, m) + n ; } }

請問以a(13,15)呼叫上列a()函式，函式執行完後其回傳值為何？ (A) 90 (B) 103 (C) 93 (D) 60

105年3月 第7題

int g(int a) { if (a > 1) { return g(a - 2) + 3; } return a; }

給定上列g() 函式，g(13) 回傳值為何？ (A) 16 (B) 18 (C) 19 (D) 22

105年3月 第10題

void f1 (int m) { if (m > 3) { printf ("%d\n", m); return; } else { printf ("%d\n", m); f2(m+2); printf ("%d\n", m); } }

void f2 (int n) { if (n > 3) { printf ("%d\n", n); return; } else { printf ("%d\n", n); f1(n-1); printf ("%d\n", n); } }

給定上列函式 f1() 及 f2()。f1(1)運算過程中，以下敘述何者為錯？ (A) 印出的數字最大的是4 (B) f1 一共被呼叫二次 (C) f2 一共被呼叫三次 (D) 數字2 被印出兩次

105年3月 第12題

int f (int n) { if (n > 3) { return 1; } else if (n == 2) { return (3 + f(n+1)); } else { return (1 + f(n+1)); } }

int g(int n) { int j = 0; for (int i=1; i<=n-1; i=i+1) { j = j + f(i); } return j; }

上列g(4)函式呼叫執行後，回傳值為何？ (A) 6 (B) 11 (C) 13 (D) 14

105年3月 第24題