再帰で2進数を出力する｜擬似言語のトレース解説と練習問題
手続 toBinary は、1 以上の整数 n を受け取り、自分自身を呼び出しながら値を出力する。
プログラム
| 1 | ○toBinary(整数型: n) |
| 2 | if (n ≧ 2) |
| 3 | toBinary(n ÷ 2 の商) |
| 4 | endif |
| 5 | (n mod 2) を出力する |
何をしているか
n が 2 以上なら、先に n を 2 で割った商で自分自身を呼び出し、戻ってきてから n mod 2 を出力します。結果として、n の2進数表記が上の桁から順に出力されます。
トレースのコツ
- まず、呼出しの引数を下向きに書き出します（例：13 → 6 → 3 → 1）。
- 出力は、いちばん下（最後の呼出し）から上へ戻る順に起こります。
- それぞれの呼出しで
nは別の変数です。戻ってきたとき、nは呼び出す前の値のままです。
よくある間違い
- 呼び出した順（上から）に出力すると考えてしまう。出力の行は再帰呼出しの後ろにあります。
- 戻ってきたあとの
nを、深い呼出しの値と取り違える。 nが 1 のときに出力されないと考える。if の外にあるので、必ず1回出力されます。
例題：toBinary(26) を最後まで追う
上のプログラムを toBinary(26) で呼び出したときの、全ステップのトレース表です。太字は、その文で値が変わった変数です。
| # | 行 | したこと | 手続 | n |
|---|---|---|---|---|
| 1 | 2 | 条件判定（真） | toBinary | 26 |
| 2 | 2 | 条件判定（真） | toBinary | 13 |
| 3 | 2 | 条件判定（真） | toBinary | 6 |
| 4 | 2 | 条件判定（真） | toBinary | 3 |
| 5 | 2 | 条件判定（偽） | toBinary | 1 |
| 6 | 5 | 出力（1） | toBinary | 1 |
| 7 | 3 | 呼出し | toBinary | 3 |
| 8 | 5 | 出力（1） | toBinary | 3 |
| 9 | 3 | 呼出し | toBinary | 6 |
| 10 | 5 | 出力（0） | toBinary | 6 |
| 11 | 3 | 呼出し | toBinary | 13 |
| 12 | 5 | 出力（1） | toBinary | 13 |
| 13 | 3 | 呼出し | toBinary | 26 |
| 14 | 5 | 出力（0） | toBinary | 26 |
この例題で問われること
問 プログラムを実行したとき、出力される値はどれか（複数あるときは出力順）。
答え {1, 1, 0, 1, 0}
- 出力された値は {1, 1, 0, 1, 0} です。
問 5行目を4回目に実行した直後の、変数 n の値はどれか。
答え 13
- 5行目は全部で5回実行されます。
- 実行した直後の n は、順に 1 → 3 → 6 → 13 → 26 です。
- 4回目の直後なので、答えは 13 です。
問 3行目が実行される回数はどれか。
答え 4
- 3行目は4回実行されます。トレース表で 3行目の行を数えると確かめられます。
練習問題 標準（5問）
本試験と同じくらいの量。レベル：中級