After Hours

General discussion


Still using recursion?

By climons ·
Tags: Off Topic
article root

This conversation is currently closed to new comments.

Thread display: Collapse - | Expand +

All Comments

Collapse -

there...some pseudo-C :) ..

by climons In reply to Still using recursion?

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 ;
Slider( 0, Before, After );
// print result

Collapse -

Its late night and my C is really rusty but

by Slayer_ In reply to there...some pseudo-C :) ...

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:
But we can easily convert it to linear sequence with the same params set
I'm not sure what you mean, are you suggesting this as a solution to a stack overflow with recursion?

Collapse -

it's 11:20 in Toronto. quite late indeed

by climons In reply to Its late night and my C i ...

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.


Collapse -

Now that it is morning, I see it clear as day

by Slayer_ In reply to it's 11:20 in Toronto. q ...

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

Collapse -

Tail Recursion

by dogknees In reply to Still using recursion?

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.

Related Discussions

Related Forums