末尾再帰最適化の正体

　再帰呼び出しはロジックを簡潔に書ける一方で、スタックの深さやパフォーマンスなど考慮すべき点が多くあります。これらの対応のために再帰処理をループなどに展開するのは、煩雑なうえに可読性を損なってしまいます。Kotlinは末尾再帰最適化のためのキーワードを提供しており、コンパイラが再帰呼び出しを最適化してくれます。これにより再帰呼び出しの読みやすさと、スタックやパフォーマンスの問題の両方を解決できます。

末尾再帰最適化の概要

　末尾再帰最適化を行うにはtailrecキーワードを使います。リスト1のように関数の先頭にtailrecを付与することで、コンパイラに末尾再帰最適化を指示できます。

リスト1. 末尾再帰最適化をする

// 級数を求める関数
tailrec fun series(n: Int, m: Long = 0): Long =
        if (n == 0) {
            m
        } else {
            series(n - 1, m + n)
        }

　Kotlinではtailrecキーワードによる明示的な末尾最適化を行っています。 tailrecキーワードを付与していない場合は、関数が末尾再帰をしていてもコンパイラは最適化をしません。これには2つの理由があります¹。

　ひとつはデバッグのためです。末尾再帰最適化されたコードは実際には再帰を行わなくなるため、デバッガによってスタックフレームを見られなくなります。デバッグの際はtailrecを外すなどの明示的な操作で末尾再帰最適化をコントロールできます。

　もうひとつは最適化が可能かどうかを検査するためです。tailrecキーワードを付与した関数を、コンパイラが末尾再帰最適化できないと判断した場合は警告を出してくれます。末尾再帰最適化しているつもりができていない、といったケースを防げます。

¹: https://blog.jetbrains.com/kotlin/2013/12/m6-2-available/

末尾再帰最適化による処理のループ展開

　tailrecキーワードの有無によってコンパイル後のコードがどのように変化するか確認してみましょう。 リスト2はフィボナッチ数列の特定のindexの値を計算する関数ですtailrecキーワードを付与せず末尾で再帰呼び出しをしています。

リスト2. tailrecを付与しないケース

fun fib(n: Int, f: Int = 0, s: Int = 1): Int =
  when (n) {
    0 -> f
    1 -> s
    else -> fib(n - 1, s, f + s)
  }

　デコンパイルをするとリスト3のようになります。

リスト3. tailrecを付与しないケースをデコンパイル

public final int fib(int n, int f, int s) {
  int var10000;
  switch(n) {
  case 0:
   var10000 = f;
   break;
  case 1:
   var10000 = s;
   break;
  default:
   var10000 = this.fib(n - 1, s, f + s);
  }

  return var10000;
}

　when式をswitch文に置き換えた以外はほとんど元のコードと同じです。つぎにtailrecキーワードを付与するケースを見てみましょう(リスト4)。

リスト4. tailrecを付与するケースをデコンパイルする

public final int fib(int n, int f, int s) {
  while(true) {
      int var10000;
      switch(n) {
    case 0:
      var10000 = f;
      break;
    case 1:
      var10000 = s;
      break;
    default:
      int var10001 = n - 1;
      int var10002 = s;
      s += f;
      f = var10002;
      n = var10001;
      continue;
    }
    return var10000;
  }
}

　再帰呼び出しが展開されてwhile文になっています。これによりスタックオーバーフローを気にする必要がなくなりました。最適化を明示的にコンパイラに任せることで、コードの可読性を保つことができています。tailrecキーワードによる末尾再帰最適化は、再帰呼び出しの展開を肩代わりしてコードを簡潔に保つ手助けをしてくれます。