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

当你处理递归时，你必须了解函数代码的两个主要部分：一个在前进的路上执行，一个在返回的路上执行：

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;
}

我们可以很容易地区分我们的两个部分。前进的道路是：

times++;
if(x) return;

其中我们只是增加了我们的 int 参数times（我们在这里忽略了递归结束的条件）。

回来的路是：

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

这将从最后一次调用到第一次调用（就像示例的第二个版本一样）执行。0因此，就像我们的示例一样，从递归结束前最后一次调用的最小数字（由于递归结束条件而更接近的数字）取到第一个。

于 2013-03-26T14:54:24.050 回答
4

如果我正确理解您的问题：

它应该从高到低打印，但它实际上是从低到高打印。这是为什么？

该行在cout<<"We are now at "<<x/2<<endl;递归调用之后。因此该函数一次又一次地以较小的数量调用自身，直到达到中断标准。具有最小数量的函数调用std::cout，返回第二小的数量执行std::cout，依此类推，直到最后一个执行。

如果您希望以其他顺序获得结果，请将上述行移高两行，以便每次迭代在调用子之前回显。

例子：

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;
}

不相关：全局变量被认为是一种不好的做法。它们有用例，这不是其中之一。我在函数中修复了它。

于 2013-03-26T14:30:40.667 回答