作成途中
ざっくり概要
プログラムの関数の基礎と仮想メモリを理解していないと攻略不可能ですができるだけ解説します。
これらは、例えばPythonで書いた"test.py"内にある関数：function()に注目していたり、実行ファイル"test.exe"そのものが、どう仮想メモリ配置されるかだったり、ふわっとプログラムの性質を表すものとはいってもこの4つは適用範囲も性質もバラバラ。よって全部別物というスタンスで学んだ方がいい。（4つを平行して同じ分野のように理解しようとすれば、そのズレで余計に混乱する恐れアリ）
これら4つを満たすプログラムも作れますが、4つの性質を全て満たすのが理想とか満たしたから性能が上がるとか、そういうものではありません。
再帰的なプログラムとは
| 関係する対象 | プログラマーが意識して実現可能か | 仮想メモリに関係するか | 満たした方がいいか |
|---|---|---|---|
| 関数 | 〇 | ✕ | プログラムによる。 |
PythonだろうがＣ言語だろうが、関数が自身をを呼び出すコードをプログラマーが書けば、それは再帰的なプログラム（関数）となります。
逆に再帰的な関数が1つだけ入っていたとしても、"Test.exe"を「再帰的なプログラムだ」とは言いません。「再帰的な関数が含まれた、1つの実行ファイル」のような表現になります。（わざわざそんなこと言うかは別として）あくまでプログラムを構築している関数の性質、というイメージでしょうか。
つまりコードの中の1つの関数という狭い話であり、仮想メモリとか関係なくプログラマーが再帰的な関数を書けば必然的に再帰的な関数となります。再帰的な関数ではないから駄目という話でもなく、ただの種類の話です。
再入可能なプログラムとは
| 関係する対象 | プログラマーが意識して実現可能か | 仮想メモリに関係するか | 満たした方がいいか |
|---|---|---|---|
| 関数またはコード全体 | 〇 | ✕ | 推奨 |
PythonだろうがＣ言語だろうが、変数がちゃんと独立しており関数同士で変数の取り合いをしてエラーを起こさなければ、それは再入可能なコード（プログラム）となります。
逆に関数の外にグローバル変数があり、そのグローバル変数が他の関数などに上書きされるなどして"Test.py"が意図しない挙動をするのなら、それは再入可能なコード（プログラム）とは言えません。
つまりコード全体で評価されるべき話であり、仮想メモリとか関係なくプログラマーが不必要なグローバル変数を利用しないなどの工夫や注意で再入可能なコード（プログラム）になります。1本線のコードならまだしも、並行処理や割り込みが発生するコード（プログラム）では再入可能であるのが望ましいと言えるでしょう。
再配置可能なプログラムとは
| 関係する対象 | プログラマーが意識して実現可能か | 仮想メモリに関係するか | 満たした方がいいか |
|---|---|---|---|
| 実行ファイルなど | ✕ | 〇 | ほぼ必須 |
適当に作った"Test.exe"や"word.exe"、"Excel.exe"など、何かしらの実行ファイルを実行するとそれぞれに独立した0番目から連番となった仮想アドレスが連なった仮想メモリが割り当てられます。
その仮想メモリのどこにコードや変数が配置されるかは事前には分かりません。OSが実行されたその時、配置場所を動的に決めています。（語弊あり）
再配置可能なプログラムとは、それでも問題なくどこに配置されても実行できるプログラムを指します。
例えばアセンブリで「ox00005000番地にある変数を持ってくる」という指示が書かれていた場合、正確にox00005000番地にその変数が格納されていないと動きません。当然ですが。
しかし「この場所から+10000番地にある変数を持ってくる」という風にしておけば、"この場所"というのがどこだろうと実行できる訳です。（仮想メモリへの割り振り時、絶対アドレスは保証できないが、相対アドレスであればちゃんと守って格納してくれるらしい。）
つまりプログラム実行後の仮想メモリ番地指定の話であり、プログラマーが出来ることは基本ありません。「ox00005000番地にint Xを格納」とか書きませんよね。最近はセキュリティ上、ランダムな箇所にバイナリデータを配置する仕組みが主流のため、再配置可能であるのが望ましいどころかほぼ必須のレベルでしょう。
これは"Test.py"作成後、コンパイルして"Test.exe"にする過程で決定します。要はコンパイラーの責任です。