# Recursion against iteration

A basic definition of recursion would be “call a subroutine from within the same subroutine”. And iteration would be travelling through several objects in a repeat/end repeat statement (items in a list, a growing number, etc.).

Here is the classic example of recursion (a factorial computation):

``````on factorial(n)
if n > 0 then
return n * (factorial(n - 1))
else
return 1
end if
end factorial
``````

And this is the “iteration version”:

``````on factorial(n)
if n is 0 then return 1
set a to n - 1
repeat while a > 0
set n to n * a
set a to a - 1
end repeat
return n
end factorial
``````

And this is a different example, just in case you feel dizziness reading this code (as me). These will return true if “B” is in a given string (false, if it isn’t):

``````on BisIn(str) --> recursion
considering case
if str's item 1 is "B" then
return true
else
try
return BisIn(text 2 thru -1 of str)
on error
return str is "B"
end try
end if
end considering
end BisIn

on BisIn2(str) --> iteration
considering case
repeat with i from 1 to count str
if str's item i is "B" then return true
end repeat
end considering
return false
end BisIn2
``````

Both concepts share the concept loop, and you may use whatever you find more readable. Be careful, though, with recursion, if you think you may recurse lots of times, as you may get out of memory. When you execute “return again(foo)”, the handler will return the result of executing again the handler “again” with parameters “foo”. If the result of such execution is executing again the handler “again”, you will have then two handlers waiting for a result: the first round, and the second one (waiting for the third execution). And so on… This means that you are storing lots of information in memory (in long recursions) and, depending on application-defined stack’s size (the application running the script), you may get a stack overflow error sooner or later.

Brief note about recursion and stack limits: seems that every app defines its owm stack memory limits. For example, if you try this code in current apps’ versions in OS X 10.4:

``````property x : 0

try
z()
on error
display dialog x
end try

to z()
set x to x + 1
z()
end z
``````

This will display “733” in Apple’s Script Editor (which seems the default value in most of AS runners), and “23815” in Satimage’s Smile.