如何使用循环编写此递归

debugcn 发表于 Dev

北海

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

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）}（其中+运算符表示串联，而-是正常减号）

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

亚诺斯佩


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的情况下，所有索引在每一步中都会发生这种情况。p（x）表示值x在该索引处打印。/表示索引已经被打印。

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)]

因此结果是：