急问一个递归化为非递归的问题。(20分)

求 f={ n+1 x<2
f(n/2)+f(n/4) x>=2
的非递归算法或程序。
十分着急，请哪位高手帮忙解决。

不用递归。可用递推吧。
从小往大推就是了。
实际上这是一个步长不断扩大的斐波那契数列。
看看
f。n＝2,4,8,16,32,....的值就知道了。

查数据结构的书吧,用堆栈实现递归.

用备忘录法，也可很简单的提高效率

找书看看先，

找到一个c编写的结果
int f(int n){
int p1=0,p2=0;
int * stack1=new stack[n];
int * stack2=new stack[n];
do
uble result,tmp1,tmp2;
if(n<2)
result=n+1;
else
{
stack1[p1++]=n;
tmp1=n/2;
while(tmp1>=2){
stack1[p1++]=tmp1;
}
stack1[p1++]=tmp1;
stack1[p1]=tmp1/2;
p2=p1;
stack2[p2]=stack[p1]+1;
stack2[--p2]=stack[p1-1]+1;
for(;p1>=1;p1--)
stack2[--p2]=stack1[p1+1]+stack2[p1]
result=stack2[0];
}
return result;
}

谢谢各位的帮忙