Eli5-What does a “stack overflow” mean?
In: 847
The simplest computer programs are just a series of instructions executed one after the other. Start with the first one, and keep going until you reach the last one, at which point the program ends. But that doesn’t usually lead to very interesting programs.
Now, you can write loops to do more interesting things (generally, things that tend to repeat a lot) but even with that, you’ll eventually reach a wall where you can’t do anything more interesting or complex.
One way to do more interesting or complex things is to create subroutines (sometimes also known as functions.) Basically, you write a smaller program which takes some parameters as input, and does things. If it also returns a value back, it’s a function. But now, you have a tool that you can “call” on at any other point in your program. Control goes from your main program to the subroutine until that subroutine ends, at which point the program flow automatically returns to the point where the subroutine was called.
In order to pass those parameters to your subroutine, and remember where to come back to once the subroutine ends, your computer uses a stack: it puts the parameters and the return address in a special place in memory, and then starts executing the subroutine’s code. The subroutine accesses those parameters, and once it ends, the code jumps back to the return address.
So, if all you did was call subroutines from your main code, and then return back to the main code, you wouldn’t need a stack, you would just need one spot in memory at a time. But you see, one subroutine can call another subroutine. Which can call another subroutine. And so on. So every time one of those subroutines ends, your computer needs to go back to where it was called, but then if that was in another subroutine, it needs to remember its return address, too. So you need a way to remember all those return addresses!
So that’s why we use a stack. It’s called a stack because it kind of works like those stacks of plates you might have seen at buffet restaurants, where every plate you put on the stack pushes the stack down, and every time you take out a plate, the stack comes back up. All you can do is put a plate on top of the stack (hiding the plate under it) or pop the top plate off (revealing the next plate under it.)
So, now that you understand what’s a stack, and how it’s used, here’s where a problem can happen. If one subroutine can call another one, and then that one can call another one, and so on, that stack can actually pile up pretty high! going back to that stack of plates at the buffet, there’s only so many plates that can fit, and you can reach a point where no more plates will fit. If you try to put another plate on top, the stack won’t go down anymore. It will OVERFLOW!
Now, if all you have is subroutine A calling subroutine B, which calls subroutine C, and so on, you’re unlikely to overflow, because you’re writing each new subroutine. You know how many plates you’re putting on the stack. The problem comes when you get something like subroutine C calling subroutine A. Put another way, if you have A > B > C > A, well, you already know that A calls B, which calls C, so now your stack is A>B>C>A>B>C>A and if there’s nothing to break that chain, these calls will keep going, putting a new plate on top of the stack at every call, until no more plates fit. Stack Overflow!
Now, there’s legitimate reasons to have call sequences like that. You might even have sequences like A>A>A>A… and as long as you have a condition in there somehwere that will stop A from calling itself, you’re probably safe. But if you made a mistake and there’s a way for A to keep calling itself, your stack will eventually overflow!
By the way, subroutines and functions that call themselves (either directly as A>A>A>A>… or indirectly like A>B>C>A>B>C>A>…) are called “recursive”, and stack overflows are common when people make mistakes with such subroutines and functions.
Latest Answers