コンパイラは再帰をどのように理解していますか？

Question

私はcとpythonでプログラミングするときに再帰を使っていますが、他の多くの言語でも使われていると思いますが、どのようにコンパイラが実際に再帰関数を解釈しますか？それはそれ自身の定義でどのように関数を使用することができますか？

Answer 1

が、どのようにコンパイラが実際に再帰関数を解釈していますか？それはそれ自身の定義でどのように関数を使用することができますか？

これを理解するには、コンパイラが関数をどのように解釈するかを理解する必要があります。 Cの場合、関数は単なるシンボル、またはメモリ内のエントリアドレスを指すポインタです。直観的には厳密にはそうではありませんが、関数呼び出しはそのようなアセンブル命令にコンパイルされます。

CALL address_of_function 

参照してください。コンパイラは、関数が再帰的かどうかを知る必要はありません。それは単にCPUが機能エントリのアドレスにジャンプし、命令を実行し続けるだけです。

そのため、その定義が完了していなくてもその機能を使用することができます。コンパイラは開始アドレスまたはシンボルを知る必要があり、ジャンプする場所を知るだけです。関数の本体は後で生成することができます。

ただし、のテール再帰を知りたい場合があります。これは、一般的に関数型プログラミング言語では特殊なケースです。 「末尾再帰」は、再帰関数呼び出しが関数定義の最後の文であることを意味します。前述の@ paulsm4のように、関数を呼び出すとき、コンパイラはコンテキストとパラメータをスタックにプッシュし、コンテキストをリカバリし、そこから戻り値を取得する必要があります。したがって、あなたの関数がそれ自身を呼び出して、次にそれ自身を呼び出すと、メモリがなくなるまでスタックは深くなります。しかし、関数呼び出しが関数定義の最後のステートメントであれば、スタックにコンテキストを保存する必要はなく、単に上書きすることができます。したがって、関数が無限に呼び出しても、スタックはオーバーフローしません。

Answer 2

これは完全にコンパイラ依存ですが、ほとんどの言語のほとんどのコンパイラはスタックを使用して再帰を実装しています。

コンパイラは、プログラムの引数をプッシュし、現在のスタックポインタとフレームポインタを保存したコードを生成し、（新しく更新されたスタックを使用して）同じ関数を呼び出します。ここで

は非常に良い記事です：Understanding the stack