Corecursion and Recursion
それぞれの特徴
- Corecursion
- Corecursionは、あるステップの出力を次のステップの入力として使用し、先頭から計算処理が行われる。
- リストの要素を遷移する各ステップで、計算処理が実行される。
- Recursion
- その逆で、末尾から計算処理が行われる。
- 終端条件(ここではリストの末端)に到達するまで、計算処理は行われない。
- その間skipされていた中間処理はstackに積まれる。
実行時に要するスタック
- Corecursion
- 固定サイズ長のスタック
- Recursion
- 要素数に比例したスタック
recursionの使用は、扱うデータの長さが事前にわかる場合が望ましい。
そうでない場合は、recursiveな処理ではなく、corecursiveで実装できないか検討する。
In Kotlin
recursionを扱いやすいように実装されている点がkotlinにはいくつかある。
Tail Call Elimination(末尾呼び出し最適化)や、
関数内に関数を定義できるlocal functionがそれにあたる。
Tail Call Elimination
Corecursionにおいて、
後続の処理で使用されない関数の呼び出し(最後の処理の呼び出し)を、スタックから除去する。（正確にはスタックに積まないようにする？）
kotlinでは、tailrecというキーワードを関数の前に付与するだけで、Tali Call Eliminationをおこなってくれる。
実例(Sum)
RecursiveSum
fun sum(n: Int): Int = if (n < 1) 0 else n + sum(n - 1)
==
sum(3)
= 3 + sum(2)
= 3 + (2 + sum(1))
= 3 + (2 + (1 + sum(0))) <= 終端
= 3 + (2 + (1 + 0))
= 3 + (2 + 1)
= 3 + 3
= 6
Recursiveに加算処理を行う。
ただし、この実装は、上述したように、sumが終端条件(n<1)に到達するまで、
各計算処理sum(n:Int)が呼ばれないため、その間の計算処理をスタックに退避させておく必要がある。
CorecursiveSum
fun sum(n:Int): Int {
tailrec fun sum_(s:Int, i:Int):Int = if (i > n) s else sum_(s+i, i+1)
return sum_(0,0)
}
==
sum(3)
= sum_(0,1)
= sum_(1,2)
= sum_(3,3)
= sum_(6,4)
= 6
corecursiveに加算処理を行う。
sum_()が呼び出されるタイミングで計算s+iを実施。
tailrecを用いて、末尾呼び出し最適化を行う。
Tail Call Optimization in JVM with Kotlin
によると、
Kotlin compiler just converts the Tail Call Optimized function to iterative way.
Hence no new stack frame is created.
tailrecを付与することで、kotlin compilerは、
以下の通り、関数をiterativeな形式(forやwhileを使った例のアレ)へ変換してくれる。
public final int sum(final int n) {
<undefinedtype> $fun$sum_$1 = new Function2() {
// $FF: synthetic method
// $FF: bridge method
public Object invoke(Object var1, Object var2) {
return this.invoke(((Number)var1).intValue(), ((Number)var2).intValue());
}
public final int invoke(int s, int i) {
while(i <= n) {
<undefinedtype> var10000 = (<undefinedtype>)this;
int var3 = s + i;
++i;
s = var3;
}
return s;
}
};
return $fun$sum_$1.invoke(0, 0);
}
ちなみに、tailrecを付与しない場合は、以下のようなkotlin bytecodeが生成される。
呼ばれることのないinvokeが一つ残されることがわかる。
public final int sum(final int n) {
<undefinedtype> $fun$sum_$1 = new Function2() {
// $FF: synthetic method
// $FF: bridge method
public Object invoke(Object var1, Object var2) {
return this.invoke(((Number)var1).intValue(), ((Number)var2).intValue());
}
public final int invoke(int s, int i) {
return i > n ? s : ((<undefinedtype>)this).invoke(s + i, i + 1);
}
};
return $fun$sum_$1.invoke(0, 0);
}