How Python Prevents Infinite Recursion (and hence Stack Overflow)

So I saw this fun little post on Reddit:

Look at the top rated answer:

Now that is some evil code. It will recurse forever, ultimately crashing the system (but not really, as I’ll explain below).

I wondered if I could build the Python equivalent of this.

Quite simple, isn’t it? The two functions call each other, which means the code will keep running forever, till it runs out of memory and your computer dies.

I wondered what would happen if I ran it? Would my computer freeze? Would I be forced to reboot my machine? Would it wipe my hard disk and kill my cat?


Nothing happened. Except this:

It seems Python has inbuilt protection against this sort of naughty programming. It internally keeps track of recursion depth, and stops if the number is exceeded. Note, you can increase this, but why would you?

Also note: This is how CPython, the most popular Python implementation handles it. Though I’m sure other implementations do similar things.

What happens if I try the same thing in C?

I ran the code above on Linux.

Segmentation fault means Linux killed the program because it was being naughty.

The difference is that Python catches the error for us and exits, while C dies horribly, and Linux is forced to step in and save the day.

Why this is useful to you?

You have to be careful when using recursion; it is possible to send your code into an infinite loop and kill the system.

I come from an embedded background, and we rarely or never use recursion. That’s because most embedded systems don’t have Memory Protection (or a very basic version of it). Memory protection is provided by the hardware, and your operating system uses these features to protect certain regions of the memory (like where the OS itself is loaded).

The segmentation fault you see above occurs because Linux gives each process a small region to play in. If you try to step out of it (like our program did), the OS intervenes and kills your program (why kill it? Because this is a techniques hackers use. They deliberately overwrite the stack to take over your system).

But if you are programming on a non-embedded system, you usually don’t have to worry about this, as the OS will protect you. All you need to do is make sure your code is stable and doesn’t try to go into an infinite recursion loop.