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」でいくつかのテクニックを提供しています。多くの場合、再帰的に計算されたものは、まったく異なるアプローチでより少ない時間とスペースで計算できます。この古典的な例は、フィボナッチ数またはその数列です。学位取得計画でこの問題に確実に対応しています。
このコインの裏返しとして、式の再帰的な定義を以前の結果をメモ化するための招待状として扱うほど高度なプログラミング システムを想像することができます。これにより、コンピューターにどのステップを実行するかを正確に伝える手間をかけずに速度の利点が提供されます。再帰的な定義を持つ数式の計算に従います。ダイクストラがそのようなシステムを想像したことはほぼ間違いありません。彼は、プログラミング言語のセマンティクスから実装を切り離すことに長い時間を費やしました。繰り返しになりますが、彼の非決定論的マルチプロセッシング プログラミング言語は、実際のプロ プログラマーよりもはるかに優れています。
最終的な分析では、多くの関数は単純に理解しやすく、読みやすく、再帰的な形式で書きやすいということです。やむを得ない理由がない限り、これらの関数を (手動で) 明示的な反復アルゴリズムに変換しないでください。あなたのコンピュータはその仕事を正しく処理します。
説得力のある理由が 1 つあります。[アスベストの下着を着用する] Scheme、Lisp、Haskell、OCaml、Perl、または Pascal のような超高水準言語のプロトタイプ システムがあるとします。C または Java での実装が必要な状況があるとします。(おそらくそれは政治的なものです。)そうすれば、確かにいくつかの関数を再帰的に記述できますが、これを文字通りに翻訳すると、ランタイム システムが爆発します。たとえば、Scheme では無限末尾再帰が可能ですが、既存の C 環境では同じイディオムが問題を引き起こします。もう 1 つの例は、レキシカルにネストされた関数と静的スコープの使用です。これは Pascal ではサポートされていますが、C ではサポートされていません。
このような状況では、元の言語に対する政治的抵抗を克服しようとするかもしれません。Greenspun の (冗談めかした) 第 10 法則のように、Lisp の再実装がうまくいかないことに気付くかもしれません。または、ソリューションへのまったく異なるアプローチを見つけることもできます。しかし、いずれにせよ、必ず方法はあります。
すべての再帰関数に対して非再帰的なフォームを書くことは常に可能ですか?
はい。簡単な形式的証明は、μ 再帰と GOTO などの非再帰計算の両方が両方ともチューリング完全であることを示すことです。すべてのチューリング完全計算は表現力において厳密に同等であるため、すべての再帰関数は非再帰チューリング完全計算によって実装できます。
残念ながら、オンラインで GOTO の適切で正式な定義を見つけることができないため、ここに 1 つを示します。
GOTO プログラムは、 Pが次のいずれかであるレジスタ マシンで実行される一連のコマンドPです。
HALT、実行を停止しますr = r + 1rレジスタはどこですかr = r – 1rレジスタはどこですかGOTO xxラベルはどこですかIF r ≠ 0 GOTO xはr任意のレジスタで、xはラベルですただし、再帰関数と非再帰関数の間の変換は、常に自明とは限りません (コール スタックを無意識に手動で再実装する場合を除きます)。
詳細については、この回答を参照してください。
再帰は、実際のインタープリターまたはコンパイラーでスタックまたは同様の構造として実装されます。したがって、再帰関数を対応する反復関数に変換することは確かにできます。コンパイラの作業をアドホックに、おそらく非常に醜く非効率的な方法で複製するだけです。
基本的にはい、本質的にあなたがしなければならないことは、メソッド呼び出し（暗黙的に状態をスタックにプッシュする）を明示的なスタックプッシュに置き換えて、「前の呼び出し」がどこに到達したかを覚えてから、「呼び出されたメソッド」を実行することです代わりは。
基本的にメソッド呼び出しをシミュレートすることにより、ループ、スタック、およびステートマシンの組み合わせをすべてのシナリオで使用できると思います。これが「より良い」ものになるかどうか (より高速になるか、ある意味でより効率的になるか) は、一般的に言うことはできません。
再帰関数の実行フローはツリーとして表現できます。
データ構造を使用してそのツリーをトラバースするループでも同じロジックを実行できます。
深さ優先のトラバーサルはスタックを使用して実行でき、幅優先のトラバーサルはキューを使用して実行できます。
答えはイエスです。理由: https://stackoverflow.com/a/531721/2128327。
単一のループで再帰を実行できますか? はい、なぜなら
チューリング マシンは、1 つのループを実行することですべてのことを行います。
- 命令をフェッチし、
- それを評価し、
- 1に行きます。
はい、明示的にスタックを使用します (ただし、再帰ははるかに読みやすく、私見です)。
はい、再帰的でないバージョンを書くことはいつでも可能です。簡単な解決策は、スタック データ構造を使用して再帰的な実行をシミュレートすることです。
原則として、再帰を削除し、データ構造と呼び出しスタックの両方で無限の状態を持つ言語の反復に置き換えることが常に可能です。これは、チャーチチューリングテーゼの基本的な結果です。
実際のプログラミング言語を考えると、答えはそれほど明白ではありません。問題は、プログラムで割り当てることができるメモリの量が制限されているが、使用できる呼び出しスタックの量が無制限である言語（スタック変数のアドレスが32ビットCである場合）を使用できる可能性が非常に高いことです。アクセスできません）。この場合、再帰は、使用できるメモリが多いという理由だけで、より強力になります。呼び出しスタックをエミュレートするのに十分な明示的に割り当て可能なメモリがありません。これに関する詳細な議論については、この議論を参照してください。
場合によっては、再帰を置き換える方がはるかに簡単です。再帰は、1990 年代に CS で教えられたファッショナブルなものでした。そのため、当時の多くの平均的な開発者は、再帰で何かを解決する場合、それがより良い解決策であると考えていました。そのため、逆方向にループして順序を逆にする代わりに、再帰を使用したり、そのようなばかげたことをしたりします。したがって、再帰を削除することは、単純な「当然のことでした」タイプの演習である場合があります。
ファッションが他のテクノロジーに移行したため、これは現在ではあまり問題になりません。
明示的なスタックとは別に、再帰を反復に変換する別のパターンは、トランポリンを使用することです。
ここで、関数は最終結果を返すか、それ以外の場合は関数呼び出しのクロージャを返します。次に、開始 (トランポリン) 関数は、最終結果に到達するまで、返されたクロージャを呼び出し続けます。
このアプローチは、相互に再帰的な関数に対して機能しますが、末尾呼び出しに対してのみ機能するのではないかと心配しています。
そうです。関数呼び出しは、goto とスタック操作に他なりません (大まかに言えば)。関数の呼び出し中に構築されるスタックを模倣し、goto と同様のことを行うだけで済みます (このキーワードを明示的に持たない言語でも goto を模倣できます)。
Have a look at the following entries on wikipedia, you can use them as a starting point to find a complete answer to your question.
Follows a paragraph that may give you some hint on where to start:
Solving a recurrence relation means obtaining a closed-form solution: a non-recursive function of n.
Also have a look at the last paragraph of this entry.
タゼゴ、再帰とは、好むと好まざるとにかかわらず、関数が自分自身を呼び出すことを意味します。人々が再帰なしで物事ができるかどうかについて話しているとき、彼らはこれを意味し、「いいえ、それは真実ではありません。私は再帰の定義に同意しないからです」と有効なステートメントとして言うことはできません。
それを念頭に置いて、あなたが言う他のほとんどすべてはナンセンスです. ナンセンスではないとあなたが言う他の唯一のことは、コールスタックなしでプログラミングを想像することはできないという考えです. これは、コールスタックの使用が一般的になるまで何十年も行われてきたことです。FORTRAN の古いバージョンにはコールスタックがなく、問題なく動作しました。
ところで、ループの手段として再帰のみを実装するチューリング完全言語 (SML など) が存在します。ループの手段として反復のみを実装するチューリング完全言語も存在します (例: FORTRAN IV)。Church-Turing テーゼは、再帰のみの言語で可能なことはすべて非再帰言語で実行でき、その逆もまた同様であることを証明しています。
以下は反復アルゴリズムです。
def howmany(x,y)
a = {}
for n in (0..x+y)
for m in (0..n)
a[[m,n-m]] = if m==0 or n-m==0 then 1 else a[[m-1,n-m]] + a[[m,n-m-1]] end
end
end
return a[[x,y]]
end