再帰のトレースのやり方

手順1:止まる条件を先に見つける

自分自身を呼ばずに return している行が、止まる条件（基底条件）です。 例では n ≦ 0 のとき 0 を返して終わります。

先にここを見るのは、どこまで積めばよいかが分かるからです。 n が1ずつ減って 0 になったところで止まるので、f(3)・f(2)・f(1)・f(0) の4段だと先に読めます。

≦ と < の読み違いに注意してください。n < 0 なら f(0) では止まらず、もう1段積むことになります。

手順2:呼び出しを下へ積む

呼び出すたびに1行を足します。書くのは、その呼び出しの引数と、戻ってきたら何をするかです。 戻り値はまだ分からないので、空けておきます。

大事なのは、n の箱が呼び出しごとに別にあることです。 f(2) を呼んでも、f(3) の n は 3 のまま残っています。 n の箱を1つだけ作って 3 → 2 → 1 と書き換えると、戻ってきたときに「f(3) の n」が分からなくなります。 表の1行が、その呼び出し専用の箱です。

手順3:下から上へ戻り値を埋める

一番下の f(0) の戻り値 0 が決まったら、1つ上の行に戻って計算します。上から埋めることはできません。f(3) は f(2) が決まるまで計算できないからです。

f(0) = 0                 ← 一番下から
f(1) = 2 + f(0) = 2 + 0 = 2
f(2) = 4 + f(1) = 4 + 2 = 6
f(3) = 6 + f(2) = 6 + 6 = 12  ← 最後に一番上

f(3) の戻り値は 12 です。手順2の表の「戻り値」の列を、下から順に埋めたことになります。

つまずきやすい形1:処理が呼び出しの前か後か

次の2つは、1行の順番が違うだけです。p(3) と q(3) を呼ぶと、何が出力されるでしょうか。

○p(整数型: n)
  if (n ≦ 0)
    return
  endif
  n を出力する
  p(n - 1)

○q(整数型: n)
  if (n ≦ 0)
    return
  endif
  q(n - 1)
  n を出力する

• ・p(3) は 3, 2, 1。出力が呼び出しの前にあるので、積みながら出力します
• ・q(3) は 1, 2, 3。出力が呼び出しの後ろにあるので、 一番下まで積んでから、戻りながら出力します

q で間違えやすいのは、「q(n - 1) を呼んだら、その呼び出しは終わり」と思ってしまうことです。呼び出しの後ろにある行は、戻ってきたあとに必ず実行されます。手順2の「戻ったらすること」の列には、この行を書いておきます。

つまずきやすい形2:自分を2回呼ぶ

1回の呼び出しの中で自分を2回呼ぶ形は、表が1列に積めません。字下げで木の形に書きます。

○r(整数型: n)
  if (n ≦ 0)
    return
  endif
  r(n - 1)
  n を出力する
  r(n - 1)

r(2) を追うと、こうなります。

r(2)
  r(1)
    r(0) → 止まる
    1 を出力
    r(0) → 止まる
  2 を出力
  r(1)
    r(0) → 止まる
    1 を出力
    r(0) → 止まる

出力は 1, 2, 1 です。 字下げ1段が1つの呼び出しで、1つ目の呼び出しを最後まで追ってから、2つ目に進みます。2つを同時に進めると崩れます。

木構造をたどる問題（左の子をたどる → 自分 → 右の子をたどる）も、この形です。 n が1増えるごとに呼び出しの数がほぼ倍になるので、本番で n が大きいときは、 全部を追わずに小さい n で規則を見つけるほうが速いこともあります。

つまずきやすい形3:引数の順番が入れ替わる

呼び出すときに引数の順番を入れ替える再帰があります。 このときは呼び出しの行ごとに、仮引数と実引数の対応を書きます。

○s(文字列型: x, 文字列型: y, 整数型: n)
  …
  s(y, x, n - 1)   ← 呼ばれた側では x = 元の y、y = 元の x

「呼ばれた側の x は、呼んだ側の何だったか」を毎段書いておかないと、 2段目あたりで x と y が分からなくなります。 ハノイの塔のように引数が3つ以上入れ替わる問題では、この書き出しが一番効きます。

大域変数は、全部の呼び出しで1つ

手順2で「n の箱は呼び出しごとに別」と書きましたが、大域変数（プログラムの冒頭で「大域:」と宣言されたもの）は全部の呼び出しで共有します。どの段で書き換えても、同じ1つの箱が変わります。

配列に結果を足していく問題では、配列は表の外に1つだけ書き、 足した順に「何段目の呼び出しで足したか」を添えておくと、順番を間違えません。

ほかの書き方の基本

変数の書き出し方、分岐と繰り返しの追い方は擬似言語のトレースのやり方に、記号の一覧は擬似言語の記法にまとめています。