再帰呼出しとは何か、似た用語とどう見分けるか
基本情報技術者試験 平成29年度秋期 午前 問6 ／ アルゴリズムとプログラミング › プログラミング
過去問にチャレンジ
再帰呼出しの説明はどれか。
- ア
あらかじめ決められた順番ではなく，起きた事象に応じた処理を行うこと
- イ
関数の中で自分自身を用いた処理を行うこと
- ウ
処理が終了した関数をメモリから消去せず，必要になったとき再び用いること
- エ
処理に失敗したときに，その処理を呼び出す直前の状態に戻すこと
会話形式の解説
講師今回は再帰呼出しの定義を問う問題です。選択肢を読むときは「誰が何を呼び出しているか」に注目してください。それで正誤がはっきりします。
受験者再帰という言葉から「もう一度使う」という意味だと思っていました。処理が終わった関数をメモリに残しておき、必要なときにまた使うという選択肢も当てはまりそうに見えます。
講師そこが引っかけになりやすいところです。再帰呼出しは、関数が処理の途中で自分自身を呼び出すことです。その選択肢は、終わった関数を残しておいて後で使い回す話ですね。処理の最中に自分を呼んでいるかというと、どうでしょうか。
受験者処理が終わってから使い回しているので、途中で自分を呼んではいません。では、これは何の説明ですか。
講師一度読み込んだプログラムを読み込み直さずに使い回す「再使用可能（リユーザブル）」の性質や、結果を保持しておいて再利用する考え方に近いです。プログラムをどう保持して再利用するかの話なので、再帰呼出しとは別物です。
受験者事象に応じて処理を行うという選択肢は、イベントドリブン（事象駆動）のことでしょうか。
講師そうです。決まった順番ではなく、起きた出来事をきっかけに処理を進める方式です。自分自身を呼び出す話は出てこないので、再帰呼出しには当たりません。
受験者失敗したときに呼び出す前の状態に戻すという選択肢は、ロールバックですね。障害から回復する仕組みなので、関数の呼び出し方とは関係がないと考えました。
講師その判断で合っています。残るのは「関数の中で自分自身を用いた処理を行う」という選択肢です。自分自身を呼び出すという定義とそのまま一致するので、これが正解です。
受験者「再び使う」ではなく「自分の中で自分を呼ぶ」が決め手だと分かりました。自分を呼び続けると、終わらなくなりませんか。
講師良いところに気付きました。再帰には、呼び出しを止める終了条件（ここで止めるという判定）が必要です。また、呼び出すたびに戻り先や局所変数がスタック（後から積んだものを先に取り出す領域）に積まれます。そのため、再帰が深くなりすぎるとスタックが足りなくなることがあります。
講師代表的な例は階乗の計算や木構造のたどり方です。大きな問題を同じ形の小さな問題に分けて解きます。同じ処理はループに書き換えられる場合も多く、そうすればスタックの使用を抑えられます。
まとめ
この問題は、再帰呼出しの説明を選ぶものです。再帰呼出しとは、関数が処理の途中で自分自身を呼び出すことで、「関数の中で自分自身を用いた処理を行うこと」が正解です。事象に応じて処理する方式はイベントドリブン、失敗時に元の状態へ戻すのはロールバックで、終わった関数をメモリに残して使い回すのは再使用可能の性質に近い別の考え方です。再帰には終了条件が必要で、呼び出すたびにスタックを使うため、深くなりすぎるとスタックが足りなくなることがあります。
解答・解説
正解はイです
この問題のテーマ
プログラムの基本用語のうち、「再帰呼出し」が何を指すかを問う問題です。
解き方の考え方
再帰呼出しは「関数が処理の途中で自分自身を呼び出すこと」と定義されます。各選択肢が「誰が何を呼び出すのか」を述べているかを見ます。自分自身を呼び出すことを述べていない選択肢は、別の仕組みの説明と判断できます。
選択肢ごとの解説
- ×ア あらかじめ決められた順番ではなく，起きた事象に応じた処理を行うことアは、順番を決めずに、起きた事象に応じて処理を行う方式を説明しています。これはイベントドリブン（事象駆動）の考え方です。関数が自分自身を呼び出すことには触れていないので、再帰呼出しの説明ではありません。
- ○イ 関数の中で自分自身を用いた処理を行うことイは、関数の中で自分自身を使って処理を行うことを説明しています。関数が自分自身を呼び出すという再帰呼出しの定義とそのまま一致するので、これが正解です。
- ×ウ 処理が終了した関数をメモリから消去せず，必要になったとき再び用いることウは、処理が終わった関数をメモリに残しておき、後でまた使うことを説明しています。これはプログラムをどう保持し、どう再利用するかの話です。処理の途中で自分自身を呼び出す仕組みではないので、再帰呼出しには当たりません。
- ×エ 処理に失敗したときに，その処理を呼び出す直前の状態に戻すことエは、処理に失敗したとき、呼び出す前の状態に戻すことを説明しています。これはロールバックの考え方で、障害から回復するための仕組みです。関数の呼び出し方とは関係がないので、再帰呼出しの説明ではありません。
補足
再帰では、呼び出すたびに戻り先や局所変数がスタックに積まれていきます。そのため、再帰が深くなりすぎるとスタックが足りなくなることがあります。同じ処理はループに書き換えられる場合も多く、そうすればスタックの使用を抑えられます。
POINT
- 再帰呼出しとは、関数が処理の途中で自分自身を呼び出すことです。
- 再帰には、呼び出しを止める終了条件が必要です。終了条件がないと呼び出しが終わりません。
- 事象に応じて処理する方式はイベントドリブン、失敗時に元の状態に戻す処理はロールバックと区別して覚えます。
- 代表的な例は階乗の計算や木構造のたどり方で、大きな問題を同じ形の小さな問題に分けて解きます。