10.14: Stack Overflows

Last updated
Save as PDF

Page ID: 14675

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Each time a function is called, the Python interpreter remembers which line of code made the call. That way when the function returns Python knows where to resume the execution. Remembering this takes up a tiny bit of memory. This isn’t normally a big deal, but take a look at this code:

def funky():
    funky()

funky()

If you run this program, you’ll get a large amount of output which looks like this:

...
    File "C:\test67.py", line 2, in funky
        funky()
    File "C:\test67.py", line 2, in funky
        funky()
    File "C:\test67.py", line 2, in funky
        funky()
    File "C:\test67.py", line 2, in funky
        funky()
    File "C:\test67.py", line 2, in funky
        funky()
RuntimeError: maximum recursion depth exceeded

The funky() function does nothing but call itself. And then in that call, the function calls itself again. Then it calls itself again, and again, and again. Each time it calls itself, Python has to remember what line of code made that call so that when the function returns it can resume the execution there. But the funky() function never returns, it just keeps making calls to itself.

This is just like the infinite loop bug, where the program keeps going and never stops. To prevent itself from running out of memory, Python will cause an error after you are a 1000 calls deep and crash the program. This type of bug is called a stack overflow.

This code also causes a stack overflow, even though there are no recursive functions:

def spam():
    eggs()

def eggs():
    spam()

spam()

When you run this program, it causes an error that looks like this:

...
    File "C:\test67.py", line 2, in spam
        eggs()
    File "C:\test67.py", line 5, in eggs
        spam()
    File "C:\test67.py", line 2, in spam
        eggs()
    File "C:\test67.py", line 5, in eggs
        spam()
    File "C:\test67.py", line 2, in spam
        eggs()
RuntimeError: maximum recursion depth exceeded