Recursion: Avoiding Stack Overflow Errors

[petrushkagoogol]

Upto how many levels of recursion can be used in an algorithm to avoid stack overflow error ?

 

[ScottSalley]

There is no guarantees as it depends upon:
1. How much stack space is there to begin with?
2. How much space does each call take?

While you can measure these for a particular use case, in general you can't rely on this.

For any of the products I work on, I try to avoid using recursion and use an iterative algorithm. When I do use recursion, it is either for an internal tool that customers won't have to use or has some means of guaranteeing it won't require a deep stack.

 

[QuantumQuest]

Upto how many levels of recursion can be used in an algorithm to avoid stack overflow error ?

This question could not be more abstract. What kind of recursion, which programming environment / language and last but not least which operating system?

 

[Irene Kaminkowa]

It depends.
For example, tail recursion is as good as any iteration.

 

[Mark44]

It depends.
For example, tail recursion is as good as any iteration.

I don't think so. In recursion of any kind, the return address and any parameters have to be pushed onto the stack, something that is not done when a loop executes. Eventually the program will run out of available stack storage.

 

[Irene Kaminkowa]

It depends.
A compiler (interpreter) may treat tail-recursive calls as jumps not function calls. Then, the space is constant.

 

[Mark44]

It depends.
A compiler (interpreter) may treat tail-recursive calls as jumps not function calls. Then, the space is constant.

If the recursive function takes parameters, I don't see how a compiler could rewrite a function call as a jump. The compiler would still have to push the parameters onto the stack.

 

[D H]

It depends.
A compiler (interpreter) may treat tail-recursive calls as jumps not function calls. Then, the space is constant.

Exactly. Many compilers are very good at recognizing tail recursion. It's called "Tail call optimization". Some interpreters are also good at recognizing tail recursion (e.g., many dialects of Lisp), many others are not (python (Guido hates TCO), perl, ruby, ...).

 

[D H]

If the recursive function takes parameters, I don't see how a compiler could rewrite a function call as a jump. The compiler would still have to push the parameters onto the stack.

Tail recursion is a very special kind of recursion. The following C function to compute $n!$ is recursive but it is not tail recursive:

unsigned factorial (unsigned n) {
    if (n <= 1) {
        return 1;
    } else {
        return n * factorial(n-1);
    }

It appears to be tail recursive because the last function that is called is the function itself. However, the last operation is to multiply the value returned value by that call with n. One needs to write a helper function to make this tail recursive in C:

unsigned factorial_helper (unsigned n, unsigned prod) {
    if (n <= 1) {
        return prod;
    } else {
        return factorial_helper(n-1, n*prod);
    }
}

unsigned factorial (unsigned n) {
    return factorial_helper(n, 1);
}

Functional languages invite one to write tail recursive functions in lieu of loops. Non-functional languages such as C (and everything derived from C) invite one to write loops in lieu of tail recursive functions.

 

[Irene Kaminkowa]

The compiler would still have to push the parameters onto the stack

Consider GCD - it can be implemented as tail recursion.
Factorial - cannot.

There is an article "Tail call" in Wiki on this subject.

 

[D H]

Consider GCD - it can be implemented as tail recursion.
Factorial - cannot.

I just showed one for factorial. It can be implemented as tail recursion.

Ackermann's function cannot.

 

[Mark44]

Good point. My mindset is from learning C 30+ years ago, before there were such sophisticated optimization schemes.

 

[Irene Kaminkowa]

Perhaps, there is a toggle for each recursion.
Mathematicians have not proved the opposite so far.
So, there is hope. And a scope for work.

 

[newjerseyrunner]

Usually if you even come close to a stack overflow, you are using the wrong algorithm. What kind of algorithm are you doing?

Also, why is everyone talking about compiler optimization? The code has to work while he's debugging it too, without the compiler optimizations.