Does an Infinite Recursion (as n approaches infinity) always result in a stack overflow?

Question

A theory question relating to recursion....

For any recursive problem, if your n gets really really really big, will it always segment fault at some value of n no matter what?

_In general_, each function calls adds to the stack. At a minimum the return address is pushed. Since stack space is finite, then yes, it will fault eventually. — 001, Nov 09 '15 at 15:22
The exception to the *in general* is tail call optimization: http://stackoverflow.com/questions/310974/what-is-tail-call-optimization. TLDR; some recursive functions can be _effectively_ turned into a while loop by the compiler. — Jonathan Dickinson, Nov 09 '15 at 15:41

score 0 · Answer 1 · answered Nov 09 '15 at 15:26

Yes, if it is a real recursion. For recursion the process needs ad least a return address on the stack. This takes stack spaces and thus eventually will lead to StackOverFlow.

If you expect such a large number of recursive calls, then you better aggregate the results.

A recursive sum would be:

Sum of all elements in a sequence = 
    first element + 
    sum of all elements in the sequence without the first one;

Instead of this, use a version without recursion

sum = 0;
elementsLeft = complete sequence   
while still elements left
{
    sum = sum + first element of elementsLeft
    elementsLeft = elementsLeft without the first element
}

What about tail recursion? Please read this Wikipedia article: https://en.wikipedia.org/wiki/Stack_overflow#Infinite_recursion — Tim Biegeleisen, Nov 09 '15 at 15:29

Does an Infinite Recursion (as n approaches infinity) always result in a stack overflow?

1 Answers1