Fibonacci非递归实现

[bruc...@gmail.com]

怎么把这个递归函数转成非递归?
int Fibonacci(int n)
{
if(n<=1) return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}

答:
int foo( int n )
{
if( n<=1 ) return 1;

int a=1, b=1;
for( int i=0; i<n/2; ++i )
{
b += a;
a += b;
}
return n%2 ? a : b;
}

---

[rain.man]

是周星星吗?
久仰大名啊:)

问个DD,递归在C中由于受到栈的物理限制,使得大部分尽量不去那样做,那是否是所有的递归算法都可以用非递归的程序写出来呢?

个人感觉递归概念除了能在描述问题中精炼外,实现中(C)没啥用处

[BruceTeen]

并不是所有递归都可使用循环来代替，比如汉诺塔问题，但可以模仿堆栈方式，将调用过程链表化，也就是使用堆内存来代替栈内存，从而避免栈内存耗尽的情况。

[rain.man]

:P 多谢指教.

再问个问题,希望不要嫌我麻烦哦

我最近在整数构,以前学过点C++(看的出,星星的C++很不错)
里面的STL用起来爽的说,但我现在是用C的,实现数构无非都是些学生代码似的DD,原因是想让自己锻炼一下,不致太懒:),但是自己的代码无论是从效率还是易用性等等方面都是无非比得上STL的,我想在STL的实现代码中参照一下,提升一下自己编码的能力,请问有什么好的资料没有?
谢谢:-)

[BruceTeen]

直接看STL的实现代码呀，最好看SGI版的STL实现，如果看不懂可以买本《STL源码剖析》参考一下

[菜刀]

星星也是我的偶象。:)
我一直误以为所有的递归都可以用循环来代替，不了解汉诺塔问题，星星可否给个简单的例子？

On 6/14/06, BruceTeen <bruc...@gmail.com> wrote:

并不是所有递归都可使用循环来代替，比如汉诺塔问题，但可以模仿堆栈方式，将调用过程链表化，也就是使用堆内存来代替栈内存，从而避免栈内存耗尽的情况。

--
暂不签名

[rain.man]

好的,我学习学习.:)

to楼上:
不用麻烦星星了,我这正好有个例子:
http://groups.google.com/group/DataStream/browse_frm/thread/9f33afc3f9beb750/?hl=zh-CN#
是求国际象棋的马踏点的程序,就是自己写的stack,很累的说
*__*!!

BruceTeen 写道：

> 直接看STL的实现代码呀，最好看SGI版的STL实现，如果看不懂可以买本《STL源码剖析》参考一下
> =讆8颺凤n鲎^t弋5�<�'甸鞳*^奠m�f暼Z� 纷`拽�跒寝琁堋丕伓瑊� �曕-掸!J,拮_5琽t镯 �-q2璼醐>昂鬿h�帮�岩l9璹 �2璼酲�9額镯,騮�棘o╩斦 5-0厚渤建m斐4饌