コトリンと尾の再帰
1前書き
いくつかのアルゴリズムは再帰的な方法で実行されるとき最もよく働きます – 計算が同じ計算のより簡単な形に基づいているところ。
ほとんどのプログラミング言語では、再帰に伴うスタックオーバーフローの危険性があります。戻ることなく、一度に実行できるネストされたメソッド呼び出しの数には制限があります。
これが問題になる場合は、代わりに従来のループを使用して、アルゴリズムを命令的な方法で書き直すことができます。
-
末尾再帰
は、特定の規則が満たされていることを前提として、コンパイラーが再帰的メソッドを命令的な方法で書き換えることができる技法です** 。
2 Kotlinでの尾部再帰の規則
末尾再帰を使用してKotlinで関数を実装するには、従うべき規則が1つあります。この規則は見かけほど単純ではありません。たとえば、階乗の例をとると、これは次のように実装されます。
この規則は見かけほど単純ではありません。たとえば、階乗の例をとると、これは次のように実装されます。
fun recursiveFactorial(n: Long) : Long {
return if (n <= 1) {
n
} else {
n ** recursiveFactorial(n - 1)
}
}
これは完璧に機能します。ただし、末尾再帰には適していません。
分割すると、上記の関数は次のことを行います。
-
n
が1以下の場合はnを返す -
accum = recursiveFactorial(n – 1)
を計算します. -
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)
}
}
これは次のように分類できます。
-
soFar = n ** accum
を計算します. -
n
⇐ 1の場合は
soFar
を返します -
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のコンパイラはこれを自動的に行うことができます – 正しいキーワードを使うだけです。