【Kotlin】6つのアルゴリズムで通常実装と末尾再帰による実装を比較する

この記事は【Kotlin】末尾再帰で10種類のアルゴリズムを実装する - Qiitaの続きです。

TL;DR

前回の記事でやっていた末尾再帰の実装を、ループを使った実装と比較します。
前回の内容＋今回の内容＋テストコードを以下に上げています。

• k163377/TailrecSamples

比較するアルゴリズム

この記事で比較するアルゴリズムは以下の6つです。

1. 階乗
2. ユークリッドの互除法
3. フィボナッチ数
4. 累乗（バイナリ法）
5. 反復法（ニュートン法）
6. 黄金比

1. 階乗

通常実装

fun fact(n: BigInteger): BigInteger{
    var i = n
    var ans = BigInteger.ONE
    generateSequence { (i--).takeIf { i > BigInteger.ZERO } }.forEach {
        ans *= it
    }
    return ans
}

末尾再帰による実装

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. ユークリッドの互除法

通常実装

fun gcd(a: Int, b: Int): Int{
    var x = a
    var y = b
    var temp: Int
    while (y != 0){
        temp = y
        y = x % y
        x = temp
    }
    return x
}

末尾再帰による実装

tailrec fun gcd(a: Int, b: Int): Int{
    if(b == 0) return a
    return gcd(b, a%b)
}

3. フィボナッチ数¹

通常実装

fun fib(n: BigInteger): BigInteger{
    var i = n
    var a = BigInteger.ZERO
    var b = BigInteger.ONE
    var temp: BigInteger
    while (i > BigInteger.ONE){
        temp = b
        b = a + b
        a = temp
        i--
    }
    return a
}

末尾再帰による実装

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. 累乗（バイナリ法）

通常実装

fun pow(a: BigInteger, n: Int): BigInteger{
    var i = n
    var atemp = a
    var ans = BigInteger.ONE
    while (i != 0){
        if(i.and(1) == 1) ans *= atemp
        atemp *= atemp
        i = i.ushr(1)
    }
    return ans
}

末尾再帰による実装

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. 反復法（ニュートン法）

通常実装

fun newton(
    f: (Double)-> Double,
    df: (Double)-> Double,
    x0: Double,
    eps: Double = Float.MIN_VALUE.toDouble()
): Double{
    var x: Double
    var xnew: Double = x0
    do {
        x = xnew
        xnew = x - f(x)/df(x)
    }while (abs(x - xnew) > eps)
    return xnew
}

末尾再帰による実装

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)
}

6. 黄金比²

通常実装

fun goldenRatio(n: Int): Double{
    var ans = 1.0
    for(i in 0 .. n){
        ans = 1.0 + 1.0 / ans
    }
    return ans
}

末尾再帰による実装

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) }
}

感想

ループを使った実装ではとにかくvarが出てくるのが気持ち悪いですね。
後、引数として渡された値を書き換えたり、BigIntegerをループで使うのが難しかったり、そういった言語仕様による問題も末尾再帰では吸収できていると思います。
実装のシンプルさも踏まえ、使える場面ではどんどん末尾再帰を使ったほうがいいと言えるでしょう。

---

1. シーケンスを使ったほうがスマートに実装できますが、この場合シーケンスは使わない方がシンプルだと感じたので、ここではループで実装しています。 ↩

2. 末尾再帰による実装ではトランポリンを用いています。トランポリンについてはこちら。 ↩