関数が自分を呼び出す再帰。スタックを意識した擬似言語のトレース技法を学びます。
日野 こむぎ
再帰のトレース、あたし頭がこんがらがる…
藤森 さやか 先生
再帰トレースは{kw('スタック', '関数呼び出しを管理するメモリ領域。
再帰でスタックが積まれる')}を意識するのがコツよ。
階乗計算の例で見てみましょう。
○ 手続: factorial(整数型: n)
if (n ≦ 1)
return 1
else
return n × factorial(n - 1)
endif
青木 澪
factorial(4) を呼び出すと、4 × factorial(3) → 4 × 3 × factorial(2) → 4 × 3 × 2 × factorial(1) → 4 × 3 × 2 × 1 = 24 となるの。
桃井 すみれ
スタックって、お皿を積み上げる感じですかぁ?
藤森 さやか 先生
そう、関数呼び出しが「積まれて」いって、最深部から「ベースケース (n≦1)」に達したら、結果を順に返しながら巻き戻る。
これがコールスタックよ。
青木 澪
もう一つ重要な例があるわ。
フィボナッチ数列ね。
○ 手続: fib(整数型: n)
if (n ≦ 1)
return n
else
return fib(n - 1) + fib(n - 2)
endif
青木 澪
fib(5) = fib(4) + fib(3) = (fib(3)+fib(2)) + (fib(2)+fib(1)) = ... と展開できるわ。
同じ計算が何度も呼ばれるから、素朴な再帰は遅いの。
日野 こむぎ
メモ化や動的計画法で高速化するんだったよね!
藤森 さやか 先生
その通り。
試験では再帰の戻り値や呼び出し回数を問われるから、ツリー状に展開して数えるのがコツ。
確認クイズ
上記の factorial(5) の戻り値はいくつか。
- 20
- 60
- 120
- 720
こたえを見る
正解: 3. 120
factorial(5) = 5 × 4 × 3 × 2 × 1 = 120 です。再帰呼び出しが「5×4×3×2×1」と展開されて計算されます。