将递归函数重写为非递归函数(Rewriting a recursive function to a non

将递归函数重写为非递归函数(Rewriting a recursive function to a non-recursive function) int foo(int x) { if (x >= 0) { return (x - 1) + 2 * foo(x - 1); } else { return 1; } }

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

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!

最满意答案

我认为你的问题确实应该是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) ，我将它作为练习留给你调整代码。

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.