c++ - 将递归函数重写为非递归函数

Question

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

}

你好，我需要重写这个函数，这样它就没有递归了。我尝试用数学方法解决这个问题，但无济于事。我是编程新手，所以任何帮助将不胜感激。提前致谢!

Answer 1

我认为您的问题中确实应该是 if(x>0)。

然后检查您的函数，我们看到 foo(0)=1 否则 foo(x)=(x-1)+2*foo(x-1)。因此 foo(x) 只依赖于 foo(x-1)。因此，您可以简单地使用迭代来推进结果

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(x>=0)，我将它作为练习留给您修改代码。