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!
The standard way to solve the issue of running out of stack space with recursive algorithm is to implement it iteratively instead.
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
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.
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.
it sounds like you're trying to do tail recursion, which has been discussed here;