c++ - 以某种方式打印的递归函数

Question

完全披露:这是一个硬件问题，我希望您提供最少数量的代码来解释这个问题，我很感激我得到的任何帮助。

基本上我必须编写一个函数，以下列方式递归打印出 2^n-1 项:

The output if n=1 is: 1
The output if n=2 is: 1 2 1
The output if n=3 is: 1 2 1 3 1 2 1
The output if n=4 is: 1 2 1 3 1 2 1 4 1 2 1 3 1 2 1

我不知道我该怎么做。我正在玩斐波那契数列，但那似乎是死胡同。谢谢!

Answer 1

第一步:
先分析问题。你发现它需要递归。

第 2 步:
找出递归方案并建立假设:
对于 n==2 你的答案是 1 2 1 ，对于 n==3 ans 是 1 2 1 3 1 2 1 然后你突然注意到对于 n==3 你正在为 n==2 写第一个答案，然后是 3 并再次回答 n==2所以现在你的假设将是 n-1 的答案，然后是 n，然后再次回答 n-1

第 3 步:
验证假设:
现在你应该验证你是否正确。您检查了 n=2 和 n=4，哇!你找到预期的答案。现在你有了一个经过验证的递归假设。继续写代码吧。

第 4 步:
写下代码:
首先找出基本情况:这里是 n=1 因为你不能更深入。所以我们的函数开始是这样的:

void foo(int n){
    if(n==1){
        cout<<1;
        return ;
    }
}

现在使用我们的假设，写下剩余的代码。

void foo(int n){
    if(n==1){
        cout<<1;
        return ;
    }
    foo(n-1);        //our hypothesis say first we need to write the answer for n-1
    cout<<" "<<n<<" ";  //then writing n itself
    foo(n-1);    //again writing answer for n-1
}