私は本、Structure and Interpretation of Computer Programs を読んでいました。そこでは、再帰手順と再帰プロセスの違い、および同様に反復手順と反復プロセスの違いについて説明しています。そのため、再帰的な手順でも反復プロセスが生成される可能性があります。
私の質問は次のとおりです。再帰プロセスを生成するプロシージャが与えられた場合、同じ結果を達成するが反復プロセスを生成する別のプロシージャをいつでも作成できますか?
私が解決しようとしていた具体的な問題は、二分探索木の順序通りのトラバーサルを行うが、反復プロセスを生成する手順を作成することでした。スタックを使用して、この問題の反復手順を取得する方法を知っています。ただし、それでも再帰プロセスが生成されます (ここで間違っている場合は修正してください)。
ありがとう、
アビナフ。
一部のタスクは、線形反復プロセスで解決することは本当に不可能です（たとえば、末尾再帰に変換することが不可能なツリー再帰）。プラットフォームに組み込まれているスタックを使用するか、言語内で自分でスタックを再作成する必要があります（通常、効率がはるかに低く、醜いソリューションです）。したがって、「再帰」を「スタックを使用して同じコードの異なる呼び出しを格納する」と定義した場合、そうです、再帰が絶対に必要になる場合があります。
'recursion'を'私の言語の関数（最終的には）それ自体を呼び出す'として定義する場合、上記のように、再帰性を自分で再実装することにより、明示的な再帰なしでうまくいくことができます。これは、言語が再帰的なプロシージャを提供していない場合、スタックスペースが十分でない場合、または同様の制限がある場合にのみ役立ちます。（たとえば、初期のFortranには再帰的な手順がありませんでした。もちろん、それらをシミュレートするために必要な動的データ構造もありませんでした！個人的には、疑似再帰の実装が実際に行われた例に出くわしたことはありません。正しい解決策。）
末尾再帰プロセスは、反復プロセスに変換できます。
しかし、すべての再帰プロセスを反復プロセスに変換できるわけではありません。