再帰関数の流れを教えていただきたいです。

Question

こちらの問題の解答コード(以下に載せました)で再帰関数の基本を学びたいのですが再帰関数を解説してるブログを見ても理解できません。。
######質問内容
.if (x==1) return 1;というのがベースケース、return f(x/2)*2+1;が再帰ステップと呼ばれるものだと思うのですが再帰関数の解説ブログには異口同音に「再帰ステップでの再帰呼び出しが最終的にベースケースに到達する」と書いてあります。今回例えばxに19という数字を入れたときにどういう流れを経てx==1に辿り着くのか詳細に教えてくださると嬉しいです。自分はxに19を与える→x!=1だからf(x/2)*2+1に放り込まれる→f(9)*2+1を返す(どこに？)ぐらいで理解が止まっています。よろしくお願い致します。

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
  if (x==1) return 1;
  return f(x/2)*2+1;
}
  
int main(){
  long long h;
  cin >> h;
  cout << f(h) << endl;
  return 0;
}

Answer 1

xに19を与える→x!=1だからf(x/2)*2+1に放り込まれる→f(9)*2+1を返す

同じステップを続けるだけです。f(9)からはf(4)を呼び出すコードになり、f(4)はf(2)を呼び出し、最終的にはf(2)が返り値の決まっているf(1)を呼び出します。

C++では、（staticや関数外の変数を読み書きする場合は別として）「再帰呼び出し」と言っても全く特別なことはなく、単にたまたま同じ名前の関数を呼び出していると考えて問題ありません。「f(19)からf(9)を呼び出した」からと言って両者が干渉することはなく、f(9)は単体で呼び出したときと同じ動作をします。

Comments

[cunwe]

ベストアンサーはひとりしか選べないので代わりに＋高評価１させていただきました。ご回答ありがとうございました。

Answer 2

#include <bits/stdc++.h>
using namespace std;

long long f(long long x) {
  if (x==1) return 1;
  long long wk = f(x/2);
  return wk*2+1;
}

int main(){
  long long h;
  cin >> h;
  cout << f(h) << endl;
  return 0;
}

説明上wkに変数を入れるとしてh=19のときの説明だから
cout << f(19) << endl;でf(19)で関数呼び出される・・・mとおく

f(19)関数内で long long wk = f(x/2);でwkに値代入するためにf(19/2)が呼び出される(f(9))・・・Aとおく

f(9)関数内で long long wk = f(x/2);でwkに値代入するためにf(9/2)が呼び出される(f(4))・・・Bとおく

f(4)関数内で long long wk = f(x/2);でwkに値代入するためにf(4/2)が呼び出される(f(2))・・・Cとおく

f(2)関数内で long long wk = f(x/2);でwkに値代入するためにf(2/2)が呼び出される(f(1))・・・Dとおく

(f(1))なので if (x==1) return 1;が呼び出されて1を返す(Dのwkに1が入る)

Dのwk代入後の処理でreturn wk*2+1;なので1*2+1を返す(Cのwkに3が入る)

Cのwk代入後の処理でreturn wk*2+1;なので3*2+1を返す(Bのwkに7が入る)

Bのwk代入後の処理でreturn wk*2+1;なので7*2+1を返す(Aのwkに15が入る)

Aのwk代入後の処理でreturn wk*2+1;なので15*2+1を返す(mのf(19)が31となる)

mのf(19)は31が帰ってきたので３１を出す

Comments

[cunwe]

ベストアンサーはひとりしか選べないので代わりに＋高評価１させていただきました。ご回答ありがとうございました。

Answer 3

１　main() から f(19) を呼び出した時、x = 19 なので

return f(x/2)*2+1;

の際にまず f(19/2) つまり f(9) が呼ばれます。

２ f(9) が呼ばれると該当の return 文で f(9/2) つまり f(4) が呼ばれます。

３　f(4) が呼ばれると該当の return 文で f(4/2) つまり f(2) が呼ばれます。

４　f(2) が呼ばれると該当の return 文で f(2/1) つまり f(1) が呼ばれます。

５　f(1) が呼ばれると x = 1 なので if (x==1) return 1; で f(1) を呼んだ f(2) に 1 が return されます。

６ f(2) では、f(x/2)*2+1 が 1*2+1 つまり 3 になるので f(2) を呼んだ f(4) に 3 が return されます。

７ f(4) では、f(x/2)*2+1 が 3*2+1 つまり 7 になるので f(4) を呼んだ f(9) に 7 が返されます。

８ f(9) では、f(x/2)*2+1 が 7*2+1 つまり 15 になるので f(9) を呼んだ f(19) に 15 が返されます。

９ f(19) では、f(x/2)*2+1 が 15*2+1 つまり 31 になるので f(9) を呼んだ main() に 31 が返されます。

Comments

[cunwe]

他の方のブログを読んだときには気づかなかったのですが、ということは再帰関数内でおこなっているのは、言葉が適切ではないかもしれませんが「行って帰って」という感じなのでしょうか？また、今回のこの再帰関数の計算量というのはどれぐらいなのでしょうか？よろしくお願いいたします。

[Yasumichi]

「行って帰って」に近いですかね。

見た目上の計算回数は、そんなに増えていかないですが、再帰の場合、関数呼び出しのオーバーヘッド等（スタックへの変数の退避等）も考えないといけません。

関数の呼び出し回数だけに着目すると

入力h → 呼び出し回数

10 →　 4
100 → 7
1000 → 10

という感じです。

[cunwe]

だいぶ少ないですね。while文で実装したらTLE(Time Limit Exceeded)したので再帰関数の有用性を実感できました。ありがとうございました！

[Yasumichi]

呼び出し回数は少ないですが、ほかにも考慮に入れないと正確な計算量はでないみたいです。

[初心者向け] プログラムの計算量を求める方法 - Qiita
https://qiita.com/cotrpepe/items/1f4c38cc9d3e3a5f5e9c

とかだと実際の計算方法は省かれてますね。

> 参考までに、コードに再帰が含まれている場合は、以下の方法で計算量を求めることになります。
>
> 漸化式を解く方法
> 公式を利用する方法

あと、対象が再帰的なデータ構造であるかどうかが再帰を使う場合の一つの指針になると思います。

[cunwe]

計算量が気になったらこのページに戻ってきて見たいと思います。対象が再帰的なデータ構造であるかどうかを見極めらるのにはもう少し時間がかかってしまいそうですが頑張りたいと思います。ありがとうございます。