非負の整数x に対して、次のとおりに定義された手続きF(x )がある。
F(10)で印刷される結果はどれか。
ここで、p div q はp をq で割った商の部分、p mod q はp をq で割った剰余、print(p )はp の値を印刷する。
印刷は、左から右に行う。
F(x ){
if(x > 0){
F(x div 8);
print(x mod 8);
}
}
| ア | 012 | イ | 10 | ウ | 12 | エ | 21 |
答え ウ
【解説】
問題のプログラムに番号を付与します。
| F(x ){ if(x > 0){ F(x div 8); print(x mod 8); } } |
… @ … A … B … C … D … E |
Bの、F(x div 8)を計算すると、10 div 8=1なので、Bの処理はF(1)になります。(1回目の再帰)
F(1)の処理を行います。Aの条件文は成立し、Bを計算します。
Bの、F(x div 8)を計算すると、1 div 8=0なので、Bの処理はF(0)になります。(2回目の再帰)
F(0)の処理を行います。Aの条件文が成立しないので、F(0)は何もしないで抜けます。(2回目の再帰処理の終了)
2回目の再帰の続きを処理します。次は、F(1)のCの処理です。
Cの、x mod 8を計算すると、1 mod 8=1なので、Cの処理は1を印刷します。
これで、F(1)の処理を抜けます。(1回目の再帰処理の終了)
1回目の再帰の続きを処理します。次は、F(10)のCの処理です。
Cの、x mod 8を計算すると、10 mod 8=2なので、Cの処理は2を印刷します。
これで、F(10)の処理を抜けます。
印刷結果は、12(ウ)になります。
【キーワード】
・再帰呼び出し
- 再帰呼び出し(recursive call、リカーシブコール)
手続き(関数)の中で、再び自身の手続きを呼び出すことです。
階乗の計算(Fn=n×Fn-1)や、フィボナッチ数(Fn=Fn-1+Fn-2)のようなアルゴリズム(再帰アルゴリズムといいます。)をプログラミングするのに適しています。
ただし、再帰呼び出しをプログラミングするときには、再帰が行われる度にスタックを消費するので、スタックの容量に注意する必要があります。
もっと、「再帰呼び出し」について調べてみよう。
戻る
一覧へ
次へ