论坛 › 『 谈天说地 』 › 递归求斐波那契数列的第n项

haijie1223 发表于 2018-1-21 16:49:38

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

数列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 发表于 2018-1-21 17:27:28

这个用递归会慢死啊

afan 发表于 2018-1-21 18:26:02

几乎不用递归，就是因为效率问题
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

绿色风 发表于 2018-1-21 21:55:22

大赞一下，都历害

449199199 发表于 2018-3-26 00:58:31

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

查看完整版本: 递归求斐波那契数列的第n项