Fibonacci..so slow by Recursion

[Underdogger]

Recursion ver.

$start = ""
MsgBox(0, "",_fibo(40) &@CRLF &"Spend: " &TimerDiff($start) &" Sec")

Func _fibo($f)
$start = TimerInit()
If $f <= 1 Then
Return 1
Else
Return _fibo($f - 1) + _fibo($f - 2)
EndIf
EndFunc

Why is it run so slowly.....??

************************************************************

For ver.

$start = ""
MsgBox(0, "", _fibloop(40) &@CRLF &"Spend: " &TimerDiff($start) &" Sec")
Func _fibloop($s)
$start = TimerInit()
$a = 1
$b = 1
For $i = 2 To $s
$temp = $a
$a = $a + $b
$b = $temp
Next
Return $a
EndFunc

Be Fast!!

[water]

Search the forum and you will find a lot of scripts for Fibonacci.

Maybe they show what to change in your code.

[DicatoroftheUSA]

Recursion is almost always slower that iteration, I cannot say for certian, it is because of having to reinitialize variables in memory. But it would probably help if you put your timerinit outside of the recursion func, and recursions functions benefit from global variables.

Edited February 8, 2013 by DicatoroftheUSA

[guinness]

You mean static not global.

[DicatoroftheUSA]

  On 2/8/2013 at 5:36 PM, 'guinness said:

You mean static not global.

Yeah, I keep forgetting about that static. I almost always used iteration. Recursion always confuses me for some reason.

Edited February 8, 2013 by DicatoroftheUSA

[Melba23]

Underdogger,

This is as fast as I can get a recursive one to run:

Global $iTotal = 0

$start_rec = TimerInit()
_Fibo_Rec(1, 1, 1, 40)
$nTime_Rec = TimerDiff($start_rec)

Func _Fibo_Rec($iCount, $iCurr, $iPrev, $iLimit)

    $iNext = $iCurr + $iPrev
    $iTotal = $iNext
    If $iCount + 1 = $iLimit Then Return
    _Fibo_Rec($iCount + 1, $iNext, $iCurr, $iLimit)

EndFunc   ;==>_Fibo_Rec

$start_Loop = TimerInit()
MsgBox(0, "", _fibloop(40) & @CRLF & TimerDiff($start_Loop) & " ms" & @CRLF & @CRLF & $iTotal & @CRLF & $nTime_Rec & " ms")

Func _fibloop($s)
    $a = 1
    $b = 1
    For $i = 2 To $s
        $temp = $a
        $a = $a + $b
        $b = $temp
    Next
    Return $a
EndFunc   ;==>_fibloop

There is a lot of overhead in recursive functions as the whole stack has to be saved and reloaded for each call - so I am not really surprised that it takes longer.

M23

[Underdogger]

Thanks guys!

Works great!