Kotlin 再帰と尾再帰

この記事では、再帰関数の作成方法について学びます。自己呼び出しする関数です。また、尾再帰関数についても学びます。

自分自身を呼び出す関数これを再帰関数と呼びます。そして、この技術は再帰と呼ばれます。

物理的な世界の例として、二つの並行する鏡を対向させて配置します。それらの間のどんな物体も再帰的に反射されます。

再帰はプログラミングではどう動作しますか？

fun main(args: Array<String>) {
　　　　...　..　...
　　　　recurse()
　　　　...　..　...
}
fun　recurse()　{
　　　　...　..　...
　　　　recurse()
　　　　...　..　...
}

ここでは、recurse()関数の本体からrecurse()関数を呼び出しています。このプログラムの動作原理は以下の通りです：

ここでは、再帰呼び出しが永遠に続いており、無限再帰に繋がります。

無限再帰を避けるために、再帰呼び出しが行われる一つの枝と再帰呼び出しが行われないもう一つの枝を使用することができます。if ... else（または同様の方法）。

例：再帰を使用して数字の階乗を検索する

fun main(args: Array<String>) {
　　　　val　number　=　4
　　　　val　result:　Long
　　　　result　=　factorial(number)
　　　　println("$number　階乗　=　$result")
}
fun factorial(n: Int): Long {
　　　　return　if　(n　==　1)　n.toLong()　else　n*factorial(n-1)
}

このプログラムを実行すると、出力は以下のようになります：

4　階乗　=　24

このプログラムはどう動作しますか？

factorial()の図は、この関数の再帰呼び出しを説明しています：

以下の手順が関与しています：

factorial(4)　　　　　　　　　　　　　　//　第1次の関数呼び出し、引数:　4
4*factorial(3)　　　　　　　　　　　　//　第2次の関数呼び出し、引数:　3
4*(3*factorial(2))　　　　　　　　//　第3次の関数呼び出し、引数:　2
4*(3*(2*factorial(1))　　　　//　第4次の関数呼び出し、引数:　1　
4*(3*(2*1))　　　　　　　　　　　　　　　　　
24

Kotlinの尾再帰

尾再帰はKotlin言語の特徴ではなく、一般的な概念です。Kotlinを含む一部のプログラミング言語では再帰呼び出しを最適化するために使用されますが、他の言語（例えばPython）ではそれらをサポートしていません。

尾再帰とは何ですか？

通常の再帰では、まずすべての再帰呼び出しを実行し、最後に返り値に基づいて結果を計算します（上記の例のように）。したがって、すべての再帰呼び出しを実行する前に結果は得られません。

尾再帰では、まず計算を実行し、次に再帰呼び出し（再帰呼び出しは現在のステップの結果を次の再帰呼び出しに渡します）を実行します。これにより、再帰呼び出しはループに等価になり、スタックオーバーフローのリスクを避けます。

尾再帰の条件

自身の関数呼び出しが最後の操作である場合、その再帰関数は尾再帰を行うことができます。例えば、

例1：尾再帰の条件に適合していません、なぜなら、自身の関数呼び出し n}}*factorial(n-1)は最後の操作ではありません。

fun factorial(n: Int): Long {
　　　　if (n ==　1) {
　　　　　　　　return n.toLong()
　　　　} else {
　　　　　　　　return n*factorial(n　-　1)　　　　　
　　　　}
}

例2：尾再帰条件に適合しています、なぜなら、自身の関数呼び出しfibonacci(n-1, a+b, a)が最後の操作です。

fun fibonacci(n: Int, a: Long, b: Long): Long {
　　　　return if (n == 0) b else fibonacci(n-1, a+, b, a)
}

Kotlinで尾再帰を実行するためにコンパイラに伝えるために、tailrec修飾子で関数をマークする必要があります。

例：尾再帰

import java.math.BigInteger
fun main(args: Array<String>) {
　　　　val n =　100
　　　　val first = BigInteger("0")
　　　　val second = BigInteger("1",
　　　　println(fibonacci(n, first, second))
}
tailrec fun fibonacci(n: Int, a: BigInteger, b: BigInteger): BigInteger {
　　　　return if (n == 0) a else fibonacci(n-1, b, a+b)
}

このプログラムを実行すると、出力は以下のようになります：

354224848179261915075

このプログラムはフェボナッチ数列の第100項です。出力は非常に大きな整数になる可能性があるため、Java標準ライブラリからBigIntegerクラスをインポートしています。

ここでは、fibonacci()関数がtrarec修飾子でマークされており、この関数は尾再帰呼び出に適しています。そのため、コンパイラはこの場合再帰を最適化します。

尾再帰を使用せずにフェボナッチ数列の第20000項（または他の大整数）では、コンパイラがjava.lang.StackOverflowError例外をスローします。
しかし、私たちの上のプログラムはうまく動作しています。これは尾再帰を使用しているためであり、効率的なループベースのバージョンを使用しているため、従来の再帰を使用していないからです。

例：尾再帰を使用する階乗

上記の例（最初の例）では、数の階乗を計算するための例は尾再帰を最適化することができません。これは同じタスクを実行する別のプログラムです。

fun main(args: Array<String>) {
　　　　val　number　=　5
　　　　println("$number　階乗　=　${factorial(number)}")
}
tailrec　fun　factorial(n:　Int,　run:　Int　=　1):　Long　{
　　　　return　if　(n　==　1)　run.toLong()　else　factorial(n-1,　run*n)
}

このプログラムを実行すると、出力は以下のようになります：

5　階乗=　120

コンパイラはこのプログラムで再帰を最適化できます。再帰関数は尾再帰が可能であり、tailrec修飾子を使用してコンパイラに再帰を最適化することを指示しています。