Scalaでの末尾再帰

投稿日: 2022-10-05 2022-10-13
タグ: Functional Programming

1. 序章

一般的に、再帰の問題は頭と末尾の再帰に分けることができます。再帰が非常に深くなると、ヘッド再帰はスタックオーバーフローエラーのリスクを伴います。

このチュートリアルでは、Scalaの末尾再帰の最適化が、呼び出しスタックを1フレームだけに減らすことで、この問題にどのように対処できるかを示します。

2. リストの長さの計算

末尾再帰と末尾再帰の両方の実装を使用して、リストの長さを計算してみましょう。

サイズNのリストの長さを計算するアルゴリズムを次のように表すことができます。

リストが空の場合は、0を返します
リストが空でない場合は、最初の要素を除いたリストの長さに1を追加します

まず、ヘッド再帰実装を記述しましょう。

def recursiveLength(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => 1 + recursiveLength(tail)
}

この実装は、アルゴリズムをScalaに直訳したものです。 ただし、問題は、呼び出しスタックがひどく深くなり、スタックオーバーフローエラーが発生する可能性があることです。

それが末尾再帰のものとどのように比較されるかを見てみましょう：

@tailrec
def tailRecursiveLength(list: List[String], accumulator: Long): Long = list match {
    case Nil => accumulator
    case head :: tail => tailRecursiveLength(tail, accumulator + 1)
}

ここで、この最後の実装にはいくつかの重要な違いがあります。

@tailrecアノテーションをメソッドに追加する必要があります。これは、コードが末尾呼び出しの最適化でコンパイルされていることを確認するようにコンパイラーに指示します
メソッドの最後の呼び出しは再帰的なものでなければなりません

2番目のポイントは、末尾再帰メソッドを作成するときに最も重要なポイントです。 これを正しく行うと、Scalaはコールスタックを1つのコールに減らすことができます。

2.1. コンパイラのサポート

間違えると、Scalaコンパイラーはエラーを発生させます。

これを示すために、@tailrecアノテーションを元のrecursiveLengthメソッドに追加しましょう。コードをコンパイルすると、次のエラーが表示されます：「@ tailrec注釈付きメソッドrecursiveLengthを最適化できませんでした：テール位置にない再帰呼び出しが含まれています」。

最初の実装が末尾再帰ではない理由は明らかではないように思われるかもしれません。 2番目のパターンマッチをより詳細な方法で書き直して、より明確にしましょう。

def recursiveLengthVerbose(list: List[String]): Long = list match {
    case Nil => 0
    case head :: tail => {
        val accumulator = recursiveLengthVerbose(tail)
        1 + accumulator 
    }
}

ご覧のとおり、最後の呼び出しは再帰的ではありません。幸いなことに、コンパイラはこれをキャッチします。

3. 結論

単純な問題でも、ヘッド再帰実装の限界に達するのは簡単です。末尾再帰の実装はあまり自然に見えないかもしれませんが、特定の状況では間違いなく狙う価値があります。

Scalaコンパイラーは、コードを最適化し、実装が末尾再帰でない場合に警告を発します。それを活用しましょう！

いつものように、コードはGitHubでから入手できます。

getdocs

13036