Re: recursion depth
Re: recursion depth
- Subject: Re: recursion depth
- From: deivy petrescu <email@hidden>
- Date: Mon, 17 Oct 2005 21:43:43 -0400
On Oct 11, 2005, at 17:59, has wrote:
Barry Wainwright wrote:
Here's a practical demonstration of recursion:
on commafy(theNum)
if theNum > 999 then return (commafy(theNum div 1000) & "," &
text -3 ¬
thru -1 of ("00" & ((theNum mod 1000) as text)))
return theNum as text
end commafy
Wouldn't be my choice as that's the sort of task that's as easily
done with iteration, and since novices will likely find an
iteration-based version easier to think about and understand they
won't see any point to using recursion in its place. Recursion's a
non-trivial concept for newbies to wrap their heads around, so you
have to sell it on its biggest advantages if you want them to
bother doing so.
The sorts of things that really demonstrate the value of recursion
are crawling tree structures (e.g. mapping filesystem hierarchies)
and divide-and-conquer algorithms (binary search, quicksort). Using
recursion here is much simpler and a lot more natural than using
iteration. For example (wishing AS had a decent 'print'-style
command instead of that lame 'log'):
on listFolders(theFolder, indent)
tell application "Finder" to set subFolders to every folder of
theFolder
repeat with subFolder in subFolders
log (indent & subFolder's name)
listFolders(subFolder, indent & tab)
end repeat
end listFolders
listFolders(choose folder, "")
This has the advantage of relating to a naturally recursive
structure that scripters are already very familiar with, so it's
easier for them to make sense of what it does and why. I always
hesitate to use the word 'intuitive', but I think crawling the
filesystem is as intuitive a demonstration of recursion as you can
get.
HTH
has
Agreed.
In AS the folder structure is a natural way to think about recursion.
However, here is another...
It can only be solved via recursion
A(x,y) = y+1 if x = 0
A(x,y) = A(x-1, 1) if y = 0
A(x,y) = A(x-1,A(x,y-1)) otherwise
I used the following script in Smile (v 3.0.6)
<script>
global n
set n to 0
on a(x, y)
global n
set n to n + 1
if x = 0 then return y + 1
if y = 0 then return a(x - 1, 1)
return a(x - 1, a(x, y - 1))
end a
<\script>
running a(3,9) I get 4093 (2^12 -3).
For n I get 11164370.
a(3,10) takes a while, and, with a(3,11) I get a stack overflow.
But, my last reading on a(3,11) is 193692955 ... Yep over 100000000
iterations.
This is all done in Smile.
SE breaks at a(3,6), and n = 42438
So much for limits...
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Applescript-users mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden