末尾再帰の説明

末尾再帰は、関数型プログラムの動作を分析する前に理解しておくべき重要な概念です。 Elm に似た疑似コードを使用して、末尾再帰とは何かを説明します。この記事を理解するのに Elm の知識は必要ありませんが。

再帰から末尾再帰へ

次の関数を検討してください:

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

factorial(4) を展開できます として

  factorial(4)
= if (4 == 0) 1 else 4 * factorial(4 - 1)
= 4 * factorial(4 - 1)
= 4 * factorial(3)
= 4 * (if (3 == 0) 1 else 3 * factorial(3 - 1))
= 4 * 3 * factorial(2)
= ...
= 4 * 3 * 2 * 1 * 1
= 24

内部関数呼び出しの結果に数値を乗算するため、これらの数値 4、3、2、1 を格納する場所が必要です。これらの数値は、スタック フレームに格納されます。 .すべての関数には独自のフレームがあるため、factorial(n) に対して n + 1 個のスタック フレームを作成する必要があります。 .

末尾再帰は、再帰呼び出しのスペース最適化です。ほとんどの最適化とは異なり、メモリ使用量の漸近的な動作を $\mathcal{から変更します。ああ}(ん)O(n)\; から$ \mathcal{O}(1)$$

アキュムレータ - 末尾再帰関数を実装するテクニック

単純な再帰関数をテール再帰関数に変換する優れた手法は、アキュムレータを使用することです。たとえば、これは factorial の末尾再帰バージョンです。 :

factorial: Int -> Int
factorial n =
    let helper acc n =
        if n == 0 then acc else helper (acc * n) (n - 1)
    in
    helper 1 n

アキュムレータを使用することは、ループで常に使用する反復プロセスを意味します。実際、末尾再帰は常に、コンパイラによってループと同じ種類の低レベル コードに変換されます。

継続渡しスタイル

アキュムレータは常に機能しているわけではありません。より複雑な再帰関数を変換するために、継続渡しスタイル (略して CPS) と呼ばれる別の手法があります。これが factorial() です 継続渡しスタイルの関数:

factorial_k: Int -> (Int -> a) -> a
factorial_k n k =
    if n <= 0 then
        k(1)
    else
        factorial_k (n - 1) (\v -> k(v * n))

factorial: Int -> Int
factorial n =
    factorial_k n (\x -> x)

ご覧のとおり、明らかな利点のないボイラープレートがたくさんあります。 CPS で手動でコードを記述するのは面倒でエラーが発生しやすいため、すべての再帰関数を CPS スタイルでコーディングする価値はおそらくありません。一方、通常の機能を CPS に変換するツールもあります。

Elm コンパイラはこのようなコードをまったくコンパイルできず、執筆時点で無限再帰を生成することに注意してください。ただし、この関数を他の言語で試すことはできます。

あとがき

末尾再帰は最適化であるため、すべてのプログラミング言語のすべての実装がそれらを実装するわけではありません。たとえば、この記事の執筆時点では、C++ 標準に必須の末尾呼び出しの削除はありませんが、すべての主流のコンパイラ (MSVC、Clang、および GCC) はいずれにせよそれを行います。関数型プログラミング言語では話が異なります。これらの言語では通常、末尾再帰関数を記述する場合、末尾呼び出しの削除が義務付けられます。その理由は、これらの言語は通常、ループを阻止するか、ループをまったく持たないためです。そのため、多くの場合、まともなパフォーマンスを達成するには末尾呼び出しの除去が必要です。これらの言語で良き市民になるためには、再帰関数を末尾再帰的に書くように努めるべきです (少なくとも、アキュムレータで変換できる簡単なケースでは)。