4.6 末尾再帰

与えられた２つの数の最大公約数を計算する、次の関数について考えてみましょう。

def gcd(a: Int, b: Int): Int = if (b == 0) a else gcd(b, a % b)

関数評価の置き換えモデルを用いると、gcd(14, 21) は次のように評価されます。

gcd(14, 21) → if (21 == 0) 14 else gcd(21, 14 % 21) → if (false) 14 else gcd(21, 14 % 21) → gcd(21, 14 % 21) → gcd(21, 14) → if (14 == 0) 21 else gcd(14, 21 % 14) → → gcd(14, 21 % 14) → gcd(14, 7) → if (7 == 0) 14 else gcd(7, 14 % 7) → → gcd(7, 14 % 7) → gcd(7, 0) → if (0 == 0) 7 else gcd(0, 7 % 0) → → 7

もう一つの再帰関数 factorial の評価と比較して下さい。

def factorial(n: Int): Int = if (n == 0) 1 else n * factorial(n - 1)

factorial(5) の適用は次のように書き換えます。

factorial(5) → if (5 == 0) 1 else 5 * factorial(5 - 1) → 5 * factorial(5 - 1) → 5 * factorial(4) → . . . → 5 * (4 * factorial(3)) → . . . → 5 * (4 * (3 * factorial(2))) → . . . → 5 * (4 * (3 * (2 * factorial(1)))) → . . . → 5 * (4 * (3 * (2 * (1 * factorial(0)))) → . . . → 5 * (4 * (3 * (2 * (1 * 1)))) → . . . → 120

２つの書き換え列には重要な違いがあります。gcd の書き換え列の項は、同じ形を繰り返しています。評価が進んでもその大きさは一定に抑えられています。対照的に factorial の評価では、オペランドの列はどんどん長くなり、評価列の最後でそれらは掛け合わされます。

Scala の実際の実装が項書き換えで行われていないとしても、やはり、書き換え列と同様の空間的な振る舞いをします。gcd の実装をみると、gcd の再帰呼び出しは評価本体の最後のアクションであることに気付きます。gcd は「末尾再帰的」だとも呼ばれます。末尾再帰関数の最後の呼び出しは、関数の先頭への戻りジャンプとして実装できます。その呼び出しの引数は、gcd の現在のインスタンスのパラメータを上書きできるので、新しいスタック空間を必要としません。ですから末尾再帰関数は繰り返し処理であり、一定の空間で実行できます。

対照的に factorial の再帰呼び出しでは、掛け算があとで施されます。ですから新しいスタックフレームが factorial の再帰インスタンス用に割り当てられ、インスタンス終了後に割り当てが除かれます。この階乗関数の設計は末尾再帰的ではありません。実行するには入力パラメータに比例した空間が必要となります。

より一般的には、もし関数の最後のアクションが他の (同じでも可) 関数の呼び出しであれば、両方の関数は一つのスタックフレームだけで充分です。そのような呼び出しは「末尾呼び出し(tail call)」と呼ばれます。原理的には、末尾呼び出しは常に呼び出した関数のスタックフレームを再利用できます。しかし (Java VM のような) いくつかの実行時環境では、末尾呼び出しでのスタックフレーム再利用を効率化するプリミティブに欠けています。ですから製品品質の Scala の実装では、直接的な末尾再帰(最後のアクションが自分自身の呼び出しとなる再帰)のスタックフレーム再利用だけが要求されています。他の末尾呼び出しも最適化されるかもしれませんが、多くの実装でそうなるということは、当てにすべきではありません。

演習 4.6.1 factorial の末尾再帰版をデザインしなさい。