What Is Stack Overflow?

By Amber D. Walker

A stack overflow is a type of programming error which occurs when a program attempts to allocate more memory on the call stack than is available. It is a potentially serious error that causes the offending program to crash and is usually the result of one of two design mistakes.

The Stack

The stack refers to a section of memory which is used to store information about the functions of a program. The sizes and technical details of the stack will be vary depending on programming language, compiler, operating system and processor type, and these details are generally hidden from the programmer in most higher-level languages.

Example Stack

Consider the following example in pseudocode:function a { 1. call function b. 2. call function c.}function b { 1. call function c. 2. Print Spot.}function c { 1. Print Run.}Since each function can call other functions, the stack exists to keep track of where in the parent function to continue after a child function returns. This example, if stopped inside function c, may have a stack that looks something like this:>A1---> B1--------> C1Since the first line of function A calls function B, and the first line of function B calls function C. After function C will finish, the program will continue back up the chain, running B2 and finally A2.

Infinite Recursion

A stack overflow occurs when a program attempts to store too much information on the stack. The most common cause of a stack overflow is a design error called infinite recursion. Consider the following example in pseudocode:function A { 1. call function A. }And the resulting stack:->A1---> A1--------> A1-------------->A1(and so on)Those familiar with computer programming will recognize this as a variation on the infinite loop, except, rather than run forever, this program will eventually consume all the memory on the stack, resulting in a crash and a stack overflow error.

Prevention

Stack overflow errors generally occur when attempting to implement recursive algorithms, and the key to avoiding most errors is to ensure that the following is true of all recursive implementations: the recursive function must contain an exit condition that does not create another layer of recursion; and the recursive function must be designed so that each layer of recursion added must bring the function closer to the exit condition.

Large Local Variables

Another, much rarer cause of stack overflow errors is the declaration of large local variables, usually in the form of arrays containing hundreds of thousands, or millions, of elements. The simplest way to avoid stack overflows in this situation is to use pointers and dynamic memory allocation to avoid declaring the data on the stack when such memory intensive operations are called for.

References & Resources