平成24年度春期 データベーススペシャリスト 午前Ⅰ 問3

呼出し構造を整理する視点

再帰的な処理を考えるときは、個々の結果を先に決めつけず、どの処理からどの処理へ移るかという呼出しの構造に注目して、重なりや分岐の現れ方を落ち着いて整理しましょう。

この問題で問われていること

確認する観点を呼出し関係の整理に絞り、処理が始まってから終わるまでに現れる道筋を図や表で追います。同じ段階を重ねて数えたり、別の道筋を混同したりしないことが大切です。

視点

正答を先に想定せず、呼出し元と呼出し先の関係を一つずつ対応づけてください。全体を一度に計算するのではなく、各処理がどの段階に属するかを整理すると、数え漏れや重複に気づきやすくなります。

確認ポイント

• 呼出し元と呼出し先の関係を整理できているか
• 同じ処理を重複して扱っていないか
• 分岐した道筋を混同せず追えているか

正解

ウ

解説

この関数は、nが0になるまで余りを使って再帰的に呼び出されます。呼出しの流れは gcd(135、35) → gcd(35、30) → gcd(30、5) → gcd(5、0) であり、初回を含めて4回です。したがって正しい選択肢はウです。

理由

135を35で割った余りは30、35を30で割った余りは5、30を5で割った余りは0です。そのため、呼出しは gcd(135、35)、gcd(35、30)、gcd(30、5)、gcd(5、0) の順に進みます。初回を1回として数えるので、合計は4回です。

比較

nが0でない間は、gcd(n、m mod n)による次の再帰呼出しが発生します。一方、nが0になった呼出しではmを返して処理が終了し、その後の呼出しはありません。この終了条件の呼出しを含めるかどうかが、選択肢の差になります。

選択肢ア

これは不正解だよ。2回という値は、再帰呼出しを途中までしか数えておらず、n＝0となる終了条件の呼出しまで含めた回数と一致しません。初回を1回とする設問条件にも合わず、必要な呼出しを2回分取り落としている点が誤りです。

選択肢イ

これは不正解だよ。3回は、初回を含めて数える点は意識していますが、余りを使った再帰処理が終了条件に達するまでの全呼出しを数え切れていません。n＝0の引数で実行される最後の呼出しも1回に含める必要があるため、1回不足します。

選択肢ウ（正解）

これは正解だよ。余りを順に求めると、呼出しは gcd(135,35)、gcd(35,30)、gcd(30,5)、gcd(5,0) と進みます。初回の呼出しも1回に数え、n＝0で終了する最後の呼出しも含めると、合計は4回になります。

選択肢エ

これは不正解だよ。5回は、n＝0となった呼出しの後にも、さらにgcdが呼ばれると誤って数えた値です。定義ではn＝0のときmをそのまま返して終了するため、終了条件の呼出しを含めても、その後の追加の1回はありません。したがって1回多い値です。

学習のポイント

再帰関数の終了条件と、初回を含めた呼出し回数の数え方を学習する。