[解決済み】すべての再帰は反復に変換できる？

質問

A redditスレッド という、一見すると興味深い疑問が浮かびました。

尾部再帰関数は些細なことで反復関数に変換することができます。それ以外のものは、明示的にスタックを使用することで変換できる。できること あらゆる 再帰は反復に変換されるのですか？

投稿にある(対?)例が対になっています。

(define (num-ways x y)
  (case ((= x 0) 1)
        ((= y 0) 1)
        (num-ways2 x y) ))

(define (num-ways2 x y)
  (+ (num-ways (- x 1) y)
     (num-ways x (- y 1))

解決方法は？

再帰的な関数を常に反復的な関数にすることができるのか？記憶が正しければ、チャーチ・チューリング論文はそれを証明しています。平たく言えば、再帰関数で計算可能なものは反復モデル（チューリングマシンなど）でも計算可能であり、その逆もまた然りということです。この論文は、変換の正確な方法を教えてくれるわけではありませんが、確実に可能であることを述べています。

多くの場合、再帰的な関数の変換は簡単です。Knuthは、"The Art of Computer Programming"でいくつかのテクニックを紹介しています。また、再帰的に計算されたものが、全く別のアプローチでより少ない時間とスペースで計算できることもよくある。その典型的な例がフィボナッチ数あるいはその数列である。皆さんも学位計画でこの問題に出会ったことがあるはずです。

このコインの裏側では、プログラミングシステムが高度化し、式の再帰的定義を、前の結果をメモするように促すものとして扱うことで、再帰的定義を持つ式の計算でどのステップを踏めばよいかをコンピュータに正確に伝えるという面倒な作業をせずに、スピードの恩恵を受けることができるようになることは、確かに想像できるだろう。ダイクストラは、ほぼ間違いなくこのようなシステムを想像していた。彼は長い時間をかけて、プログラミング言語の意味論から実装を切り離そうとした。そしてまた、彼の非決定論的プログラミング言語とマルチプロセシングプログラミング言語は、実践的なプロのプログラマーよりも上のレベルにある。

最終的には、多くの関数が再帰的な形で理解しやすく、読みやすく、書きやすいということです。やむを得ない理由がない限り、これらの関数を明示的な反復アルゴリズムに（手動で）変換する必要はないでしょう。その作業はコンピュータが正しく処理してくれます。

ひとつだけ、やむを得ない理由があると思います。例えば、[ ]のような超高水準言語でプロトタイプのシステムを作ったとします。 アスベストの下着を着る ] Scheme、Lisp、Haskell、OCaml、Perl、Pascal。CやJavaでの実装を必要とするような条件があったとする。(その場合、再帰的に書かれた関数でも、文字通りに翻訳するとランタイムシステムを爆発させるようなものがあることは確かです。例えば、Schemeでは無限末尾再帰が可能だが、同じイディオムは既存のC言語環境では問題を起こす。もうひとつの例は、PascalではサポートされているがCではサポートされていない、辞書的にネストされた関数と静的スコープの使用だ。

このような状況では、元の言語に対する政治的抵抗を克服しようとすることがあります。Greenspunの第10法則のように、Lispをひどく再実装してしまうかもしれません。あるいは、全く別の解決方法を見つけるかもしれません。しかし、いずれにせよ、方法は必ずあるはずです。