やねう企画2005年入社問題解答と解説(3)

(昨日の解説の続き)

再帰を仮想スタックの導入により非再帰に変換するという話をした。実は、仮想スタックを導入すれば、“いつでも”再帰は非再帰に変換できる。賢いコンパイラならば自動的にやってしまうだろう。それを人間様が「出来ない」というのはどこかおかしな話だ。

「仮想スタック」を導入と言ったが、場合によっては、導入して非再帰型プログラムに書き換えたあと、縮退して仮想スタックを用いなくても済むプログラムになることがある。たとえば、tail recursion(末尾再帰)を仮想スタックを導入して書き換えようとしたとき、最終的には縮退して仮想スタック自体が消去出来る。同様に、有名な例としては「ハノイの塔」のプログラムを“仮想スタックを用いないで”、非再帰に変形できるという事実がある。