Corecursion and Recursion in Kotlin

# Corecursion and Recursion

![fig1.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202689/c6d8fef4-b7bc-09b0-b822-9045c0281c95.png)

<img https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202689/c6d8fef4-b7bc-09b0-b822-9045c0281c95.png width=55%>

## それぞれの特徴
- Corecursion
	- Corecursionは、あるステップの出力を次のステップの入力として使用し、先頭から計算処理が行われる。
	- リストの要素を遷移する各ステップで、計算処理が実行される。
- Recursion
	- その逆で、末尾から計算処理が行われる。 
	- 終端条件(ここではリストの末端)に到達するまで、計算処理は行われない。
		- その間skipされていた中間処理はstackに積まれる。

## 実行時に要するスタック
- Corecursion
	- 固定サイズ長のスタック
- Recursion
	- 要素数に比例したスタック

recursionの使用は、扱うデータの長さが事前にわかる場合が望ましい。
そうでない場合は、recursiveな処理ではなく、corecursiveで実装できないか検討する。

# In Kotlin
recursionを扱いやすいように実装されている点がkotlinにはいくつかある。
Tail Call Elimination(末尾呼び出し最適化)や、
関数内に関数を定義できるlocal functionがそれにあたる。

## Tail Call Elimination
![fig2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/202689/ffb66749-65a8-e261-f957-a06bdbd25e95.png)


Corecursionにおいて、
後続の処理で使用されない関数の呼び出し(最後の処理の呼び出し)を、スタックから除去する。（正確にはスタックに積まないようにする？）
kotlinでは、`tailrec`というキーワードを関数の前に付与するだけで、Tali Call Eliminationをおこなってくれる。

### 実例(Sum)
#### RecursiveSum

```kotlin
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
```kotlin
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](https://medium.com/coding-blocks/tail-call-optimization-in-jvm-with-kotlin-ebdf90b34ec9)

によると、

> 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`を使った例のアレ)へ変換してくれる。

```kotlin
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が一つ残されることがわかる。

```kotlin
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);
}
```

# Reference
[The Joy of Kotlin](https://www.manning.com/books/the-joy-of-kotlin)