递归求斐波那契数列的第n项

haijie1223

数列1、1、2、3、5、8、13、21、34、……，前2项为1、1，之后的每一项等于前2项之和，称之为斐波那契数列。
请使用递归求出斐波那契数列的第n项。
这是其他论坛转过来的，正好前几天群里有人问这个代码，就发过来吧。简单的很，但是递归的效率很低，抛砖引玉，希望有更强大的算法代码。

For $i = 0 To 5
        ConsoleWrite('_CalcFbn(' & $i & ')=' & _CalcFbn($i) & @CRLF)
Next
Func _CalcFbn($n)
        If $n < 2 Then Return $n
        Return _CalcFbn($n - 1) + _CalcFbn($n - 2);
EndFunc   ;==>_CalcFbn

afan

这个用递归会慢死啊

afan

几乎不用递归，就是因为效率问题

Local $ii = 60  ;位
Local $nX = ___Test($ii)
MsgBox(0, '', $ii & ' = ' & $nX)

Func ___Test($ii, $n0 = 0, $n1 = 1, $nX = 1)
        If $ii = 1 Then Return $nX
        $ii -= 1
        $nX = $n0 + $n1
        $n0 = $n1
        $n1 = $nX
        Return ___Test($ii, $n0, $n1, $nX)
EndFunc   ;==>___Test

绿色风

大赞一下，都历害

449199199

在这里学到了函数内调用自己。我穷只有一个金币了