この記事では、再使用可能・再入可能・再配置可能・再帰的について、初心者にも分かりやすく、図解付きで丁寧に解説しています！
再使用可能プログラム
- 再使用可能（リユーザブル）なプログラムは主記憶装置にロードしたプログラムを再ロードすることなく実行しても正しい結果が得られる。
- 再使用可能なプログラムはプログラムの最初か最後に変数を初期化する。
再入可能プログラム
- 再入可能（リエントラント）なプログラムは複数のプログラムから呼び出されても、それぞれ正しい結果を返す。
- 再入可能プログラムは再使用可能プログラムでもある。
再配置可能プログラム
- 再配置可能（リロケータブル）なプログラムは主記憶装置のどこに配置しても実行可能。
再帰的プログラム
- 再帰的（リカーシブ）なプログラムは自分自身を呼び出す。
- BNF記法は再帰的にプログラムの構文を定義する方法。
プログラムは主記憶装置へロードする
私たちが使うプログラムは、普段、補助記憶装置に記録されており、プログラムを実行する時は主記憶装置へロードしてから実行します。CPUは主記憶装置に置いてある命令を実行しますからね。
主記憶装置にロードしたプログラムをCPUが処理する手順はこちらの記事で解説しています。
再使用可能（リユーザブル）
主記憶装置に一度ロードして実行したプログラムを、再ロードすることなく実行しても正しい結果になるようなプログラムを再使用可能なプログラムと呼びます。再使用可能なプログラムはプログラムの最初か最後に変数を初期化しておく必要があります。変数の初期化をすることで、再ロードせずとも、前回の結果を引継がないで処理でき、毎回正しい結果が得られます。
再入可能（リエントラント）
同時に複数のタスクから呼び出されても、お互いに干渉することなく、正しい結果が得られるようなプログラムを再入可能なプログラムと呼びます。再入可能なプログラムの多くは再使用可能なプログラムです。再ロードしなくても正しい結果が得られるからこそ、複数同時に呼び出されても問題ないわけです。
再配置可能（リロケータブル）
主記憶装置のどのアドレスに配置しても実行可能なプログラムを再配置可能なプログラムと呼びます。CPUがプログラム中の命令を実行するとき、処理対象とするデータや次に実行する命令が格納されている主記憶装置のアドレスを指定します。アドレスを指定するときに、「アドレス：0005」の命令を次に実行！という風にするのではなく、「プログラムの先頭アドレスから100足したアドレス」の命令を次に実行！という風に指示します。こうすると、プログラムをどのアドレスに格納してもOKになります。
再帰的（リカーシブ）
プログラムの実行中に自分自身を呼び出すことが出来るプログラムを再帰的なプログラムと呼びます。
再帰的の例を見てみましょう。
「1からnまでの整数を足し算した結果を返すプログラム」はこのようになります。
f(n)：if n=1 then return 1 else return n＋f(n－1)
・n=1の時、f(1)=1
・n=1以外の時、f(n)=n+f(n-1)
n=1以外の時の結果には、f(n-1)と自分自身が含まれていますね。
では、実際に計算してみましょう。n=1~5の時の結果はそれぞれこのようになります。
・n=5のときf(5)=5+f(4)
・n=4のときf(4)=4+f(3)
・n=3のときf(3)=3+f(2)
・n=2のときf(2)=2+f(1)
・n=1のときf(1)=1
f(5)=5+f(4)なので、
f(5)=5+(4+f(3))=9+f(3)=9+(3+f(2))=12+f(2)=12+(2+f(1))=14+f(1)
=14+1=15となります。
このように、処理の中で自分自身を呼び出すような性質を再帰的と言います。
BNF記法
プログラミングで構文を再帰的に定義する方法にBNF記法があります。
下の定義では1桁の数字の足し算を表現しています。この例を元にBNF記法を見てみます。
<Number>::=0|1|2|3|4|5|6|7|8|9
<Formula>::=<Number>”+”<Number>|<Formula>”+”<Number>
「<S>::=〇」は「Sは〇と定義する」を、「|」は「または」を意味します。
なので、【<Number>::=0|1|2|3|4|5|6|7|8|9】は、【Numberには0,1,2,3,4,5,6,7,8,9のどれかが入ること】を意味し、
【<Formula>::=<Number>”+”<Number>|<Formula>”+”<Number>】は、【FormulaにはNumber+NumberまたはFormula+Numberが入ること】を意味します。
FormulaにはNumber+Numberが入るので、例えば、2+3や8+5が入ります。
また、Formula＋Numberが入るので、例えば、Formula=2+3、Number=9の場合は、2+3+9が入ります。Formula=2+3+9、Number=1とすれば、Formula=2+3+9+1になり、足す数をどんどん増やしていくことが出来ます。
このようにBNF記法ではプログラムの構文を定義することが出来ます。
基本情報技術者試験での出題例
令和元年度秋期問7
基本情報技術者
午前試験 令和元年度秋期問7
次のBNFで定義される＜変数名＞に合致するものはどれか。
＜数字＞::＝ 0｜1｜2｜3｜4｜5｜6｜7｜8｜9
＜英字＞::＝ A｜B｜C｜D｜E｜F
＜英数字＞::＝＜英字＞｜＜数字＞｜_
＜変数名＞::＝＜英字＞｜＜変数名＞＜英数字＞
ア _B39 イ 246 ウ 3E5 エ F5_1
正解は”エ”
BNF記法では「<S>::=〇」は「Sは〇と定義する」を、「|」は「または」を意味します。
なので、
<数字>には、0~9のどれか1文字
<英字>には、A~Fのどれか1文字
＜英数字＞には、数字または英字または_のどれか1文字
＜変数名＞には、英字1文字または変数名の後ろに英数字1文字を付けたもの
が入ります。
変数名は英字1文字か変数名の後ろに英数字1文字を付けたものです。ア～エは全て2文字以上なので、変数名だとしても変数名の後ろに英数字1文字を付けたものになります。
ア～エの選択肢が変数名になり得るか確かめてみましょう。
【ア】
「_B39」が変数名ということは、「_B3」が変数名、「9」が英数字と言うことです。
「9」は数字1文字なので英数字でOKですね。では、「_B3」は変数名でしょうか？
「_B3」は英字1文字ではないので、変数名だとしたら変数名の後ろに英数字1文字を付けたものになるはずです。これも分解してみましょう。
「_B3」が変数名ということは、「_B」が変数名、「3」が英数字と言うことです。「3」は英数字でOKですね。では、「_B」は変数名でしょうか？これも英字1文字ではないので分解してみましょう。
「_B」が変数名ということは、「_」が変数名、「B」が英数字と言うことです。「B」は英数字でOKですね。では、「_」は変数名でしょうか？
「_」は英字1文字でもなければ、変数名の後ろに英数字1文字を付けたものでもありません。ということは「_」は変数名ではないということです。
「_」が変数名ではないということは「_B」は変数名ではないということで、
「_B」が変数名ではないということは「_B3」は変数名ではないということで、
「_B3」が変数名ではないということは「_B39」は変数名ではないということになります。
よって、アは間違いです。
他の選択肢もこのように分解して考えてみると答えはエになります。
実際にエの選択肢を見てみましょう。
【エ】
「F5_1」が変数名ということは、「F5_」が変数名、「1」が英数字と言うことです。
「1」は数字1文字なので英数字でOKですね。では、「F5_」は変数名でしょうか？
「F5_」は英字1文字ではないので、変数名だとしたら変数名の後ろに英数字1文字を付けたものになるはずです。これも分解してみましょう。
「F5_」が変数名ということは、「F5」が変数名、「_」が英数字と言うことです。「_」は英数字でOKですね。では、「F5」は変数名でしょうか？これも英字1文字ではないので分解してみましょう。
「F5」が変数名ということは、「F」が変数名、「5」が英数字と言うことです。「5」は英数字でOKですね。では、「F」は変数名でしょうか？
「F」は英字1文字なので変数名です。
「F」が変数名だということは「F5」は変数名だということで、
「F5」が変数名だということは「F5_」は変数名だということで、
「F5_」が変数名だということは「F5_1」は変数名だということになります。
よってエが正しいことが分かります。
平成31年度春期問8
基本情報技術者
午前試験 平成31年度春期問8
複数のプロセスから同時に呼び出されたときに，互いに干渉することなく並行して動作することができるプログラムの性質を表すものはどれか。
ア リエントラント
ウ リユーザブル
イ リカーシブ
エ リロケータブル
正解は”ア”
複数から呼び出されても互いに干渉することなく、正しい結果を返す性質をリエントラントと言います。
平成29年度秋期問6
基本情報技術者
午前試験 平成29年度秋期問6
再帰呼出しの説明はどれか。
ア あらかじめ決められた順番ではなく，起きた事象に応じた処理を行うこと
イ 関数の中で自分自身を用いた処理を行うこと
ウ 処理が終了した関数をメモリから消去せず，必要になったとき再び用いること
エ 処理に失敗したときに，その処理を呼び出す直前の状態に戻すこと
正解は”イ”
関数の中で自分自身を呼び出して処理する性質を再帰呼出しと言います。
