再帰は再帰でも安全な再帰

こんにちはHANDAI JKの石田です。

梅雨もまだだというのに連日真夏日でちょっとうんざりしますね！ さて、今日は「再帰」の話をしようと思います。

再帰とは

関数の中で自分自身を呼び出すことです。階乗の計算や、フィボナッチ数列がよく例として挙げられますよね。

/* 再帰呼出しを使って階乗を計算する関数 */
int fact(int n) {
  if (n == 0) return 1;
  else return fact(n - 1) * n;
}

再帰の問題点

プログラマーの味方である再帰ですが、ちょっとした落とし穴があることをご存知ですか？ 実は、上記のプログラムの引数に1,000,000のような大きな数を渡すとスタックオーバーフローが発生していしまいます。

なぜスタックオーバーフローとなるかというと、コンピューターの中でプログラムが実行されるその仕組みに理由があるので簡単に説明します。

関数内のローカル変数や関数末尾でreturnした時にプログラムのどの位置にジャンプするかといった情報はスタックという領域に格納されています。基本的にreturnされるタイミングでスタックの領域は開放されるのですが、再帰関数の場合returnする前にどんどん自分自身を呼び出していくのでスタックの領域が圧迫されていき、ついにはいっぱいになってしまうというわけです。

末尾再帰と末尾再帰最適化

じゃあ再帰関数は非安全かというと、そうでもありません！末尾再帰という形の再帰になっていれば、スタックオーバーフローは発生しないのです。以下がKotlinという言語で実装した末尾再帰版の階乗を計算する関数です。(Kotlinでは末尾再帰最適化をしてほしい関数にtailrecキーワードをつけます。)

fun factTailRec(n: Int): Int {
  tailrec fun f(n: Int, acc: Int): Int {
    return if (n == 0) {
      acc
    } else {
      f(n - 1, acc * n)
    }
  }

  return f(n, 1)
}

6行目に注目してください。「末尾再帰である」条件は「自分自身を呼び出した結果を返す」ということです。最初に登場した実装では再帰部分がreturn fact(n - 1) * n;となっていたのに対し、こちらの末尾再帰版の実装ではf(n - 1, n * acc)となっています。

末尾再帰になっているとコンパイラによって末尾再帰最適化が行われ、例えばループによる実装にプログラムが変換されるのでスタックオーバーフローが発生しないのです。

まとめ

末尾再帰でないと困るという実際のケースは限られますし、すべての言語が末尾再帰最適化に対応しているわけではないので、必ず末尾再帰でないというわけではありません！ですが、せっかく再帰を習ったのなら末尾再帰も知識として知っておくといいと思います。