末尾再帰最適化について

概要

自分の中での整理用に書きました。
詳しくは参考記事を参照してください。
末尾再帰最適化について、再帰関数やスタックオーバーフローにも触れつつ書いていきます。

キーワード

• 再帰関数
• スタックオーバーフロー
• 末尾再帰

再帰関数とは

関数の中でその関数自身を呼び出す関数のこと

例)階乗n!を求める関数
6!=6*5*4*3*2*1=720
みたいに、その数字以降全ての積を表すのが階乗
これを関数にすると、

factorial.js

function factorial(n){
  if (n === 1) return 1;
  else return n*factorial(n-1)
}

ただし、この関数には問題があり、nが非常に大きな数になった場合にスタックオーバーフローが起きてしまう

スタックオーバーフロー

上記の階乗の計算を求める際、例えばn=10のとき、
factorial(10)=10*factorial(9)なので、factorial(9)の計算結果が必要となるためfactorial(9)を計算しにいく。
このとき、10*factorial(9)の10をどこかに記憶しておかないといけない。
同様にfactorial(9)では9*factorial(8)となるので9を記憶し、これがfactorial(1)=1と分かるまで繰り返される。
この記憶の積み重ねがメモリに溜まっていく。（このときに使われるデータ構造がスタック）
nが大きくなればなるほどメモリが必要になるが、メモリも無限ではないため、いつかはデータが多すぎて溢れてしまう。
これがスタックオーバーフロー。

これを回避するためには、ループでプログラムを記述するか、末尾再帰最適化を利用する。（実際は末尾再帰で書いたコードがループで書かれたものにコンパイルされるっぽい）

末尾再帰

返り値が再帰関数の呼び出しのみになっている場合に、それを末尾再帰(Tail Recursion, Tail Call)と呼ぶ。

上記の階乗を求めるコードを末尾再帰として書きなおすと下のようになる。

factorialTailCall.js

function factorialTailCall(n, accumulator = 1){
  if (n === 1) return accumulator;
  else return factorialTailCall(n-1, n*accumulator)
}

factorialTailCall(4)のとき、
factorialTailCall(3,4*1)
factorialTailCall(2,3*4)
factorialTailCall(1,2*12)
という順番で関数が呼び出されていき、最終的に24が帰ってくる。

積を保存しておくaccumulatorを引数に追加することで、再帰関数の呼び出しのみを返り値にできている。
末尾再帰の条件を満たしているとき、コンパイラなんかが最適化してくれることを末尾再帰最適化と言う。
ただし、末尾再帰最適化に対応しているものとしていないものがある。

言語ごとの対応・非対応

言語	対応しているか	補足
Java	×
Scala	○	@tailrec
Kotlin	○	tailrec修飾子
JavaScript	△	※後述

JavaScriptの末尾再帰最適化

ES6の仕様には末尾再帰最適化があるみたいだが、それに対応しているブラウザがSafariくらいしかない模様(ES6対応表)
Node.jsでは一時期--harmonyオプションをつけることで末尾再帰最適化ができていたみたいだが、現在のバージョンでは非対応になってしまっている。(Node.js ES6対応表)
babelについても、一時期対応していた時期もあったみたいだが、現在は非対応になっているようだ。

実際にNode.jsで前述のfactorialTail関数とfactorialTailCall関数を動かしたら、末尾再帰になっているはずの後者の方が早くスタックオーバーフローを起こしてしまった
悲しい

おまけ フィボナッチ数列

フィボナッチ数列を通常の再帰と末尾再帰で書くと下記のような感じ

通常の再帰

fibo.js

function fibo(n) {
  if (n === 0) return 0;
  else if (n === 1 || n === 2) return 1;
  else return fibo(n-1) + fibo(n-2);
}

末尾再帰

fiboTailCall.js

function fiboTailCall(n, a = 1, b = 0) {
  if (n === 0) return 0;
  else if (n === 1) return a;
  else return fiboTailCall(n-1, a+b, a);
}

参考

末尾再帰による最適化
http://www.fos.kuis.kyoto-u.ac.jp/~igarashi/class/pl/09-rec-iter.html