After Hours

Ask something
Discussion Locked

Still using recursion?

0 helpful
5 replies

by climons

Closed to new repliesThis discussion is closed. It stays readable, but it takes no new replies.
article root

5 replies

by climons

I haven't analyzed margin cases, I admit - maybe they're OK, but the idea is here

#define a_size XXX
int After = 0, Before = 0;
int array[a_size]; // consider it's filled
int equilsNo = 0;
int equils[a_size] ; // results

void Slider( int sliderIndex, int Before, int After )
{
if ( After == Before )
equils[equilsNo++] = sliderIndex;
if ( sliderIndex < a_size )
{
Before += array[sliderIndex];
After -= array[sliderIndex++];
Slider( sliderIndex, Before, After );
}
}

int main()
{
int i;
for ( i = 0; i < a_size; i++ ) // i less than a_size - chars are eaten
After = array[ i ] ;
Slider( 0, Before, After );
// print result
}

by slayer_

I'm not sure I understand where you are storing a result. And I don't see an exit. So I would expect it to continue looping past the middle point. But I am probably reading it wrong. But I understand the theory.

What lost me was this:
[i]But we can easily convert it to linear sequence with the same params set [/i]
I'm not sure what you mean, are you suggesting this as a solution to a stack overflow with recursion?

by climons

Here is the exit condition:
if ( sliderIndex LESS THAN a_size ) - compare char is just eaten away as control character
{
Before += array[sliderIndex];
After -= array[sliderIndex++];
Slider( sliderIndex, Before, After );
}
If the condition is wrong, we don't call ourselves anymore and return-return-return.....until main() is reached, Call stack is getting released on its way back.
Results are stored in equils[] array and can be printed

I like recursions, they're very elegant. But if the stack is limited ( I had once real world situation with firmware where stack space was really scarce ), then the only way is to write linear sequence. Think of the same Slider function again, only without calling itself. In this case we put it into the loop for array indexing. We also need to make sure parameters sliderIndex, Before and After are visible outside the function ( not a problem for recursion, because we can pass them as values, that's what I like ). We can do it either by passing parameters by reference ( just pointers in C ) or making them global variables. In the latter case they don't need to be parameters actually.

Cheers

by dogknees

If you can set the code up so the recursive call is the last operation in the function, you don't need to keep all calls on the stack, you can short-circuit the returns. I don't know if you can code this in C as you'll need to get at the stack and stack pointer.

by slayer_

I imagine if the indenting was visible, it would have been more obvious in my sleep deprived state.

This discussion is closed to new replies.