Infinite recursion and the stack

One of the issues with recursion is the possibility that it will go postal, which is probably why code containing recursive structures is often banned from things like aerospace applications. Infinite recursion is probably the worst-case-scenario – supposedly recursion that is limitless. However the opposite is true – recursion relies on the use of the stack, and stacks are not infinite. Every time a recursive function call occurs, a stack frame is created for that function. As this continues, the stack begins to fill up, eventually leading to a stack overflow. Here is a super simple piece of code that will do just that:

#include <stdio.h>

int main(void)
{
    main();
    return 0;
}

Nothing to it really, except that compiling and running this code will simply produce a “Segmentation fault” error, quite quickly in fact. Can we dig a little deeper? Sure, and it’s as simple as adding a variable, say an integer to the mix, and printing out its address. The code from above can be modified in the following manner:

#include <stdio.h>

int main(void)
{
    int x;
    printf("x lives at %p.\n", (void*)&x);
    main();
    return 0;
}

When compiled on a Raspberry Pi running Linux, this program prints out the memory address of the variable x – every time a recursive call to function main is activated. Don’t watch the screen, it will take a while to process – instead redirect the output to a file. Looking at the output file, the first x is stored at location 0xbe8266ec, giving a rough indicate of where the stack starts in memory. Calculating the word count of the file, returns 523,931 lines which literally means that the function main was called 523,931 times before the stack overflowed, and the program “seg-faulted”.

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s