Wednesday, October 1, 2014

#1 2005-10-31 07:07:39 am

julifos
Administrator
From: MalasaƱa, Madrid
Registered: 2002-11-20
Posts: 2014

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):

Applescript:

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":

Applescript:

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):

Applescript:

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:

Applescript:

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.

Offline

 

Board footer

Powered by FluxBB

[ Generated in 0.033 seconds, 10 queries executed ]

RSS (new topics) RSS (active topics)