如何使用循环编写此递归

Question

我在网站上看到以下内容作为练习。它基本上说不使用递归和不使用向量，堆栈等结构编写以下函数：

void rec(int n) {
        if (n != 0) {
                cout << n << " ";
                rec(n-1);
                rec(n-1);
        }
}

刚开始我以为这会很容易，但是我却很难做到。

为了更好地理解它，我将其定义为数学函数，如下所示：

f（x）= {如果x = 0，则为1，否则为f（x-1）+ f（x-1）}（其中+运算符表示串联，而-是正常减号）

但是，展开此操作会更加困难，而且我被卡住了。有没有直接的方法可以将其编写为循环？而且，更一般而言，是否有一种算法可以解决此类问题？

Answer 1

void loop(int n)
{
    int j = 0;
    int m = n - 1;

    for (int i = 0; i < int(pow(2, n)) - 1; i++)
    {
        j = i;
        if (j == 0)
        {
            std::cout << n << " ";
            continue;
        }
        m = n - 1;
        while (true)
        {
            if (m == 1)
            {
                std::cout << m << " ";
                m = n - 1;
                break;
            }
            if (j >= int(pow(2, m)))
            {
                j = j - int(pow(2, m)) + 1;
            }
            if (j == 1)
            {
                std::cout << m << " ";
                m = n - 1;
                break;
            }
            else
            {
                j--;
            }
            m--;
        }
    }
    std::cout << std::endl;
}

以 n = 3 为例

out =     [3 2 1 1 2 1 1] 
indexes = [0 1 2 3 4 5 6] 

考虑索引列表；对于 i > 0 且 i <= 2^(m)，索引 i 与索引 i + 2^(m)-1 具有相同的值，其中 m = n - 1。对于每个 n 都是如此。如果在列表的后半部分，则通过此公式在前半部分找到其对应的索引。如果结果数为 1，则值为 m。如果不是，则您位于树的较低级别。m = m - 1 并重复直到索引为 1 或 m =1，在这种情况下您已到达树的末尾，打印 1。

例如，当 n = 4 时，这就是在每个 while 步骤中所有索引都会发生的情况。p(x) 表示在该索引处打印值 x。A / 表示索引已被打印：

n = 4,m = 3
[0 1 2 3 4 5 6 7 8 9 10 11 12 13 14]
m = 3
[p(n=4) 1 2 3 4 5 6 7 8 9 10 11 12 13 14]
if(i >=2^3) -> i = i -2^3 + 1)
[/ 1 2 3 4 5 6 7 1 2 3 4 5 6 7]
if(i == 1) -> print m, else i = i -1
[/ p(3) 1 2 3 4 5 6 p(3)1 2 3 4 5 6]

m = 2
if (i >=2^2) -> i = i - 2^2 +1
[/ / 1 2 3 1 2 3 / 1 2 3 1 2 3] 
if(i == 1) -> print m, else i = i -1
[ / / p(2) 1 2 p(2) 1 2 / p(2) 1 2 p(2) 1 2]
m = 1
if (m == 1) -> print(m)
[ / / / p(1) p(1) / p(1) p(1) / / p(1) p(1) / p(1) p(1)]

因此结果是：

[4 3 2 1 1 2 1 1 3 2 1 1 2 1 1]