Clever Geek Handbook

C - Managing the Call Stack in Recursive Methods

I'm new to here and I have a problem bugging me. I'm a beginner, so please don't laugh at me. I want recursive quicksort to work on a large number of items, say 100000. I know this will result in a stack overflow. I've been searching searches for the past few days trying to find a way to manage the call stack. I can actually find a good source of information. My idea is to remove the return address of every recursive call except the last one, which will fall back to the first call to the function. I don't know if this is possible or if this is another solution for this problem.

PS: I want the quicksort relay to be recursive.

Sorry if my problems seem silly, but I can coax any suitable answer. Sorry for my bad english. Thank!

+3


source to share


4 answers


The standard way to solve the stack space expiration problem with a recursive algorithm is to implement it iteratively instead.



+3


source


Note that the 100,000 elements in the array are nothing; this will only result in deep nested calls of 17 functions:

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


To log(N)/log(2)

- log(2)

convert it to base base 2.

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

+3


source


If stack space is an issue, and in general memory is not, you can easily convert a recursive implementation to an iterative one using your own heap-allocated stack. That is, instead of making a recursive function call, push the arguments you want into your own stack data structure. Then you can iterate over your stack and process each set of arguments.

+1


source


it looks like you are trying to do the tail recursion we talked about here;

Tail recursion in C

0


source






More articles:


All Articles