How to write this recursion with loops

Question

I saw the following as an exercise in a website. It basically says write the following function without using recursion and without using structures like vector, stack, etc:

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

At first I thought it was going to be easy, but I'm suprisingly struggling to accomplish it.

To understand it better, I defined it like a math function as the following:

f(x) = {1 if x = 0, f(x-1) + f(x-1) otherwise} (where + operator means concatenation and - is the normal minus)

However, Unrolling this made it harder, and I'm stuck. Is there any direct way to write it as a loop? And also, more generally, is there an algorithm to solve this type of problems?

Answer 1

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