recursion depth
recursion depth
- Subject: recursion depth
- From: Matt Neuburg <email@hidden>
- Date: Sun, 09 Oct 2005 09:52:57 -0700
- Thread-topic: recursion depth
Okay, let's all test the depth of recursion, please.
on remvix(L, ix)
if L is {} then return {}
if ix is 1 then
return rest of L
else
return item 1 of L & remvix(rest of L, ix - 1)
end if
end remvix
set L to {}
set max to 504
repeat with x from 1 to max
set end of L to x
end repeat
remvix(L, max)
OMM, that works, but if "max" is set to 505, we get a stack overflow.
However, other users report other numbers. So now I'd like to collect some
more data. Please report what your maximum "max" is (and anything else you
think might be affecting this - your ram size, for instance?).
To make this easier, the following *might* be a correct testing algorithm,
though I'm not entirely certain:
on remvix(L, ix)
if L is {} then return {}
if ix is 1 then
return rest of L
else
return item 1 of L & remvix(rest of L, ix - 1)
end if
end remvix
on test(max)
set L to {}
repeat with x from 1 to max
set end of L to x
end repeat
try
remvix(L, max)
return true
on error
return false
end try
end test
-- find an upper bound
set x to 2
repeat while test(x)
set x to x * 2
end repeat
-- do the search
on binarySearch(lt, rt)
local mid, ok1, ok2
repeat while (lt ¾ rt)
set mid to round (lt + rt) / 2 rounding down
set ok1 to test(mid)
if not ok1 then
set ok2 to false
else
set ok2 to test(mid + 1)
end if
if ok1 and not ok2 then return mid
if not ok1 then
set rt to mid - 1
else
set lt to mid + 1
end if
end repeat
end binarySearch
return binarySearch(2, x)
On my machine, that yields 502, which makes sense because it's 504 minus the
two addition stack levels used by the nesting in the script. m.
--
matt neuburg, phd = email@hidden, <http://www.tidbits.com/matt/>
A fool + a tool + an autorelease pool = cool!
AppleScript: the Definitive Guide
<http://www.amazon.com/exec/obidos/ASIN/0596005571/somethingsbymatt>
_______________________________________________
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