# APCS 觀念題 - 遞迴
###### tags: `APCS`
## 第 1 題
給定下方函式 `f()`，已知 `f(14)`、`f(10)`、`f(6)` 分別回傳 25、18、10，函式中的 (?) 應為下列何者？
```c
int f(int n)
{
if (n < 2)
{
return n;
}
else
{
return (n + f(___(?)___));
}
}
```
(A) `(n + 1) / 2`
(B) `n / 2`
\(C\) `(n - 1) / 2`
(D) `(n / 2) + 1`
<!-- B -->
## 第 2 題
函數 `f()` 定義如下，如果呼叫 `f(1000)`，指令 `sum = sum + i` 被執行的次數最接近下列何者？
```c
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;
}
```
(A) 1000
(B) 3000
\(C\) 5000
(D) 10000
<!-- B -->
## 第 3 題
請問以 `a(13, 15)` 呼叫下方 `a()` 函式，函式執行完後其回傳值為何？
```c
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) 90
(B) 103
\(C\) 93
(D) 60
<!-- B -->
## 第 4 題
給定下方 `g()` 函式，`g(13)` 回傳值為何？
```c
int g(int a)
{
if (a > 1)
{
return g(a - 2) + 3;
}
return a;
}
```
(A) 16
(B) 18
\(C\) 19
(D) 22
<!-- C -->
## 第 5 題
給定下方函式 `f1()` 及 `f2()`。`f1(1)` 運算過程中，以下敘述何者為錯？
```c
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);
}
}
```
(A) 印出的數字最大的是 4
(B) `f1` 一共被呼叫二次
\(C\) `f2` 一共被呼叫三次
(D) 數字 2 被印出兩次
<!-- C -->
## 第 6 題
下方程式輸出為何？
```c
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
```
<!-- A -->
## 第 7 題
給定下方函式 `f()`，當執行 `f(10)` 時，最終回傳結果為何？
```c
int f(int i)
{
if (i > 0)
if (((i / 2) % 2) == 0)
return f(i - 2) * i;
else
return f(i - 2) * (-i);
else
return 1;
}
```
(A) 1
(B) 3840
\(C\) -3840
(D)執行時導致無窮迴圈，不會停止執行
<!-- C -->
## 第 8 題
下方為一個計算 n 階層的函式，請問該如何修改才會得到正確的結果？
```c=
int fun(int n) {
int fac = 1;
if (n >= 0) {
fac = n * fun(n - 1);
}
return fac;
}
```
(A) 第 2 行，改為 `int fac = n;`
(B) 第 3 行，改為 `if (n > 0) {`
\(C\) 第 4 行，改為 `fac = n * fun(n + 1);`
(D) 第 4 行，改為 `fac = fac * fun(n - 1);`
<!-- B -->
## 第 9 題
下方 `g(4)` 函式呼叫執行後，回傳值為何？
```c
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;
}
```
(A) 6
(B) 11
\(C\) 13
(D) 14
<!-- C -->
## 第 10 題
下方 `Mystery()` 函式 `else` 部分運算式應為何，才能使得 `Mystery(9)` 的回傳值為 `34`？
```c
int Mystery(int x)
{
if (x <= 1)
{
return x;
}
else
{
return ___(?)___;
}
}
```
(A) `x + Mystery(x - 1)`
(B) `x * Mystery(x - 1)`
\(C\) `Mystery(x - 2) + Mystery(x + 2)`
(D) `Mystery(x - 2) + Mystery(x - 1)`
<!-- D -->
## 第 11 題
給定下方 `G()`, `K()` 兩函式，執行 `G(3)` 後所回傳的值為何？
```c
int K(int a[], int n)
{
if (n >= 0)
return (K(a, n - 1) + a[n]);
else
return 0;
}
int G(int n)
{
int a[] = {5, 4, 3, 2, 1};
return K(a, n);
}
```
(A) 5
(B) 12
\(C\) 14
(D) 15
<!-- C -->
## 第 12 題
下方函式以 `F(7)` 呼叫後回傳值為 12，則 `<condition>` 應為何？
```c
int F(int a)
{
if (<condition>)
return 1;
else
return F(a - 2) + F(a - 3);
}
```
(A) a < 3
(B) a < 2
\(C\) a < 1
(D) a < 0
<!-- D -->
## 第 13 題
下方主程式執行完三次 `G()` 的呼叫後，`p` 陣列中有幾個元素的值為 0？
```c
int K(int p[], int v)
{
if (p[v] != v)
{
p[v] = K(p, p[v]);
}
return p[v];
}
void G(int p[], int l, int r)
{
int a = K(p, l), b = K(p, r);
if (a != b)
{
p[b] = a;
}
}
int main(void)
{
int p[5] = {0, 1, 2, 3, 4};
G(p, 0, 1);
G(p, 2, 4);
G(p, 0, 4);
return 0;
}
```
(A) 1
(B) 2
\(C\) 3
(D) 4
<!-- C -->
## 第 14 題
給定下方 `G()` 函式，執行 `G(1)` 後所輸出的值為何？
```c
void G(int a)
{
printf("%d ", a);
if (a >= 3)
return;
else
G(a + 1);
printf("%d ", a);
}
```
(A) 1 2 3
(B) 1 2 3 2 1
\(C\) 1 2 3 3 2 1
(D) 以上皆非
<!-- B -->
## 第 15 題
下方程式執行後輸出為何？
```c
int G(int B)
{
B = B * B;
return B;
}
int main()
{
int A = 0, m = 5;
A = G(m);
if (m < 10)
A = G(m) + A;
else
A = G(m);
printf("%d \n", A);
return 0;
}
```
(A) 0
(B) 10
\(C\) 25
(D) 50
<!-- D -->
## 第 16 題
下方 `G()` 應為一支遞迴函式，已知當 `a` 固定為 `2`，不同的變數 `x` 值會有不同的回傳值如下表所示。請找出 `G()` 函式中 `(a)` 處的計算式該為何？
```c
int G(int a, int x)
{
if (x == 0)
return 1;
else
return ___(a)___;
}
```
|a 值|x 值|G(a, x) 回傳值|
|-|-|-|
|2|0|1|
|2|1|6|
|2|2|36|
|2|3|216|
|2|4|1296|
|2|5|7776|
(A) `((2 * a) + 2) * G(a, x - 1)`
(B) `(a + 5) * G(a - 1, x - 1)`
\(C\) `((3 * a) - 1) * G(a, x - 1)`
(D) `(a + 6) * G(a, x - 1)`
<!-- A -->
## 第 17 題
下方 `G()` 為遞迴函式，`G(3, 7)` 執行後回傳值為何？
```c
int G(int a, int x)
{
if (x == 0)
return 1;
else
return (a * G(a, x - 1));
}
```
(A) 128
(B) 2187
\(C\) 6561
(D) 1024
<!-- B -->
## 第 18 題
下方函式若以 `search(1, 10, 3)` 呼叫時， `search` 函式總共會被執行幾次？
```c
void search(int x, int y, int z)
{
if (x < y)
{
t = ceiling((x + y) / 2);
if (z >= t)
search(t, y, z);
else
search(x, t - 1, z);
}
}
// 註：ceiling() 為無條件進位至整數位。例如 ceiling(3.1) = 4, ceiling(3.9) = 4。
```
(A) 2
(B) 3
\(C\) 4
(D) 5
<!-- C -->
## 第 19 題
給定函式 `A1()`、 `A2()` 與 `F()` 如下，以下敘述何者有誤？
```c
void A1(int n)
{
F(n / 5);
F(4 * n / 5);
}
void A2(int n)
{
F(2 * n / 5);
F(3 * n / 5);
}
void F(int x)
{
int i;
for (i = 0; i < x; i = i + 1)
printf("*");
if (x > 1)
{
F(x / 2);
F(x / 2);
}
}
```
(A) `A1(5)` 印的 \* 個數比 `A2(5)` 多
(B) `A1(13)` 印的 \* 個數比 `A2(13)` 多
\(C\) `A2(14)` 印的 \* 個數比 `A1(14)` 多
(D) `A2(15)` 印的 \* 個數比 `A1(15)` 多
<!-- D -->
## 第 20 題
下方 `F()` 函式回傳運算式該如何寫，才會使得 `F(14)` 的回傳值為 `40` ?
```c
int F(int n)
{
if (n < 4)
return n;
else
return ___(?)___;
}
```
(A) `n * F(n - 1)`
(B) `n + F(n - 3)`
\(C\) `n - F(n - 2)`
(D) `F(3n + 1)`
<!-- B -->
## 第 21 題
若以 `B(5, 2)` 呼叫下方 `B()` 函式，總共會印出幾次 "base case"？
```c
int B(int n, int k)
{
if (k == 0 || k == n)
{
printf("base case\n");
return 1;
}
return B(n - 1, k - 1) + B(n - 1, k);
}
```
(A) 1
(B) 5
\(C\) 10
(D) 19
<!-- C -->
## 第 22 題
若以 `G(100)` 呼叫下方函式後，`n` 的值為何?
```c
int n = 0;
void K(int b)
{
n = n + 1;
if (b % 4)
K(b + 1);
}
void G(int m)
{
for (int i = 0; i < m; i = i + 1)
{
K(i);
}
}
```
(A) 25
(B) 75
\(C\) 150
(D) 250
<!-- D -->
## 第 23 題
若以 `F(15)` 呼叫下方 `F()` 函式，總共會印出幾行數字？
```c
void F(int n)
{
printf("%d\n", n);
if ((n % 2 == 1) && (n > 1))
{
return F(5 * n + 1);
}
else
{
if (n % 2 == 0)
return F(n / 2);
}
}
```
(A) 16 行
(B) 22 行
\(C\) 11 行
(D) 15 行
<!-- D -->
## 第 24 題
若以 `F(5, 2)` 呼叫下方 `F()` 函式，執行完畢後回傳值為何?
```c
int F(int x, int y)
{
if (x < 1)
return 1;
else
return F(x - y, y) + F(x - 2 * y, y);
}
```
(A) 1
(B) 3
\(C\) 5
(D) 8
<!-- C -->
----
## 解答
|1|2|3|4|5|
|-|-|-|-|-|
|B|B|B|C|C|
|6|7|8|9|10|
|-|-|-|-|-|
|A|C|B|C|D|
|11|12|13|14|15|
|-|-|-|-|-|
|C|D|C|B|D|
|16|17|18|19|20|
|-|-|-|-|-|
|A|B|C|D|B|
|21|22|23|24|25|
|-|-|-|-|-|
|C|D|D|C|-|
[<< APCS 觀念題 - 函式與變數作用域](https://hackmd.io/@kaeteyaruyo/APCS-concept-function) | [目錄](https://hackmd.io/@kaeteyaruyo/APCS-concept-index) | [APCS 觀念題 - 演算法與資料結構 >>](https://hackmd.io/@kaeteyaruyo/APCS-concept-advanced)
Sign in with Wallet
Connect another wallet