How to write this recursion with loops

If you fiddle with it enough, you can get at least one way that will output the ordered sequence without revisiting it :)

let n = 5

// Recursive 
let rec_str = ''
function rec(n) { 
  if (n != 0) { 
    rec_str += n
    rec(n-1); 
    rec(n-1); 
  } 
}

rec(n)
console.log(rec_str)

// Iterative 
function f(n){
  let str = ''
  
  for (let i=1; i<1<<n; i++){
    let t = i
    let p = n
    let k = (1 << n) - 1

    while (k > 2){
      if (t < 2){
        break 
      } else if (t <= k){
        t = t - 1
        p = p - 1
        k = k >> 1
      } else {
        t = t - k
      }
    }
    str += p
  }
  console.log(str)
}

f(n)

(The code is building a string, which I think should be disallowed according to the rules, but only for demonstration; we could just output the number instead.)

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;
}

For n = 3 for instance

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

Consider the list of indexes; for i > 0 and i <= 2^(m) the index i has the same value as the index i + 2^(m)-1 where m = n - 1. This is true for every n. If you are in the second half of the list, find its correspondent index in the first half by this formula. If the resulting number is 1, the value is m. If not, you are in a lower level of the tree. m = m - 1 and repeat until the index is 1 or m =1, in which case you've reached the end of the tree, print 1.

For instance, with n = 4, this is what happens with all the indexes, at every while step. p(x) means the value x gets printed at that index. A / means that index has already been printed.:

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

Therefore the result is:

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