Sign in to follow this  
Followers 0
Underdogger

Fibonacci..so slow by Recursion

7 posts in this topic

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!! ;)

Share this post


Link to post
Share on other sites



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

Maybe they show what to change in your code.


My UDFs and Tutorials:

Spoiler

UDFs:
Active Directory (NEW 2017-04-18 - Version 1.4.8.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX (NEW 2017-02-27 - Version 1.3.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2015-04-01 - Version 0.4.0.0) - Download - General Help & Support - Example Scripts
Excel - Example Scripts - Wiki
Word - Wiki
PowerPoint (2015-06-06 - Version 0.0.5.0) - Download - General Help & Support

Tutorials:
ADO - Wiki

 

Share this post


Link to post
Share on other sites

#3 ·  Posted (edited)

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 by DicatoroftheUSA

Share this post


Link to post
Share on other sites

You mean static not global.


_AdapterConnections()_AlwaysRun()_AppMon()_AppMonEx()_BinaryBin()_CheckMsgBox()_CmdLineRaw()_ContextMenu()_ConvertLHWebColor()/_ConvertSHWebColor()_DesktopDimensions()_DisplayPassword()_DotNet_Load()/_DotNet_Unload()_Fibonacci()_FileCompare()_FileCompareContents()_FileNameByHandle()_FilePrefix/SRE()_FindInFile()_GetBackgroundColor()/_SetBackgroundColor()_GetConrolID()_GetCtrlClass()_GetDirectoryFormat()_GetDriveMediaType()_GetFilename()/_GetFilenameExt()_GetHardwareID()_GetIP()_GetIP_Country()_GetOSLanguage()_GetSavedSource()_GetStringSize()_GetSystemPaths()_GetURLImage()_GIFImage()_GoogleWeather()_GUICtrlCreateGroup()_GUICtrlListBox_CreateArray()_GUICtrlListView_CreateArray()_GUICtrlListView_SaveCSV()_GUICtrlListView_SaveHTML()_GUICtrlListView_SaveTxt()_GUICtrlListView_SaveXML()_GUICtrlMenu_Recent()_GUICtrlMenu_SetItemImage()_GUICtrlTreeView_CreateArray()_GUIDisable()_GUIImageList_SetIconFromHandle()_GUIRegisterMsg()_GUISetIcon()_Icon_Clear()/_Icon_Set()_IdleTime()_InetGet()_InetGetGUI()_InetGetProgress()_IPDetails()_IsFileOlder()_IsGUID()_IsHex()_IsPalindrome()_IsRegKey()_IsStringRegExp()_IsSystemDrive()_IsUPX()_IsValidType()_IsWebColor()_Language()_Log()_MicrosoftInternetConnectivity()_MSDNDataType()_PathFull/GetRelative/Split()_PathSplitEx()_PrintFromArray()_ProgressSetMarquee()_ReDim()_RockPaperScissors()/_RockPaperScissorsLizardSpock()_ScrollingCredits_SelfDelete()_SelfRename()_SelfUpdate()_SendTo()_ShellAll()_ShellFile()_ShellFolder()_SingletonHWID()_SingletonPID()_Startup()_StringCompact()_StringIsValid()_StringRegExpMetaCharacters()_StringReplaceWholeWord()_StringStripChars()_Temperature()_TrialPeriod()_UKToUSDate()/_USToUKDate()_WinAPI_Create_CTL_CODE()_WinAPI_CreateGUID()_WMIDateStringToDate()/_DateToWMIDateString()Au3 script parsingAutoIt SearchAutoIt3 PortableAutoIt3WrapperToPragmaAutoItWinGetTitle()/AutoItWinSetTitle()CodingDirToHTML5FileInstallrFileReadLastChars()GeoIP databaseGUI - Only Close ButtonGUI ExamplesGUICtrlDeleteImage()GUICtrlGetBkColor()GUICtrlGetStyle()GUIEventsGUIGetBkColor()Int_Parse() & Int_TryParse()IsISBN()LockFile()Mapping CtrlIDsOOP in AutoItParseHeadersToSciTE()PasswordValidPasteBinPosts Per DayPreExpandProtect GlobalsQueue()Resource UpdateResourcesExSciTE JumpSettings INISHELLHOOKShunting-YardSignature CreatorStack()Stopwatch()StringAddLF()/StringStripLF()StringEOLToCRLF()VSCROLLWM_COPYDATAMore Examples...

Updated: 04/09/2015

Share this post


Link to post
Share on other sites

#5 ·  Posted (edited)

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 by DicatoroftheUSA

Share this post


Link to post
Share on other sites

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


Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind._______My UDFs:

Spoiler

ArrayMultiColSort ---- Sort arrays on multiple columns
ChooseFileFolder ---- Single and multiple selections from specified path treeview listing
Date_Time_Convert -- Easily convert date/time formats, including the language used
ExtMsgBox --------- A highly customisable replacement for MsgBox
GUIExtender -------- Extend and retract multiple sections within a GUI
GUIFrame ---------- Subdivide GUIs into many adjustable frames
GUIListViewEx ------- Insert, delete, move, drag, sort, edit and colour ListView items
GUITreeViewEx ------ Check/clear parent and child checkboxes in a TreeView
Marquee ----------- Scrolling tickertape GUIs
NoFocusLines ------- Remove the dotted focus lines from buttons, sliders, radios and checkboxes
Notify ------------- Small notifications on the edge of the display
Scrollbars ----------Automatically sized scrollbars with a single command
StringSize ---------- Automatically size controls to fit text
Toast -------------- Small GUIs which pop out of the notification area

 

Share this post


Link to post
Share on other sites

:thumbsup:

Thanks guys!

Works great!

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0