user1311596
user1311596

Reputation: 51

C - Manage call stack in recursive methods

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!

Upvotes: 3

Views: 329

Answers (4)

sardok
sardok

Reputation: 1116

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

Tail recursion in C

Upvotes: 0

sarnold
sarnold

Reputation: 104080

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.

Upvotes: 3

jamesdlin
jamesdlin

Reputation: 90125

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.

Upvotes: 1

stefanB
stefanB

Reputation: 79850

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

Upvotes: 3

Related Questions