Example4.6

4.6 末尾再帰

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

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

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

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

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

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

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


  • お疲れさまです。「評価が進んでもその大きさは定数で・・・」の「定数で」は「一定に」の方が適しているように思います。 -- ryugate (2008-05-19 22:13:10)
  • あちこちのご指摘どうもありがとうございます>ryugateさん。現時点ではとりあえず誤字誤訳も含めてまずは一巡翻訳しようと考えております。その間に皆さんに色々ご指摘頂き、纏めて修正していこうかと。訳語などもどこまで日本語にするかあるいはカタカナにするかなど迷っている箇所が多いので、気軽にアドバイス頂ければと思います。 -- tmiya (2008-05-23 07:06:24)
    名前:
    コメント:

タグ:

+ タグ編集
  • タグ:

このサイトはreCAPTCHAによって保護されており、Googleの プライバシーポリシー利用規約 が適用されます。

最終更新:2011年02月24日 08:32
ツールボックス

下から選んでください:

新しいページを作成する
ヘルプ / FAQ もご覧ください。