递归地打印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",然后返回并打印其余的数字.

"展开"如下图所示:

如果你剥离了这些函数并给自己留下一系列命令,你会得到:

print 3
    print 2
        print 1
    print 2
print 3

每个缩进表示不同的功能.