専門学校で情報処理の勉強しております。自宅のパソコンが故障しており使用

質問

専門学校で情報処理の勉強しております。自宅のパソコンが故障しており使用不可能です。実際にプログラムを動かすことが一番なのですが、、大変申し訳ございませんが有識者の方ご教授お願い致します。Q1
class Calculator {
public int count = 0;
public void calc(int n, int p) {
count++;
if (p>n) return;
for (int i=0; i<n; i++) {
calc(n, p+1);
}
}
}

// int nは、キーボードからの入力
Calculator c = new Calculator();
c.calc(n, 0);
System.out.println(c.count);
この時、出力されるc.countはどのくらいですか？ nを用いた式で表現しては頂けませんでしょうか

回答No.1

jjon-com · ベストアンサー

再帰プログラムですから，プログラムを実行して最終的なc.countの値だけ表示しても理解できるものではないと思います。ｎに適当な値を入れて手動でトレースすれば理解できるのではないですか。

--------
ｎ＝１の場合のcalc()メソッドの呼ばれ方は次のとおり。
（注意：右から左に読んでください）

calc(1,2)←calc(1,1)←calc(1,0)

for文によって一方向の枝が伸び，if(p>n) return なのでそれが ｎ＋１段階つまり今回は２段階繰り返される。よって出力される値は３です。

--------
ｎ＝２の場合のcalc()メソッドの呼ばれ方は次のとおり。

calc(2,3)←calc(2,2)←calc(2,1)←calc(2,0)
calc(2,3)／
calc(2,3)←calc(2,2)／
calc(2,3)／
calc(2,3)←calc(2,2)←calc(2,1)／
calc(2,3)／
calc(2,3)←calc(2,2)／
calc(2,3)／

for文によって２方向の枝が伸び，if(p>n) return なのでそれが ｎ＋１段階つまり今回は３段階繰り返される。よって出力される値は15です。

--------
上図で表現してきたcalc()メソッドの呼び出し回数を式で表現すると次のとおり。

３回 ＝ (１×１)＋１＋１
15回 ＝ (２×２×２)＋(２×２)＋２＋１

この結果から，ｎ＝３の場合は次のようになることが推測できるでしょう。

121回 ＝ (３×３×３×３)＋(３×３×３)＋(３×３)＋３＋１

ここまでくればPCの故障は関係ないはずです。ｎを用いたらどう表現できるか考えてみてください。学校の宿題かもしれないので最終的な解答は省略ということで。

お礼

ありがとうございました