Recursive vs Iterative

[wraithdu]

So I know this has been discussed before, and there's a wiki article on it, but I wanted to get some more opinions. Pros and cons anyone?

From my testing, aside from the recursion limits discussed in the wiki article (which is actually lower for x64 EXEs, 1898 IIRC), I didn't notice any performance difference. I tested returning arrays of all files and folders on my C: drive, and both versions were nearly identical at just under 9 seconds. To boot, there's no way that recursion limit was anywhere near being reached.

As an exercise I converted the recursive functions in my _SecureDelete UDF and some of my other projects to iterative versions, and came up with the below.

Iterative Pros:

- simpler handling of one-time tasks such as function initializations, parameters, and error handling/recording

Cons:

- can result in significantly longer and more complex code (see the _SecureDelete update I just posted, took more code and a clever idea to keep memory usage down while traversing directory trees)

Edited October 1, 2012 by wraithdu

[twitchyliquid64]

on compiled languages, the recursion overhead is much more noticable.

I'm not sure if recursion in autoit has a relative overhead to iteration.

[Mat]

Recursion uses the stack a lot though, whereas iteration could be using just a single register. Function calling overhead in recursion is at least return pointer, base pointer, parameter.

In some cases recursion makes sense. There are a lot of optimisations you can do on tail recursion, and some datatypes like linked lists are far easier to work with recursion. Talk to anyone who has used LISP and they will probably describe to you how beautiful recursion is.

[PhoenixXL]

1. Recursion: When a recursive call is made, the method/process copies or clones itself, making new copy of:

• the code
• the local variables (with their initial values),
• the parameters

2. Iteration : there is no recursive call involved that saves a lot of time and space too as no extra space is needed to store each copy generated in recursion.

Hence I prefer Iteration,

but I use recursion since it makes code reading, cleaning much easier and simultaneously less mental work for the code

for Professional Apps Iteration would be preferable

Edited October 2, 2012 by PhoenixXL

[twitchyliquid64]

*sigh*

in assembly code, this can be reduced to a few instructions.

1 push ebp

2 sub ebp, 4*number of parameters

3 mov DWORD [ebp+___], param (for each param)

4 call func

5 pop ebp

which is the overhead for recursion.

[Spiff59]

I recall one of my instructors listing off what he considered the biggest programming sins.

He showed us some assembler routines that modified their own op codes and ranked "self-modifying code" as the top sin.

Recursive calls came in second. It was a Structured Programming course and being the early 80's he ranked (excessive) use of "go to" as third. So, besides the obvious downside of possibly exhausting the stack, I've always considered the generally negative view of recursion as just a "rule" whose intent (successful or not) is to improve program clarity and ease maintenance.

One night last year when I was bored for a challenge I spent 2 hours trying to cleanly remove the recursion from the (never used?) _ArrayPermute() function. I gave up in frustration... It may be that there are times when recursion is the only way to go?

[OBloodyHell]

Recursion is a remarkably powerful tool that can simplify certain types of coding, at the cost of potentially notable overhead.

The classic example of an easy thing to code recursively is the Factorial function, F(n)= n*F(n-1)

1) You have to be careful you properly code for an end, or the code will run on infinitely until terminated or it causes a resource crash

2) It has to have a finite end, duh.

3) It can be a resource hog, as each iteration of the recursion usually takes a lot of time and setup to save the prior state when calling the new state. Hence, placing a deep recursion that calls itself 1000 times in a loop that runs 100,000 times can be a bit of a bear.

4) Often there is a lot of trash collection overhead, too, as usually it's implemented that allocations are made for each call, and then released, often fairly often and quickly.

Recursion is usually best when you can define the recursive function inclusively as a single function... if it calls other routines a lot, or is a huge, 1000-line code blort, then it's probably better to look if an iterative system will work. The more complex the termination conditions are, the better an iterative solution is likely to be.

====

P.S., Long ago, in a bygone era, I implemented a recursive algorithm in Fortran 77 .... which did not support recursion.

I did it, yes, as you'd expect: by simulating the recursion using iteration.

Edited October 30, 2012 by OBloodyHell

[OBloodyHell]

I recall one of my instructors listing off what he considered the biggest programming sins.

He showed us some assembler routines that modified their own op codes and ranked "self-modifying code" as the top sin.

Recursive calls came in second. It was a Structured Programming course and being the early 80's he ranked (excessive) use of "go to" as third. So, besides the obvious downside of possibly exhausting the stack, I've always considered the generally negative view of recursion as just a "rule" whose intent (successful or not) is to improve program clarity and ease maintenance.

LOL, ya, the old structured programming days.... Your instructor never got over the switch to event driven coding, since it's obvious to me that many coders ignore the whole idea of avoiding "go tos", which is generally what a throw/catch pair is. Current event driven coding ignores black boxing entirely, since you can never really tell when an event is going to steal focus anyway, making a black box impossible.

The real problem is when you get an event-driven coder operating on a procedural environment like SQL, which is a defacto procedural language with some event gew-gaws thrown in... The event coder will be determined to ignore all structural coding rules and code like SQL was event driven, leading to defacto spaghetti code even when the problem doesn't need it. Hint: Avoid Throw/Catch scenarios in SQL.

Structured programming, however, is like anything else -- it can be taken by someone, and they can just run straight off the end of the earth with it.

Anyone who knows the old language APL knows that the prime goal of an APL program is to fit it on a single line. THAT, in APL, is considered "elegant". It's a unique language with a very unique set of goals and qualities (SNOBAL is the only other language I found quite as impressive... and in SNOBAL, recursion isn't a function, it's inherent in the DESIGN).

That didn't stop some idiot from writing a book titled "Structured Programming Techniques In APL".... written by someone who needed a few headbashings with a cluebat.

You should avoid self-modifying code as much as possible, and yes, you should use structured programming techniques when they make sense, but my own experience writing code is that it's quite possible to use a GOTO far more clearly than a complexly interweaved structural construct sometimes. In general, you shouldn't have more than a single goto or two, tops, in any given 100 lines or more of code, or a single function, whichever is smaller, and even there, it's pushing it.

Recursion is a powerful tool when used correctly. Most problems it is "correctly" applied to are pretty self-evident, in that they naturally define themselves quickly and easily as a recursive routine. Parsing a line of text or breaking it into a BNF grammar can be such a thing -- Hence my earlier comment about SNOBOL. SNOBOL was designed with text processing (interpreting a computer language) in mind.

[Richard Robertson]

Throw/catch is much more complex than a goto. Throw is a mechanism to provide details on why it failed, not only that it failed. In appropriate debugging modes, high level languages also include stack traces in each exception thrown too. Also take into account the fact that a goto cannot unwind the stack to look for an appropriate error handler.

SQL isn't a programming language. It's a query language. If you try to use it like you would a programming language, you should always expect issues.

[PhoenixXL]

Iteration Wins

Global $nReset = 1000

Local $Timer = TimerInit()
_Recursion()
ConsoleWrite('Recursion TimerDiff:' & TimerDiff($Timer) & @CR)

$Timer = TimerInit()
_Iteration()
ConsoleWrite('Iteration TimerDiff:' & TimerDiff($Timer))

;Recursion
Func _Recursion()
Static $nStart = 0
For $n = 0 To 1000
;Anything
Next
$nStart += 1
If $nStart < $nReset Then Return _Recursion()
Return 1
EndFunc   ;==>_Recursion

;Iteration
Func _Iteration()
Local $nStart = 0
While $nStart < $nReset
For $n = 0 To 1000
;Anything
Next
$nStart += 1
WEnd
Return 1
EndFunc   ;==>_Iteration

Edited October 31, 2012 by PhoenixXL

[JScript]

@PhoenixXL

Very good example, thanks!

JS

[Richard Robertson]

If you know what you are doing, an iterative system will always be faster than a recursive system simply due to the lack of function set up and tear down.

[danielkza]

If you know what you are doing, an iterative system will always be faster than a recursive system simply due to the lack of function set up and tear down.

If the algorithm can be trivially converted to an iterative version (mostly tail recursive algorithms e.g. a factorial function) that is usually true. But for algorithms involving backtracking and/or that need a manual stack in iterative form that may not always be the case: you need to consider the effects of replacing the very optimized native call stack with your own version, how cache locality will affect the performance, etc. For example, if you're targeting an ABI which can pass function arguments through registers, using a manual stack may force the compiler to perform multiple memory reads and writes instead of simply keeping the parameters in registers, possibly untouched, between recursive calls.

Edited October 31, 2012 by danielkza

[jchd]

It may be that there are times when recursion is the only way to go?

Correct. There are well-know functions (mostly useless by themselves) which have been proven not primitive recursive: Ackerman, Sudan, ...

In practice, these academic constructions are only of interest in the theory of computability and such.

But there are a number of real-world domains where solving problems require non-primitive recursion algorithms. Even where large computations traditionally used an iterative algorithm, it now sometimes makes sense to switch to recursion spread on massively parallel processors (e.g. herds of GPUs). This choice largely depends on the fine-grain nature of the algorithms and gory implementation details, like how the parameters can be shared/passed, local/global stacks and memory management ease, hardware features, compiler cleverness, ...

[Jon]

AutoIt relies entirely on recursion for running scripts. Each time you enter a function in fact.

[Tlem]

Hello, I am far from having your skills, but something disturb me.

I take the code PhoenixXL provide and do my own test (just to see the differences).

The first time I launch it on my PC, recursion was faster than iterative, so I do the whole code on a loop :

expandcollapse popup

Global $nReset = 1000
Global $nTestVar

For $Loop = 1 To 5
Local $Timer = TimerInit()
_Recursion()
ConsoleWrite($nTestVar & ' loop - Recursion TimerDiff:' & TimerDiff($Timer) & @TAB & @TAB)

$Timer = TimerInit()
_Iteration()
ConsoleWrite($nTestVar & ' loop - Iteration TimerDiff:' & TimerDiff($Timer) & @CR)
Next

;Recursion
Func _Recursion()
Static $nStart = 0
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
$nStart += 1
If $nStart < $nReset Then Return _Recursion()
Return 1
EndFunc ;==>_Recursion

;Iteration
Func _Iteration()
Local $nStart = 0
While $nStart < $nReset
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
$nStart += 1
WEnd
Return 1
EndFunc ;==>_Iteration

And there is the TimerDiff result :

1000 loop - Recursion TimerDiff:594.156799258006  1000 loop - Iteration TimerDiff:767.341100614743
1000 loop - Recursion TimerDiff:0.593092138805351  1000 loop - Iteration TimerDiff:579.525889463605
1000 loop - Recursion TimerDiff:0.597841345757631  1000 loop - Iteration TimerDiff:580.969369011983
1000 loop - Recursion TimerDiff:0.586946106278871  1000 loop - Iteration TimerDiff:582.377369190777
1000 loop - Recursion TimerDiff:0.593371503920191  1000 loop - Iteration TimerDiff:579.684848213949

I probably miss something, but I didn't see what. Can someone help me to understand?

[UEZ]

Here another topic:

Br,

UEZ

[PhoenixXL]

@Tlem this is because the static variable isnt ever set back to zero

Try this

expandcollapse popup

Global $nReset = 1000
Global $nTestVar

For $Loop = 1 To 5
Local $Timer = TimerInit()
_Recursion()
ConsoleWrite($nTestVar & ' loop - Recursion TimerDiff:' & TimerDiff($Timer) & @TAB & @TAB)

$Timer = TimerInit()
_Iteration()
ConsoleWrite($nTestVar & ' loop - Iteration TimerDiff:' & TimerDiff($Timer) & @CR)
Next

;Recursion
Func _Recursion()
Static $nStart = 0
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
$nStart += 1
If $nStart < $nReset Then Return _Recursion()
$nStart = 0
Return 1
EndFunc   ;==>_Recursion

;Iteration
Func _Iteration()
Local $nStart = 0
While $nStart < $nReset
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
$nStart += 1
WEnd
Return 1
EndFunc   ;==>_Iteration

[PhoenixXL]

A FOR loop in iteration proves to be fastest [100 Times]

Global $nReset = 1000
Global $nTestVar

For $Loop = 1 To 5
Local $Timer = TimerInit()
_Recursion()
ConsoleWrite($nTestVar & ' loop - Recursion TimerDiff:' & TimerDiff($Timer) & @TAB & @TAB)

$Timer = TimerInit()
_Iteration()
ConsoleWrite($nTestVar & ' loop - Iteration TimerDiff:' & TimerDiff($Timer) & @CR)
Next

;Recursion
Func _Recursion()
Static $nStart = 0
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
$nStart += 1
If $nStart < $nReset Then Return _Recursion()
$nStart=0
Return 1
EndFunc ;==>_Recursion

;Iteration
Func _Iteration()
For $n=0 To $nReset
For $n = 0 To 1000
;Anything
$nTestVar = $n
Next
Next
Return 1
EndFunc ;==>_Iteration

Edited November 1, 2012 by PhoenixXL

[Tlem]

Your first message give me explication of what was wrong, but the result didn't make iteration the winner all time :

1000 loop - Recursion TimerDiff:597.365307601944 1000 loop - Iteration TimerDiff:592.773662574433
1000 loop - Recursion TimerDiff:585.603756902064 1000 loop - Iteration TimerDiff:591.226817933564
1000 loop - Recursion TimerDiff:585.188620341412 1000 loop - Iteration TimerDiff:583.973940822088
1000 loop - Recursion TimerDiff:589.34026531305 1000 loop - Iteration TimerDiff:584.71174409038
1000 loop - Recursion TimerDiff:589.252824032105 1000 loop - Iteration TimerDiff:593.518449970597

Your second code is more convincing to show iteration speed, but we can find the same difference of time that I show in my first post (isn't it another bug code?) ^^.

1000 loop - Recursion TimerDiff:595.584913725068 1000 loop - Iteration TimerDiff:0.58275562955627
1000 loop - Recursion TimerDiff:591.154741733935 1000 loop - Iteration TimerDiff:0.637790557179753
1000 loop - Recursion TimerDiff:584.631566302421 1000 loop - Iteration TimerDiff:0.640304843213313
1000 loop - Recursion TimerDiff:589.111465283996 1000 loop - Iteration TimerDiff:0.756800096101599
1000 loop - Recursion TimerDiff:589.041065275056 1000 loop - Iteration TimerDiff:0.588342931853071

Even if I have difficulty in dreading the principle of this recursive version, thank you for the demonstration.

Edited November 1, 2012 by Tlem