開発者ドキュメント

コトリンと尾の再帰


1前書き

いくつかのアルゴリズムは再帰的な方法で実行されるとき最もよく働きます – 計算が同じ計算のより簡単な形に基づいているところ。

ほとんどのプログラミング言語では、再帰に伴うスタックオーバーフローの危険性があります。戻ることなく、一度に実行できるネストされたメソッド呼び出しの数には制限があります。

これが問題になる場合は、代わりに従来のループを使用して、アルゴリズムを命令的な方法で書き直すことができます。


  • 末尾再帰

    は、特定の規則が満たされていることを前提として、コンパイラーが再帰的メソッドを命令的な方法で書き換えることができる技法です** 。


2 Kotlinでの尾部再帰の規則

末尾再帰を使用してKotlinで関数を実装するには、従うべき規則が1つあります。この規則は見かけほど単純ではありません。たとえば、階乗の例をとると、これは次のように実装されます。

この規則は見かけほど単純ではありません。たとえば、階乗の例をとると、これは次のように実装されます。

fun recursiveFactorial(n: Long) : Long {
    return if (n <= 1) {
        n
    } else {
        n **  recursiveFactorial(n - 1)
    }
}

これは完璧に機能します。ただし、末尾再帰には適していません。

分割すると、上記の関数は次のことを行います。


  1. n

    が1以下の場合はnを返す


  2. accum = recursiveFactorial(n – 1)

    を計算します.


  3. n ** accum

    を返す

そのように書かれて、あなたは再帰呼び出しが関数の最後の呼び出しではないことがわかります。


3テール再帰として階乗の実装

代わりに、末尾再帰を使用して階乗関数を実装するには、計算が実行される場所を変更するためにそれを作り直す必要があります。

乗算は

の後ではなく、再帰呼び出しの前に行われるようにする必要があります。これは、部分的な結果をパラメータとして渡すことによって最も簡単に行われます。

fun factorial(n: Long, accum: Long = 1): Long {
    val soFar = n **  accum
    return if (n <= 1) {
        soFar
    } else {
        factorial(n - 1, soFar)
    }
}

これは次のように分類できます。


  1. soFar = n ** accum

    を計算します.


  2. n

    ⇐ 1の場合は

    soFar

    を返します


  3. n – 1



    soFar

    を渡して、

    factorial

    関数を呼び出します.

今回は、再帰呼び出しがプロセスの最後のステップです。

正しい形式の再帰関数を作成したら、

tailrec

キーワードを使用して** Kotlinに末尾再帰について考慮するように指示します。これは、可能であれば、関数をループとして書き換えることが許可されていることをコンパイラーに通知します。このキーワードは関数自体に適用されるので、次のようになります。

tailrec fun factorial(n: Long, accum: Long = 1): Long


4階乗のコンパイル出力

これの目的は、スタックオーバーフローの問題を回避するために命令的な方法で実行される再帰コードを書くことです。上記の関数を逆コンパイルすると、コンパイラによって生成された結果は本当に不可欠であることがわかります。

public final long factorial(long n, long accum) {
   while(n > (long) 1) {
      long var10000 = n - (long)1;
      accum = n **  accum;
      n = var10000;
   }

   return n **  accum;
}

これがどのように機能するかをすぐに確認でき、このコードでスタックオーバーフローの危険性が絶対にないことを確認できます。

** 5パフォーマンスの向上

安全性の向上だけでなく、この最適化を使用してパフォーマンスが向上することもあります。これらの利点は、再帰の深さや計算の複雑さなど、他の要因によって異なります。

  • 改善は、メソッド呼び出しが単なるループよりも高価であるという事実から来ています。

階乗の例をもう一度使用して、実行と比較にかかる時間を測定できます。

  • 末尾再帰なしで

    factorial(50)

    1,000,000回を計算する

〜70msかかります
** 末尾再帰を伴う

factorial(50)

1,000,000回の計算

〜45ms

単純なベンチマークを使用すると、36%のスピードアップが得られました。これは、コンパイラが実装を再作業できるようにするためだけに重要です。

これらの測定は、単純な関数の非常に単純なベンチマークによるものです。実際の業績の変化は状況によって異なりますので、決定を下す前に必ず測定する必要があります。


6. 概要

いくつかのシナリオでは、末尾再帰は、安全性とパフォーマンスの両方に関して、私たちのコードにいくつかの重要な利点を与えることができます。 Kotlinのコンパイラはこれを自動的に行うことができます – 正しいキーワードを使うだけです。

モバイルバージョンを終了