递归打印 n, n-1, n-2,...3,2,1,2,3,...n

Question

你好，我有一个家庭作业问题，我被卡住了..任何提示或技巧将不胜感激。问题是：

用 C++ 编写一个递归函数，将正整数作为参数 n，然后打印 n, n-1, n-2,...3,2,1,2,3,...n。您的算法进行了多少次递归调用？你算法的最坏情况运行时间是多少？

我卡在了第一部分。编写一个打印 n, n-1, n-2,...3,2,1,2,3,...n

的递归函数

到目前为止我有：

print(int n)
{
    if (n==0)
    return;
    cout<<n<<" ";
    print(n-1);

return;
}

但这只会打印从 n 到 1 我不知道如何仅使用一个参数和递归的单个函数从 2 打印到 n。

我试过这个：它给出了正确的输出但是有一个循环并且有两个参数：

p and z has the same value. 

void print(int p,int z)
{

if (p==0)
    {
        for(int x=2;x<=z; x++)
            cout<<x<<" ";
        return;
    }
    else

    cout<<p<<" ";
    print(p-1,z);

return;
}

非常感谢任何提示或提示。

所以它现在可以工作了，但我无法理解如何（评论中的问题）：

void print(int n)
{

if (n==1){
    cout<<n;
    return;
    }
else
    cout<< n;
    print(n-1); // how does it get passed this? to the line below?
    cout<<n;    // print(n-1) takes it back to the top?
return;
}

Answer 1

你想要的输出是镜像的，所以你可以有这一系列的步骤：

print num
recursive step on num-1
print num again

这就是递归的情况。现在您需要一个适当的基本情况来停止递归，这应该不难。

给定伪代码：

recursive_print(n):
    if n == 1:
        print 1
        return

    print n
    recursive_print(n-1)
    print n

（如果您愿意，只需查看您的解决方案）。

我们来追踪一下。一个点将标记我们在打印方面的进展。

. recursive_print(3)    // Haven't printed anything
3 . recursive_print(2) 3    // Print the 3
3 2 . recursive_print(1) 2 3    //Print 2
3 2 1 . 2 3         // Print 1
3 2 1 2 . 3         // Print 2
3 2 1 2 3 .         // Print 3

函数的每次展开都会在相对的两边给我们 2 个数字，我们向下构建到“1”，然后返回并打印其余数字。

"unrolling"如图所示：

如果你剥离函数并留下一系列命令，你将得到：

print 3
    print 2
        print 1
    print 2
print 3

其中每个缩进表示不同的功能。

Answer 2

答案比你想象的要简单。

递归调用与常规调用没有什么不同。唯一的区别是被调用的函数也是调用者，所以你需要确保你不会永远调用它（你已经这样做了）。让我们考虑一下常规调用。如果您有以下代码片段：

statement1
f();
statement2

语句 1 被执行，然后 f 被调用并执行它的事情，然后，在 f 完成后，语句 2 被执行。

现在，让我们考虑一下您的问题。从你写的第二个程序就可以看出你在这个问题上的努力，但是算了，第一个已经很接近答案了。

让我们考虑一下您的函数的作用。它打印从 n 到 0，然后从 0 到 n 的所有数字。第一步，你要打印n，然后打印n-1到0和0到n-1的所有数字，再打印一个n。看到它的走向了吗？

所以，你必须这样做：

print(n)
call f(n-1)
print(n)

希望我的解释足够清楚。

Answer 3

这更像是 hack -- 使用 std::stream 而不是递归...

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

int main() {
    rec(3);
}

打印

递归打印 n, n-1, n-2,...3,2,1,2,3,...n

recursively print n, n-1, n-2,...3,2,1,2,3,...n

c++

algorithm

recursion