c++ - 使用递归的 C++ 中的数字模式函数

Question

使用递归实现以下函数。不要使用任何局部变量或循环。

无效模式(无符号整数 n)

//前提条件:n > 0;

//后置条件:输出由整数行组成。第一行

//是数字n。下一行是数字 2n。下一行是

//4n 的数字，以此类推，直到达到大于

的数字

//4242. 然后向后重复这个数字列表，直到你回来

//到 n.

/* n = 840 的示例输出:

840

1680

3360

6720

6720

3360

1680

840 */

//这是我的代码

#include <iostream>

using namespace std;

void pattern(unsigned int n)
{
    if(n > 0)
    {
        cout << n << endl;
        return pattern(n * 2);
    }else if( n > 4242)
    {
        return pattern(n / 2);
    }
}

int main()
{
    pattern(840);
    return 0;
}

//我的代码只是一直加倍n，并没有分回到原来的n。

Answer 1

其他两个答案指出了其中一个问题(只要 n > 0 为真，n > 4242 也为真)，但另一个问题是您只调用 pattern用n / 2如果n > 4242 .所以你最终会来回“乒乓”。例如，在您在问题中显示的示例输出中，当您点击 6720 时你会减半调用pattern(3360) ，但在下一次调用时，您将使用 3360 调用模式自 3360 < 4242 以来翻了一番.

我认为最明显的方法是将其拆分为两个函数并添加一个“方向” bool 值，指示您是向上还是向下:

void pattern(unsigned int n) {
   pattern_with_dir(n, true);
}

void patten_with_dir(unsigned int n, bool increase) {
    if (n <= 0) {
        return;
    }
    cout << n << endl;
    if (n > 4242) {
        pattern_with_dir(n, false);
    } else {
        if (increase) {
            pattern_with_dir(n * 2, true);
        } else {
            pattern_with_dir(n / 2, false);
        }
    }
}

请注意，您也可以将其拆分为 3 个函数:

void pattern(unsigned int n) {
   pattern_up(n);
}

void pattern_up(unsigned int n) {
    cout << n << endl;
    if (n > 4242) {
        pattern_down(n);
    } else {
       pattern_up(n * 2);
    }
}

void pattern_down(unsigned int n) {
    if (n <= 0) {
        return;
    }
    cout << n << endl;
    pattern_down(n / 2);
}

但最简洁的解决方案是利用递归堆栈来帮助你倒数:

void pattern(unsigned int n) {
   // Going up
   count << n << endl;
   if (n <= 4242) {
       pattern(n*2);
   }
   // this will be called "on the way back down"
   count << n << endl;
}