Re: recursion depth
Re: recursion depth
- Subject: Re: recursion depth
- From: has <email@hidden>
- Date: Mon, 10 Oct 2005 15:21:18 +0100
Nigel Garvey wrote:
> >FWIW, the only situation I can think of offhand where call stack overflows
> >are a significant problem for ASers are in recursive sort routines such as
> >quicksort.
>
>Recursive algorithms seldom need to go very deep -- as I believe you're saying.
Completely depends on the type of algorithm. Imperative programming idioms tend not to use recursion for much other than 'divide-and-conquer' algorithms (such as quicksort) and crawling tree structures (which in AS is usually stuff like filesystems), and in those cases recursion depth is generally not that deep (assuming good design). OTOH, functional programming can involve extremely deep call nesting since FP prefers recursion for many basic tasks such as traversing a list where imperative programming would have to use iteration. (FP languages are designed for that sort of thing, of course.)
Worst-case behaviour for quicksort is N recursions, where N is the length of the list being sorted. Picking good pivot values minimises the risk of this, however. FWIW, I should point out that the only times I've seen a quicksort blow the call stack in day-to-day AppleScripting it's been a naive implementation that takes the first item as pivot. There's all sorts of ways you can minimise or eliminate stack overflows in things like quicksort; even a simple improvement like using the middle item as pivot makes a big difference. Discussion here: <http://en.wikipedia.org/wiki/Quicksort>. Really though, this is all complex and boring stuff that only the wonks should deal with so that regular users never need to. [1]
Final thought: naive recursive sort algorithms aside, the most likely times AS users will get stack overflow errors is when dealing with the crustier parts of the language itself, e.g. the classic 'every text item of <some string containing more than ~4000 tokens>'.
has
[1] OT: This is one of the big reasons I've long been peeved at Apple for failing to provide AS with a proper library mechanism, because the ad-hoc copy-n-paste approach to code sharing used by much of the AS community encourages the spread of naive code (i.e. simple, but fragile, inefficient and error-prone) instead of the more robust and sophisticated (and correspondingly more 'scary-looking') routines that more skilled and knowledgeable developers produce. AS users, especially the novices, deserve 'best of breed' resources but unwittingly end up with 'lowest common denominator' instead; very frustrating.
--
http://freespace.virgin.net/hamish.sanderson/
_______________________________________________
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