Can infinite recursion be implemented?

Question

I understand that for C at least the stack frame and return address are written to the stack every time the recursive function is called, but is there an obscure way of making it not run out of memory? Obviously this is purely a hypothetical question as I can't imagine a use case for it.

Answer 1

You can emulate recursion using a stack

The part of memory related to function calls and static variables (declared with int x; in C) is separate from the part of memory related to dynamic allocation (using malloc() in C). Only the former, called "the stack" is limited and will lead to a "Stack Overflow" error. Well, of course that's not entirely true. The latter is called "the heap" and of course your computer is not magic and will run out of memory at some point if you really try to push its limits.

• Recursive function to loop and stack
• How can you emulate recursion with loop and stack?
• How ti rewrite a recursive method by using a stack?
• Way to go from recursion to iteration

You can use tail-recursion to avoid adding layers to the call stack

Stack overflow is due to the size of the call stack. Imagine a function like this:

int f(int n)
{
    int x;
    if (n < 2)
    {
        return 1;
    }
    else
    {
        x = f(n-1);
        return n * x;
    }
}

When making the recursive call to f, the computer needs to keep some note of the fact that we'll need to do one more multiplication once the recursive call is completed. Taking note of this is achieved by adding a layer to a "call stack" with some information on the values of variables, and where in the code we are. This requires memory and will lead to stack overflow in case the stack becomes too big.

Now compare with the following code:

int f(int n, int acc)
{
    if (n < 2)
    {
        return acc;
    }
    else
    {
        return f(n-1, n * acc);
    }
}

This time the recursive call is directly encapsulated in the return, meaning there is no more work to do after the recursive call. Imagine you asked me to do a job and report the result to you; by making the recursive call I'm delegating some work to my friend; then instead of staying around waiting for my friend to report back to me so that I can report back to you, I leave immediately and tell my friend to report directly to you. This saves memory by "cutting the middle man".

Read more:

• Wikipedia: Tail call
• Wikipedia: Tail-recursive functions

In languages that feature lazy evaluation, you can write a seemingly infinitely-recursive function, then only evaluate it as far as required:

• Haskell infinite recursion