Recursive

本物のページはこちら→recursive

繰り返し回数のわからないfor文
深さ優先探索は再起かstackで実装できる。
2重for文にすることによっても実装はできる。

再帰の実装の仕方

int recursive(){
 if(again){
    recursive();
}else{
    return 1;
}
}

再起には、
  • 再起を抜ける条件
  • 再起する条件

で分岐する必要がある。
ずーっと再起から抜けられないと、StackOverFlowのエラーになる。
これは、関数をいっぱい呼び出しすぎて、関数用のメモリ領域であるスタック領域がいっぱいになりすぎちゃった、という意味である。
いわゆる、無限ループのようなもの。
現実世界で言うと、合わせ鏡のような状況だ。

何かの合計値を求める場合

結果の値+=再帰関数(初期値);

というパターンが多い気がする。

再起のデバッグ

私のように再起のことがなかなか頭の中だけでは考えにくい人へ

  int recursive(int depth,vector<int> danceCost,int cost){
      for(int i=0;i<depth;i++)cout<<"\t";//depth 再起の深さを示す引数を作る。その分だけタブでインデントして出力
      cout<<"depth:"<<depth<<" num:"<<danceCost.size()<<" cost:"<<cost<<endl;//次の行は普通の出力

こうすると、再起が深いほどインデントされて出力されてわかりやすい!
出力
danceCost:1
        depth:1 num:2 cost:1
                depth:2 num:1 cost:6
                        depth:3 num:0 cost:10
result = 10 cost = 1
danceCost:4
        depth:1 num:1 cost:14
                depth:2 num:0 cost:19
result = 0 cost = 14
ans:0

TopCoderで再帰の問題

簡単な順に並べます

サポートサイト Wikidot.com