Jump to content

Fibonacci..so slow by Recursion

Underdogger
 Share

Recommended Posts

Underdogger Wayfarer

Underdogger

Posted
Posted

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

Link to comment
Share on other sites
water Universalist

water

Posted
Posted

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 2022-02-19 - Version 1.6.1.0) - Download - General Help & Support - Example Scripts - Wiki
ExcelChart (2017-07-21 - Version 0.4.0.1) - Download - General Help & Support - Example Scripts
OutlookEX (2021-11-16 - Version 1.7.0.0) - Download - General Help & Support - Example Scripts - Wiki
OutlookEX_GUI (2021-04-13 - Version 1.4.0.0) - Download
Outlook Tools (2019-07-22 - Version 0.6.0.0) - Download - General Help & Support - Wiki
PowerPoint (2021-08-31 - Version 1.5.0.0) - Download - General Help & Support - Example Scripts - Wiki
Task Scheduler (NEW 2022-07-28 - Version 1.6.0.1) - Download - General Help & Support - Wiki

Standard UDFs:
Excel - Example Scripts - Wiki
Word - Wiki

Tutorials:
ADO - Wiki
WebDriver - Wiki

 

Link to comment
Share on other sites
DicatoroftheUSA Universalist

DicatoroftheUSA

Posted
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

Statism is violence, Taxation is theft.

Autoit Wiki

Link to comment
Share on other sites
guinness Universalist

guinness

Posted
Posted

You mean static not global.

UDF List:

 
_AdapterConnections() • _AlwaysRun() • _AppMon() • _AppMonEx() • _ArrayFilter/_ArrayReduce • _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 parsing • AutoIt Search • AutoIt3 Portable • AutoIt3WrapperToPragma • AutoItWinGetTitle()/AutoItWinSetTitle() • Coding • DirToHTML5 • FileInstallr • FileReadLastChars() • GeoIP database • GUI - Only Close Button • GUI Examples • GUICtrlDeleteImage() • GUICtrlGetBkColor() • GUICtrlGetStyle() • GUIEvents • GUIGetBkColor() • Int_Parse() & Int_TryParse() • IsISBN() • LockFile() • Mapping CtrlIDs • OOP in AutoIt • ParseHeadersToSciTE() • PasswordValid • PasteBin • Posts Per Day • PreExpand • Protect Globals • Queue() • Resource Update • ResourcesEx • SciTE Jump • Settings INI • SHELLHOOK • Shunting-Yard • Signature Creator • Stack() • Stopwatch() • StringAddLF()/StringStripLF() • StringEOLToCRLF() • VSCROLL • WM_COPYDATA • More Examples...

Updated: 22/04/2018

Link to comment
Share on other sites
  • Moderators
Melba23 Universalist

Melba23

Posted
  • Moderators
Posted

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

Public_Domain.png.2d871819fcb9957cf44f4514551a2935.png Any of my own code posted anywhere on the forum is available for use by others without any restriction of any kind

Open spoiler to see 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

 

Link to comment
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
 Share
Go to topic listing

  • Recently Browsing   0 members

    • No registered users viewing this page.
×
×
  • Create New...