C - Manage call stack in recursive methods - 【StackMirror】|c|recursion|stack-overflow|quicksort|callstack

I am new here and I have a problem that's bugging me.I am a beginner so please don't laugh at me. I want to make recursive quicksort work on a large number of elements,let's say 100000.I know this will cause the stack to overflow.I have been googling for the past few days trying to find a way to manage the call stack.I can't really find a good source of information. My ideea is to remove the return adress of each recursive call,except the last one,which will return to the first function call.I don't know if that is possible or if it is another solution for this problem.

P.S. : I want to keep the quicksort recursive.

Sorry if my problems looks silly,but i sould appreaciate any pertinent answer. Sorry for my bad English. Thank you!

2012-04-03 23:30
by user1311596

Post some code. If the recursion can be tail-called, you might be able to make it work - Kerrek SB 2012-04-03 23:40

Two things that will help; don't use a naive method when choosing a pivot, and always recur on the smaller partition first - Blastfurnace 2012-04-03 23:40

If you're choosing a decent pivot, you'll run out of memory long before recursion depth becomes a problem. Then the depth is logarithmic in the size of the array - Daniel Fischer 2012-04-03 23:42

The standard way to solve the issue of running out of stack space with recursive algorithm is to implement it iteratively instead.

2012-04-03 23:34
by stefanB

I understand that recursion is better to be avoided,but is it possible to work my way around this problem and still use the recursive method - user1311596 2012-04-03 23:37

if the data are causing the problem then you can pass them around, but if the number of method calls is the problem I don't see how you can easily get around that - stefanB 2012-04-03 23:40

So it is not possible to remove the return addresses of every recursive call,except the first recursive call,which i will store in a variable and the last recusive call,which return address i want to swap with the address of the first call.Sorry again for my silly question,but I am tired and frustrating of not finding a answer to this question.Thank you again - user1311596 2012-04-03 23:48

@user1311596 No you cannot.You do not get that kind control over the stack with C. Note however that some compilers will do tail call optimization, effectively doing what you want automatically (though the only way to know is to look at the generated assembly. - nos 2012-04-04 00:08

Please note that 100000 items in an array is nothing; this will only lead to nested calls 17 functions deep:

$ echo "l(100000)/l(2)" | bc -l
16.60964047443681173951

That's log(N)/log(2) -- the log(2) is to convert it to log base 2.

Any platform that supports recursive function calls will almost certainly be able to handle 17 nested calls.

2012-04-03 23:44
by sarnold

If stack space is a problem but memory in general isn't, you can easily convert a recursive implementation into an iterative one by using your own heap-allocated stack. That is, instead of making a recursive function call, push the arguments you care about onto your own stack data structure. You then can iterate over your stack and process each set of arguments.

2012-04-03 23:41
by jamesdlin

it sounds like you're trying to do tail recursion, which has been discussed here;

Tail recursion in C

2012-04-04 08:41
by sardok