コンパイラを設計する際には、再帰の取り扱いが特別な治療が必要ですか？

Question

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

Answer 1

スタックをまったく持っています は 再帰をサポートするときにコンパイラが持たなければならない特別な治療。

Fortranの初期バージョンのような古いプログラミング言語では、ランタイム環境には関数スタックがなく、各関数にはメモリのどこかに1つのアクティベーションレコードが予約されていました。つまり、再帰は不可能ではありませんでした。なぜなら、あなたが再帰的に関数を呼び出した場合、あなたはその唯一のアクティベーションレコードを上書きし、そこに到着した方法のコンテキストを追跡するからです。

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

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

お役に立てれば！