基本情報技術者講座
★ 猫本 4-09 プログラムの属性(その2) ★
基本情報技術者 令和元年度秋期 問11
自然数nに対して，次のように再帰的に定義される関数f(n)を考える。f(5)の値はどれか。
f(n)：if n≦1 then return 1 else return n＋f(n－1)
| ア | 6 |
| イ | 9 |
| ウ | 15 |
| エ | 25 |
解説
(頭の準備体操)
再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)
| f(5)＝5＋f(4) | f(5)＝5＋10＝15(正解) | |
| ↓ | ↑ | |
| f(4)＝4＋f(3) | f(4)＝4＋6＝10 | |
| ↓ | ↑ | |
| f(3)＝3＋f(2) | f(3)＝3＋3＝6 | |
| ↓ | ↑ | |
| f(2)＝2＋f(1) | f(2)＝2＋1＝3 | |
| ↓ | ↑ | |
| f(1)＝1 | → | ↑ |
よって，ウである。
解答
ウ
基本情報技術者 平成29年度春期 問6
関数 f(x，y)が次のように定義されているとき，f(775，527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。
f(x，y): if y = 0 then return x else return f(y，x mod y)
| ア | 0 |
| イ | 31 |
| ウ | 248 |
| エ | 527 |
解説
(頭の準備体操)
再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)
f(775,527)＝f(527,775 mod 527)＝f(527,248)
f(527,248)＝f(248,527 mod 248)＝f(248,31)
f(248,31)＝f(31,248 mod 31)＝f(31,0)
f(31,0)
ここで，y＝0であることから，x＝31を返す。
よって，イである。
解答
イ
基本情報技術者 平成28年度秋期 問7
整数x，y(x＞y≧0)に対して，次のように定義された関数F(x，y)がある。F(231，15)の値は幾らか。ここで，x mod y はxをyで割った余りである。
| ア | 2 |
| イ | 3 |
| ウ | 5 |
| エ | 7 |
解説
(頭の準備体操)
再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)
F(231,15)＝F(15,231 mod 15)＝F(15,6)
F(15,6)＝F(6,15 mod 6)＝F(6,3)
F(6,3)＝F(3,6 mod 3)＝F(3,0)
F(3,0)
ここで，y＝0であるとこから，x＝3を返す。
よって，イである。
解答
イ
基本情報技術者 平成28年度春期 問7
nの階乗を再帰的に計算する関数 F(n) の定義において，aに入れるべき式はどれか。ここで，nは非負の整数である。
n＞0のとき， F(n)＝【 a 】
n＝0のとき， F(n)＝1
| ア | n＋F(n－1) |
| イ | n－1＋F(n) |
| ウ | n×F(n－1) |
| エ | (n－1)×F(n) |
解説
(頭の準備体操)
再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)
検証するデータを想定する(3回ぐらい試せば傾向が見えてくる)。
3!(3の階乗)は，3×2×1＝6
| ア | F(3)＝3＋F(2) | F(3)＝3＋4＝7 | |
| ↓ | ↑ | ||
| F(2)＝2＋F(1) | F(2)＝2＋2＝4 | ||
| ↓ | ↑ | ||
| F(1)＝1＋F(0) | F(1)＝1＋1＝2 | ||
| ↓ | ↑ | ||
| F(0)＝1 | → | ↑ |
| イ | F(3)＝2＋F(3)＝2＋(2＋F(3))・・・・ 永遠に続く |
| ウ | F(3)＝3×F(2) | F(3)＝3×2＝6(正解) | |
| ↓ | ↑ | ||
| F(2)＝2×F(1) | F(2)＝2×1＝2 | ||
| ↓ | ↑ | ||
| F(1)＝1×F(0) | F(1)＝1×1＝1 | ||
| ↓ | ↑ | ||
| F(0)＝1 | → | ↑ |
| エ | F(3)＝2×F(3)＝2＋(2×F(3))・・・・ 永遠に続く |
よって，ウである。
解答
ウ
基本情報技術者 平成31年春期 問6
三つのスタックA，B，Cのいずれの初期状態も[1，2，3]であるとき，再帰的に定義された関数f()を呼び出して終了した後のBの状態はどれか。 ここで，スタックが，[a1，a2，…，an-1] の状態のときにanをpushした後のスタックの状態は[a1，a2，…，an-1，an]で表す。
f(){
Aが空ならば{
何もしない。
}
そうでない場合{
Aからpopした値をCにpushする。
f()を呼び出す。
Cからpopした値をBにpushする。
}
}
| ア | [1，2，3，1，2，3] |
| イ | [1，2，3，3，2，1] |
| ウ | [3，2，1，1，2，3] |
| エ | [3，2，1，3，2，1] |
解説
(頭の準備体操)
再帰的：「手続の内部から自分自身を呼び出すことができる。」(FE27.1.07)
| ① | A[1，2] | B[1，2，3] | C[1，2，3，3] |
| ② | A[1] | B[1，2，3] | C[1，2，3，3，2] |
| ③ | A[] | B[1，2，3] | C[1，2，3，3，2，1] |
| ④ | A[] | B[1，2，3] | C[1，2，3，3，2，1] |
| ⑤ | A[] | B[1，2，3，1] | C[1，2，3，3，2] |
| ⑥ | A[] | B[1，2，3，1，2] | C[1，2，3，3] |
| ⑦ | A[] | B[1，2，3，1，2，3] | C[1，2，3] |
よって，アである。
解答
ア