Recursion question

[electroRF]

Hi Guys,

I'd like to ask something about recursion, using C.

I think it'd be best to describe the question by giving an example.

I wrote a recursive function that gets set of N numbers, and stores all subsets in an array (i.e. for "123", it stores, "", "1", "2", "3", "12", "23", 13", 123").

however, since I didn't want each function call to allocate memory for N-size array (because then I'd have in Stack N * 2^N memory occupation), I allocated a N * 2^N array before I started the recursion, and each function call updated that array.

Is there a way to have the recursive function calls allocate their on arrays without too much memory occupations?

thanks!

 

[Ian Rogers]

Just don't use local variables at all.... I never use Recursive functions if I can help it... If it's absolutely necessary then use a global array and an array of pointers!!!

I can't see that a function dynamically assigning arrays would work in these types of functions.
If the array was declared static... then you could work from the same array each recursion...

 

[misterT]

Is this an exercise from a book that you are trying to solve in general, or is this something that you are actually going to implement in a microcontroller? Like Ian said, recursions are not a good idea in microcontrollers. Some embedded compilers even have a very small limit for number of nested functions calls you can make.

Post the function you have come up with so far.

 

[electroRF]

Hi T and Ian,
Thank you.

This is something I was trying to solve in general, and thought to implement it on my PIC so it'd print all subsets on the GLCD.

Yes, I understand that recursion are indeed not a good idea because they take much Stack space of the on-board RAM (I know that thanks to T's great link on memory allocations).

Static Array can indeed be useful in recursions.

 

[misterT]

Choosing the right kind of data structure is very important when you need to get the best performance. The other very important thing is the algorithm. (Well, choosing the data structure and algorithm go usually hand-in-hand).
It does not matter how you implement the algorithm.. first get it working, then improve from that.
I like the way you are thinking about memory usage efficiency etc. I just did not get the full picture of the recursion problem.. still, without seeing the code, I like the way you approach problems.