Rewriting a recursive function to a non-recursive function

Question

int foo(int x)
{   
    if (x >= 0)
    {
        return (x - 1) + 2 * foo(x - 1);
    }
    else
    {
        return 1;
    }

}

Hi, I need to rewrite this function such that it will be free of recursion. I tried solving this mathematically, but to no avail. I am new to programming, so any help will be much appreciated. Thanks in advance!

Answer 1

I assume that it really should be if(x>0) in your question.

Then examining your function, we see that foo(0)=1 and otherwise that foo(x)=(x-1)+2*foo(x-1). Thus foo(x) only depends on foo(x-1). So, you can simply use an iteration to progress the result

int foo(int x)
{
  auto result=1;           // result if x=0
  for(int n=0; n!=x; ++n)  // increment result to desired x
    result=n+2*result;     // corresponds to (x-1)+2*foo(x-1) in original
  return result;
}

If it really was if(x>=0) instead, I leave it as an exercise to you to adapt the code.