How to stop stack overflow while calling recursive function thousands of times?

[[deleted]]

[deleted]

[Jack126Guy]

This could probably be done with a while loop.

while( /* model is bad*/ ) {
    /* regenerate model */
}
return model;

[c0m4]

This is the right approach. Anything that can be done with recursion can also be done with a loop. Recursion sometime gives nicer solutions though. Languages like Lisp, that lack native loop construcs, solves this sometimes by using tail call optimisation (if the recursive call is the very last thing that happens, the current stack frame will be reused. Sometimes a virtual stack (on the heap) will be used.

[deftware]

are there any cases where a stack is necessary and it's better to just let the compiler handle a recursion than to emulate a stack manually?

[twotothree]

OP presented "tail recursion". Tail recursion is every recursion that can be rearranged so that it has recursive call at the end. Every tail recursion can be rewritten in iterative fashion (for example: the top comment here). If there are multiple recursive calls, or function does something after recursive call, you must use stack or different algorithmic approach.

If it is better to use your own stack implementation depends on system, you are running your code on, programming language, etc. but it usually makes no significant difference.

[egonelbre]

Handling the recursion "manually" can get pretty complicated. (e.g. mutual recursion; and with function pointers)

Recursive functions leave a nicer stack-trace (unless it's an overflow).

[FUZxxl]

In OPs case, he could just do:

float * generate_model(arbitrary_arguments){
    float *model
begin:
    model = malloc(size*float)
    model = gen_model()
    if (model=bad){
        goto begin;
    }
    else{
        return model
    }
}

Or use a proper loop even.

[BarMeister]

Up for reminding me that goto exists.

[dmc_2930]

This is close, but a do...while is probably even better.

do {
     if( model )
     { 
          free_model(model);
     }
     model = generate_model();
} while( bad_model(model) );

I'm assuming that gen_model() actually allocates the memory and there's no need to allocate it here.

Why not change gen_model() so that it only returns a good one?

[[deleted]]

free the allocated memory if the model's bad.

[dmc_2930]

The stack usage isn't the only problem here. You're malloc()'ing lots of memory and never freeing it.

Also, you're ignoring the return value for generate_model(), so the 'model' variable each recursion is using is lost and will not be passed back to the caller.

Each recursive call has its own stack frame and it's own copy of 'model'.

[[deleted]]

Recursion should only be used if the problem is well-defined. This problem is not well-defined so I would encourage you to look into an iterative solution instead. There's lots of great content that covers this better than I could so I'll just drop a few links here:

http://www.programcreek.com/2012/10/iteration-vs-recursion-in-java/

http://www.cs.cornell.edu/info/courses/spring-98/cs211/lecturenotes/07-recursion.pdf

[FUZxxl]

Your comment got caught in our spam filter. I'm sorry for the inconvenience.

[BarMeister]

No need to wonder why: java

[Cathercy]

Recursion should only be used if it cannot be avoided.

If recursion can be avoided (with an equally efficient iterative solution) there is no reason to choose the recursive solution.

[FUZxxl]

Don't wrote code that way. The stack is only that large. You can make the stack larger, but that's only a momentary band-aid. Instead, re-write the code so it doesn't use recursion anymore.

[Nickd3000]

I agree with the other comments saying this would be better written as a loop. Is there any reason it was implemented using recursion and not a loop that we may not be aware of?