2

関数呼び出しは、スタック データ構造を介して処理されます。これは再帰をサポートするのに十分ですか?

4

1 に答える 1

5

スタックを持つことは、再帰をサポートするときにコンパイラが持たなければならない特別な扱いです。

初期バージョンの FORTRAN のような古いプログラミング言語では、ランタイム環境に関数スタックがなく、各関数にはメモリ内のどこかにその関数用に予約されたアクティブ化レコードが 1 つだけありました。これは、再帰がまったく不可能であることを意味していました。関数を再帰的に呼び出すと、その唯一のアクティベーション レコードが上書きされ、どのようにそこにたどり着いたかというコンテキストが失われてしまうからです。

関数スタックの導入により、プログラミング言語で再帰を実際に表現できるようになりました。それ以前は、プログラマーは問題を抽象的に解決するためのツールとして再帰を使用していましたが、コール スタックがないため、そのコードを反復ロジックに変換する必要がありました。

プログラミング言語が再帰をサポートするには、コール スタックを動的に維持するためのメカニズムが必要です。これは、明示的なスタックを介する必要はありません。理論的には、すべてのスタック フレームを動的に割り当て、それらをリンク リストとして連鎖させることができます。これは、たとえば、コルーチンやクロージャーをサポートする必要があり、実際には関数が戻った後に古いアクティベーション レコードを保持して、後でデータを保存できるようにする必要がある場合に役立ちます。

お役に立てれば！

于 2011-09-08T02:40:10.303 に答える