Help us understand the problem. What is going on with this article?

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

More than 1 year has passed since last update.

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

TL;DR

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

比較するアルゴリズム

この記事で比較するアルゴリズムは以下の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. フィボナッチ数1

通常実装
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. 黄金比2

通常実装
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. 末尾再帰による実装ではトランポリンを用いています。トランポリンについてはこちら。 

wrongwrong
public class Main { public static void main(String[] args) { console.log("Hello World!"); } } Error: java: シンボルを見つけられません シンボル: 変数 console 場所: クラス com.wrongwrong.Main
https://wrongwrong163377.hatenablog.com/
microad
データとテクノロジーをかけ合わせたマーケティングプラットフォームを提供する会社です。
https://www.microad.co.jp/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした