Re: Recursive functions and stack overload
Re: Recursive functions and stack overload
- Subject: Re: Recursive functions and stack overload
- From: Andrew Farmer <email@hidden>
- Date: Wed, 26 Apr 2006 14:53:44 -0700
On 26 Apr 06, at 01:26, Paolo Bertani wrote:
Hi,
I'm sorting a plain C array with the "Quicksort" algorithm.
The quicksort() function calls itself recursively for a numer of
times that depends on the size of the array and the array's initial
configuration.
Since the array contains 10,000-100,000 elements the function calls
itself many times.
Is there the risk of some sort of stack overload?
Not really.
Quicksort has a maximum stack depth of lg(n), where n is the number
of elements in the array. Even with a 100,000 element array, the
maximum recursion depth is 16-17 calls. This probably won't be an
issue unless you allocate a lot of data on the stack (which you
shouldn't be doing in a quicksort).
Attachment:
PGP.sig
Description: This is a digitally signed message part
_______________________________________________
Do not post admin requests to the list. They will be ignored.
Cocoa-dev mailing list (email@hidden)
Help/Unsubscribe/Update your Subscription:
This email sent to email@hidden