0

再帰関数がわかりません。

私は私を助けるためにこのコードを書きましたが、なぜそれがそのように機能するのか理解できません。

0からn/2 i入力までのステップを逆方向に出力しますが、再帰的に実行されたため、低から高にスキップしたすべてのステップを印刷する理由がわかりません。私は近くにいますが、まだそこにはいません...

#include <iostream>
#include <conio.h>
using namespace std;

int recursiv(int );

int times;

int main(){    
    int x;    
    cout<<"Imput number\n";
    cin>>x;    
    recursiv(x);

    getch();
  return 0;
}
int recursiv(int x){

    times++;
    if(x)
    recursiv(x/2);
    cout<<"We are now at "<<x/2<<endl;
    if (!x)
    cout<< "We reached "<<x<<" but it took "<<times-1<< " steps\n";
    return 0;
}
4

2 に答える 2

4

私があなたの質問を正しく理解している場合：

高から低に印刷する必要がありますが、実際には低から高に印刷します。何故ですか？

この行cout<<"We are now at "<<x/2<<endl;は、再帰の呼び出しの後にあります。そのため、関数は、ブレーク基準に達するまで、少量で何度も何度も自分自身を呼び出します。最小量の関数はを呼び出し、std::cout2番目に最小量を返す関数std::coutはそれを実行し、最後の関数がそれを実行するまで続きます。

別の順序で結果が必要な場合は、上記の行を2行上に移動して、子を呼び出す前に各反復がエコーするようにします。

例：

int recursiv(int x, int times = 0) {
  std::cout << "We are now at " << x/2 << std::endl;

  if(x)
    return recursiv(x/2, times + 1);
  else
    std::cout << "We reached " << x << " but it took " << times << " steps" << std::endl;

  return 0;
}

無関係：グローバル変数は悪い習慣と見なされます。それらのユースケースがありますが、これはそれらの1つではありません。関数内で修正しました。

于 2013-03-26T14:30:40.667 に答える
4

再帰を扱うときは、関数コードの2つの主要な部分を理解する必要があります。1つは前に実行され、もう1つは後に実行されます。

void X() {
    // way forward
    X();
    // way back
}

再帰が終了するまで関数を何度も呼び出しながら、順方向部分が実行されます。最後の呼び出しから最初の呼び出しに戻るときに、戻る方法が実行されます。

void print(int x) {
    if (!x) return; // end of recursion
    std::cout << x << " ";
    print(x-1);
}

上記の例には、先に進む途中std::cout << xに含まれています。これは、呼び出しが次のように出力されることを意味します。print(5)5 4 3 2 1

void print(int x) {
    if (!x) return; // end of recursion
    print(x-1);
    std::cout << x << " ";
}

上記の例では、実際の印刷を関数の途中に移動しました。これは、同じ呼び出しで次のprint(5)ように印刷されることを意味します1 2 3 4 5。

あなたの関数を取り上げましょう（少しクリーンアップされました）：

int recursiv(int x){
    times++;
    if(!x) return 0; // split
    recursiv(x/2);
    cout << "We are now at "<< x / 2 << endl;
    return 0;
}

2つの部分を非常に簡単に区別できます。今後の方向性は次のとおりです。

times++;
if(x) return;

ここでは、intパラメーターをインクリメントするtimesだけです（ここでは、再帰の終了の条件を無視します）。

戻る方法は次のとおりです。

cout<<"We are now at "<<x/2<<endl;
return 0;

これは、最後の呼び出しから最初の呼び出しまで実行されます（例の2番目のバージョンと同じように）。0したがって、例のように、再帰が終了する前に最後に呼び出された最小の番号（再帰の終了条件のために近い番号）から最初の番号に移動します。

于 2013-03-26T14:54:24.050 に答える