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.