2つに枝分かれする再帰｜擬似言語のトレース解説と練習問題
関数 f は、自分自身を 2 回呼び出して値を計算する。
プログラム
| 1 | ○整数型: f(整数型: n) |
| 2 | if (n ≦ 1) |
| 3 | return 2 |
| 4 | endif |
| 5 | return f(n － 1) ＋ f(n － 2) |
何をしているか
f(n) は、f(n － 1) と、もう1つ小さい引数での呼出しの和を返します。n が 1 以下になったら、決まった値を返して止まります。
トレースのコツ
- 呼出しを木の形に書きます。
f(5)の下に、呼び出される2つを枝として並べます。 - 葉（
nが 1 以下）に戻り値を書き、下から上へ足し上げます。 - 「条件式が評価される回数」は、木の節の数（呼出しの総数）と同じです。
よくある間違い
- 同じ引数の呼出しを1回分しか数えない。
f(2)が木の中に3回出てくれば、3回実行されます。 - 左の枝だけ計算して、右の枝を忘れる。
- 止まる条件の
n ≦ 1で、nが 0 や負になる場合を見落とす。
例題：f(6) を最後まで追う
上のプログラムを f(6) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | 手続 | n |
|---|---|---|---|---|
| 1 | 2 | 条件判定（偽） | f | 6 |
| 2 | 2 | 条件判定（偽） | f | 5 |
| 3 | 2 | 条件判定（偽） | f | 4 |
| 4 | 2 | 条件判定（偽） | f | 3 |
| 5 | 2 | 条件判定（偽） | f | 2 |
| 6 | 2 | 条件判定（真） | f | 1 |
| 7 | 3 | 戻る（2） | f | 1 |
| 8 | 2 | 条件判定（真） | f | 0 |
| 9 | 3 | 戻る（2） | f | 0 |
| 10 | 5 | 戻る（4） | f | 2 |
| 11 | 2 | 条件判定（真） | f | 1 |
| 12 | 3 | 戻る（2） | f | 1 |
| 13 | 5 | 戻る（6） | f | 3 |
| 14 | 2 | 条件判定（偽） | f | 2 |
| 15 | 2 | 条件判定（真） | f | 1 |
| 16 | 3 | 戻る（2） | f | 1 |
| 17 | 2 | 条件判定（真） | f | 0 |
| 18 | 3 | 戻る（2） | f | 0 |
| 19 | 5 | 戻る（4） | f | 2 |
| 20 | 5 | 戻る（10） | f | 4 |
| 21 | 2 | 条件判定（偽） | f | 3 |
| 22 | 2 | 条件判定（偽） | f | 2 |
| 23 | 2 | 条件判定（真） | f | 1 |
| 24 | 3 | 戻る（2） | f | 1 |
| 25 | 2 | 条件判定（真） | f | 0 |
| 26 | 3 | 戻る（2） | f | 0 |
| 27 | 5 | 戻る（4） | f | 2 |
| 28 | 2 | 条件判定（真） | f | 1 |
| 29 | 3 | 戻る（2） | f | 1 |
| 30 | 5 | 戻る（6） | f | 3 |
| 31 | 5 | 戻る（16） | f | 5 |
| 32 | 2 | 条件判定（偽） | f | 4 |
| 33 | 2 | 条件判定（偽） | f | 3 |
| 34 | 2 | 条件判定（偽） | f | 2 |
| 35 | 2 | 条件判定（真） | f | 1 |
| 36 | 3 | 戻る（2） | f | 1 |
| 37 | 2 | 条件判定（真） | f | 0 |
| 38 | 3 | 戻る（2） | f | 0 |
| 39 | 5 | 戻る（4） | f | 2 |
| 40 | 2 | 条件判定（真） | f | 1 |
| 41 | 3 | 戻る（2） | f | 1 |
| 42 | 5 | 戻る（6） | f | 3 |
| 43 | 2 | 条件判定（偽） | f | 2 |
| 44 | 2 | 条件判定（真） | f | 1 |
| 45 | 3 | 戻る（2） | f | 1 |
| 46 | 2 | 条件判定（真） | f | 0 |
| 47 | 3 | 戻る（2） | f | 0 |
| 48 | 5 | 戻る（4） | f | 2 |
| 49 | 5 | 戻る（10） | f | 4 |
| 50 | 5 | 戻る（26） | f | 6 |
この例題で問われること
問 f(6) を呼び出したときの戻り値はどれか。
答え 26
- 呼出しは全部で25回行われます。
- 奥の呼出しから順に 2 → 2 → 4 → 2 → 6 → … → 2 → 2 → 4 → 10 → 26 を返し、最後に返る 26 が答えです。
問 2行目の条件式が評価される回数はどれか。
答え 25
- 2行目の条件式は25回評価され、真が13回、偽が12回です。
問 3行目が実行される回数はどれか。
答え 13
- 3行目が実行されるのは、2行目の条件が真になったときだけです。
- 2行目の条件は25回評価され、真になるのは13回です。したがって 3行目は13回実行されます。
練習問題 標準（5問）
本試験と同じくらいの量。レベル：中級