【Kotlin】末尾再帰で10種類のアルゴリズムを実装する

この記事は[MicroAd Advent Calendar](https://qiita.com/advent-calendar/2018/microad)の23日目の記事です。

## 続き
- [【Kotlin】6つのアルゴリズムで通常実装と末尾再帰による実装を比較する \- Qiita](https://qiita.com/wrongwrong/items/cf41b9d3f6f3b2eca1f0)

## TL;DR
末尾再帰最適化を効かせてアルゴリズムを10種類実装します。
この記事で実装している内容＋一部アルゴリズムのループによる実装＋テストコードを以下に上げています。

- [k163377/TailrecSamples](https://github.com/k163377/TailrecSamples)

## 前書き
先輩が書いた[Scalaではじめる末尾再帰](https://qiita.com/dashiishida/items/c20d6e08a260e3ce0f64)に影響を受けたので、Kotlin + 末尾再帰で以下の10種類のアルゴリズムを実装してみました。

1. 階乗
2. ユークリッドの互除法
3. フィボナッチ数
4. 累乗（バイナリ法）
5. 反復法（ニュートン法）
6. 基数ソート
7. 黄金比
8. 偶奇判定
9. マッカーシーの91関数
10. アッカーマン関数

### 注意書き
~~面倒だったので~~本質的な部分にフォーカスするため、雑に実装しています。各実装に関する説明は脚注をご覧ください。

## 階乗/ユークリッドの互除法/フィボナッチ数
再帰といえば必ず出てくるアルゴリズムから3つを実装しました。
### 1. 階乗
```kotlin:fact
tailrec fun fact(n: BigInteger, ans: BigInteger = BigInteger.ONE): BigInteger {
    if(n.compareTo(BigInteger.ONE) < 1) return ans
    return fact(n.dec(), ans * n)
}
```

### 2. ユークリッドの互除法
```kotlin:gcd
tailrec fun gcd(a: Int, b: Int): Int{
    if(b == 0) return a
    return gcd(b, a%b)
}
```

### 3. フィボナッチ数[^fibo]
[^fibo]: この実装はn=1項目を0と置いて（=引数は1以上を想定して）います。
```kotlin:fib
tailrec fun fib(n: BigInteger, a: BigInteger = BigInteger.ZERO, b: BigInteger = BigInteger.ONE): BigInteger{
    if(n == BigInteger.ONE) return a
    return fib(n.dec(), b, a+b)
}
```

## 累乗/反復法/基数ソート
ループで実装するような内容ですが、末尾再帰を用いて実装しました。
これらのアルゴリズムはループを使って実装すると状態管理が面倒ですが、末尾再帰で実装するとその辺りの管理が楽になります。

### 4. 累乗（バイナリ法）[^bin]
[^bin]: 自分のブログに[解説記事](https://wrongwrong163377.hatenablog.com/entry/2018/12/11/003000)を書いています。

```kotlin:pow
tailrec fun pow(a: BigInteger, n: Int, ans: BigInteger = BigInteger.ONE): BigInteger{
    if(n == 0) return ans
    return pow(a * a,  n.ushr(1),  if(n.and(1) == 1) ans * a else ans)
}
```

### 5. 反復法（ニュートン法）[^loop]
[^loop]: この章は[自分のブログ](https://wrongwrong163377.hatenablog.com/entry/2018/12/12/003000)を元に書いています。反復法の実用上は最大反復回数も書く必要がありますが、今回は飛ばしています。
```kotlin:newton
tailrec fun newton(
    f: (Double)-> Double,
    df: (Double)-> Double,
    x: Double,
    eps: Double = Float.MIN_VALUE.toDouble()
): Double {
    val xnew = x - f(x) / df(x)
    if(abs(xnew - x) < eps) return xnew
    return newton(f, df, xnew, eps)
}
```
#### 汎化
反復法は$x_k$と漸化式（と閾値）があれば成り立つので、以下のような形に置き直すことができます。

```kotlin:iteration
tailrec fun iteration(
    r: (Double)-> Double,
    x: Double,
    eps: Double = Float.MIN_VALUE.toDouble()
): Double {
    val xnew = r(x)
    if(abs(xnew - x) < eps) return xnew
    return iteration(r, xnew, eps)
}
```

### 6. 基数ソート[^rad]
[^rad]: 符号無し整数にのみ適用可能な実装です。
```kotlin:radixSort
tailrec fun radixSort(list: List<UInt>, mask: UInt = 1u): List<UInt> {
    if (mask == 0u) return list
    val small = ArrayList<UInt>()
    val big = ArrayList<UInt>()
    list.forEach {
        if(it and mask == 0u) small.add(it) else big.add(it)
    }
    small.addAll(big)
    return radixSort(small, mask.shl(1))
}
```

## トランポリンを用いた末尾再帰最適化[^torampoline]
相互再帰や戻り値を使うような再帰などは通常末尾再帰最適化が効きませんが、トランポリンを用いることで末尾再帰として書くことができます。
トランポリンは[Arrowというライブラリのもの](https://wrongwrong163377.hatenablog.com/entry/2018/12/22/195035)を使用しています。
[^torampoline]: トランポリンとその使い方は[こちらの記事](https://qiita.com/torao@github/items/4b224489c71bf460ad7c)を参考にさせていただきました。

### 7. 黄金比[^golden]

[^golden]: 黄金比の計算は[こちらの記事](https://waman.hatenablog.com/entry/20120506/1336272430)を参考にさせていただきました。
```kotlin:goldenRatio
fun goldenRatio(n: Int): TrampolineF<Double> = when(n < 1){
    true -> Trampoline.done(1.0)
    else -> Trampoline.defer { goldenRatio(n-1) }.map{ 1.0 + (1/it) }
}

fun main(){ println(goldenRatio(10000).runT()) }
```
### 8. 偶奇判定
```kotlin:Even-Odd
fun odd(n: Int): TrampolineF<Boolean> = when (n) {
    0 -> Trampoline.done(false)
    else ->  Trampoline.defer { even(n - 1) }
}
fun even(n: Int): TrampolineF<Boolean> = when (n) {
    0 -> Trampoline.done(true)
    else -> Trampoline.defer { odd(n - 1) }
}

fun main(){
    println(even(10000).runT())
    println(odd(10000).runT())
}
```
### 9. マッカーシーの91関数[^mac]
[^mac]: トランポリンを用いる場合、ものすごく再帰回数が多くなる（自分の環境では$n=-1000000000$とか）状態で実行すると`java.lang.OutOfMemoryError: Java heap space`になります。

```kotlin:mac
fun mc(n: Int): TrampolineF<Int> = when(n > 100){
    true -> Trampoline.done(n - 10)
    else -> Trampoline.defer { mc(n + 11) }.map{ mc(it).runT() }
}

fun main(){ println(mc(-1000000).runT()) }
```

### 10. アッカーマン関数
```kotlin:ack
fun ack(m: Int, n: Int): TrampolineF<Int> {
    if (m == 0) return Trampoline.done(n + 1)
    if (n == 0) return Trampoline.defer { ack(m-1, 1) }
    return Trampoline.defer { ack(m, n-1) }.map{ ack(m-1, it).runT() }
}

fun main(){ println(ack(3, 10).runT()) }
```

## 感想
実装を進めていくことで、そもそも言語仕様を深く把握しきれていなかったこと、関数型言語でよく使うような概念を把握できていないことなどに気づけたので、いい経験になったなと思います。
トランポリン関連の実装で用いたArrowは、書いている途中で存在を知ったため、動作の仕組みや実装について調べきることができませんでした。こちらも後で調査してみたいですね。