再起になってますか？[C++]

質問

再起を使って総和のプログラムをつくったのですが、ちゃんと再起に
なってるのか自信がないので教えてください。
これはほんの一部のコードなんですが
computeRecursiveSum()の中のreturn( computeSum() );
の部分があってるのかわかりません。

本やそこらのサイトをみてみるとこの部分は、
return(n+Sum(n-1)); という風になっているのですが
下のような書き方してもよろしいのでしょうか？
一応、正しい答えはでます。

int Summation::computeSum() const{
　　int a=0;
　　for (int i=0; i<=number; i++){
　　　　a = i*(i+1)/2;
　　}
　　return a;
}
int Summation::computeRecursiveSum() const {
　　int n = number;
　　if ( n < 0 )
　　　　return (-1);
　　else if ( n = 0 )
　　　　return (0);
　　else
　　　　return( computeSum() );
}

回答No.1

betagamma · ベストアンサー

結論からいうと、なっていません。
それから、再起ではなく、再帰です。
ただ、非常に巧妙に、正しい答えはでていますね。どうして正しい答えがでるのか、行番号をつけて、順に追ってみていきましょう。
1:int Summation::computeRecursiveSum() const {
2:　　int n = number;
3:　　if ( n < 0 )
4:　　　　return (-1);
5:　　else if ( n = 0 )
6:　　　　return (0);
7:　　else
8:　　　　return( computeSum() );
9:}
まず、5行目に間違いがあり、n==0のはずです。n=0は、nに0を代入しろ、という意味です。if(0){}else{printf("Hello");}などとやってみるとわかるのですが、if(計算式)で、計算式の結果が0になる場合は、成り立たない(false)とみなされるんですね。したがって、7行目のelseをこえて、8行目のreturn (computeSum())に行きます。

computeSumでは何をやっているのでしょうか？
1:int Summation::computeSum() const{
2:　　int a=0;
3:　　for (int i=0; i<=number; i++){
4:　　　　a = i*(i+1)/2;
5:　　}
6:　　return a;
7:}
ですね。これは、大変無駄なことをやっていることがわかりますか？4行目のa=i*(i+1)/2は、総和を計算する式ですね。ただ、これは、
a=1*(1+1)/2
a=2*(2+1)/2
a=3*(3+1)/2
...
a=number*(number+1)/2
をずーっと羅列したのと同じことになります。最後のa=number*(number+1)/2だけ計算すれば、答えは求まりますよね？a=で値を上書きしている部分は全部無駄です。

正しい答えは、次のようになります。
int Summation::computeRecursiveSum(int n) {
if(n==0)return 0;
else return n+computeRecursiveSum(n-1);
}
です。

お礼

解説どうもありがとうございます。
自分でもなにかがおかしいと思ってのですっきりしました。

回答No.4

noname#30727

n
Σ k
k=1

↑のような式はループを使って計算します。
ループを使わなくてもazexさんが書かれている i*(i+1)/2で計算できますが、
両者を混ぜてしまってはうまくない。

ループで計算する場合は、
int a = 0;
for (int i = 1; i <= number; i++) {
a += i;
}

これを再帰で計算するのですが、再帰というのは自分自身を直接または間接的に
呼び出す事を指します。computeRecursiveSum()がcomputeRecursiveSum()を
呼び出していないので再帰とは言えません。

お礼

回答ありがとうございます。
確かにループのなかにあの式があるのは不自然ですね。
全くきづきませんでした。

回答No.3

επιστημη（@episteme）

再帰になっていません。自分自身を呼び出していないから。

お礼

ご指摘ありがとうございます。

回答No.2

JaritenCat

No.1に補足

＞正しい答えは、次のようになります。
＞int Summation::computeRecursiveSum(int n) {
＞if(n==0)return 0;
＞else return n+computeRecursiveSum(n-1);
＞}

nが負だと困るので
if(n<=0)return 0;
の方がいいかと。。

お礼

補足ありがとうございます。