The most fundamental use of stacks
relates to how functions are called. One function can call another function
which can call a third and so on to any depth until there is no more stack left
to support further calls.
When a call is made one method of passing
arguments to a function is to push the data onto the stack along with the
address of the program statement execution must return to when the function has
completed its work. This stack is referred to as the call stack
or sometimes the machine stack. A specific CPU register, the
stack pointer (SP), may be provided to manage it. In this case a call
function instruction says: push the return
onto the stack and jump to the function address, making that part of the pushing
Note that there are several differences between your average call stack and the stack implemented in Algorithms 10. In the majority of cases the call stack grows downwards in memory giving local variables a positive offset from SP. SP points to the last element put on the stack not the next free space so it is decremented down before data is pushed on. It is usual to discuss the depth of function calls meaning the number of calls made before a return starts the climb back up to calls higher in the calling hierarchy. An upside down stack fits well with this view:
When called the first action function
code takes is to push the old value of another CPU register, the frame
pointer (FP), onto the stack. The current value of SP is then stored in
FP allowing modification of SP to make space on the stack for any additional
local variables the function has.
On a return from a function the value of
SP is restored from FP and FP gets its old value back, popped off the stack.
Lastly, a return instruction in the machine code tells the CPU to send
execution back to the instruction address stored on the stack by the call and
currently referenced by SP. Thus FP and SP work together to walk up and down
The blocks of memory on the call stack
for each individual function call are stack frames. Function local variables that cannot be held
in registers because they are too big to fit or because those registers may be
used by the callee when that function calls another function are put on the
stack. Large return items can be passed back on the stack but more usually the
return or a reference to it is passed in a CPU register. Thus the availability
of this storage space makes nested function calls possible.
The ability to call a function from
within another function allows a strategy called recursion to be
used. In this scenario a function takes some action to reduce the complexity of
a problem and then calls itself until the problem becomes simple enough to
solve without further calls.
If a large list of items is
to be sorted for example, sorting the entire list is going to involve a lot comparisons and
moving items around. Sorting half the list will be easier so we can code a
function that passes half the list to another version of itself that in turn
halves the list and passes it on to a third version. Eventually a version will
get a list containing one or maybe no items. Such lists can be deemed already
sorted in both cases. Unfortunately this is not the full story and the final
episode will have to keep until we look at sorting in detail.
A simpler problem is to compute the
factorial value of a number. Factorial , represented as is the number of
different ways items can be arranged in a sequence of the items, just the
ticket for working out our chances of winning the next offering of Lotto.
One way of thinking of this is to say we
have choices for the first item to put into a sequence, choices for the
second and so on until we get a single choice for the last. If we start by creating sequences then each of the original sequences clones into sequences to accommodate the choices available at the next choosing. Each of these sequences then clones again to satisfy each of the choices remaining,
and so on.
To get the total of possible sequences, needs to be multiplied by the product of all the other choices for each
choosing down to the last. In other words
if n > 1:
return n * factorial(n - 1)
return 1 # for the last choice
This function returns the correct value
for 0! unity that is, and if by some horrible breach of the precondition for
factorials n is negative recursion never starts.
The if statement divides actions to be taken into two cases. The n >
1 case is the recursive case: the problem
requires further simplification. The else: case is the base case where further simplification is
no longer needed and it is time to work out a value and return it, not too hard
for factorial. A recursive function must include both cases and progress
towards the base case must be guaranteed.
Emulating the call stack
To see the call stack in action open the
file recursive.py from the download in PyCharm and change return
1 to return 1/0 in factorial() to get a divide by zero error. Run the file and output shows the error in line 7,
the base case, and the four previous calls for the recursive case in line 5. To
display line numbers at any time right click on the left grey border to the
edit pane and select the option from the context menu. This display shows how
the stack was used to record lines in the code where a call was made and
therefore the location after the call where execution must jump back to on a
return to process the returned value.
The values of n stored in each stack frame can be seen using PyCharm's debugger.
Delete the error generator and left click the grey left border at line 4 to
set a breakpoint on the if statement: a red circle
appears and the line is highlighted. Right click in the editor pane and select
Debug 'recursive' from the context menu. Single step through the program using
the F8 key or by clicking the two blue circles or blue down arrow icon on the top border of the
Debug pane. Note the decreasing values of n on the way down and the increasing values stored in each
stack frame on the way back up. When execution reaches the print() statement press F9 to finish.
Note that you
can stop any program running in PyCharm using Ctrl + F2 or by clicking the red
square in a Debug or Run pane's left border.
Another view of values on the call stack
can be got from running print_view.py. This version uses print statements to
log the value of n. Together the debugger
and print statements provide alternatives for revealing program behaviour. For
certain situations print statements provide a better solution and by viewing
console output while single stepping a program the two alternatives can be used
Recursion may provide a simplified view
of some problems but in essence all it does is to allow the call stack to be
used for storing and retrieving a sequence of values in LIFO order. It should
therefore be possible to use a stack to achieve the same result. Using the
stack ADT from Algorithms 10, factorial() can be written
from stack import stack as Stack
stk = Stack(n-1) # create a stack for n-1 elements
while n > 1:
n -= 1 # decrement n by 1
result = 1
while not stk.is_empty():
n = stk.pop()
result *= n # multiply result by n
When a recursive function does all its
work on the way down so that no additional computation is required after the
recursive call it is tail recursive: the recursive call being
last before the return - in the tail. In many cases a tail recursive function
can be modified to do all computation within a loop and recursion is not
The function factorial(n) above is not tail recursive: the return from the recursive call is
multiplied by n after it is received. To
make it so another parameter is needed to pass forward the result of computations done
def tr_factorial(n, result=1):
if n > 1:
return tr_factorial(n - 1, n * result)
Converting this version to a loop gets:
result = 1
while n > 1:
result = n * result
n = n - 1
Attempting full implementation within a
loop is not always a viable solution. The Quicksort algorithm supplies an
example. The list to be sorted is partitioned into two subdivisions: basically
elements less than or greater than a partition value. In a fully recursive
version there are two recursive calls one for each sub-partition. There are no
returns so these calls could be classed as tail recursive. However, because
there are two calls, while partitioning and sub-partitioning of left partitions
say can be done in a loop, right partitions are best passed to a recursive call
to avoid the complication of a local stack.
Use of a stack for subroutine linkage, local variables and arguments was first described by Alan Turing in his proposals for
the Automatic Computing Engine (ACE) (Turing 1946). Possibly independently -
this is the opinion of Donald Knuth (Knuth 1968), the stack concept was
further developed by Edsger Dijkstra. ALGOL 60 provided recursion. Early FORTRAN did not use a stack for
calling subroutines and recursion was not possible.
Recursion is a useful tool for problem
solving in many cases, far beyond the simple examples discussed here. It can be
viewed as a special case of decomposition: breaking a problem down into more
manageable parts. It is also a special case of iteration.
Consider a problem that could be solved
using nested loops but the depth of nesting is unknown when it is coded. What
the innermost loop or the base case does is plain to see but the number of
outer loops required to get there can vary from one instance of a structure to
another. Quicksort is one such problem: the depth of recursion depends not only
on the size of the list but also on its composition both of which can vary for
A similar problem, solved using
recursion, can be found in the _getstr() method in array_types.py from the download. This
method constructs a string representation of an array and the function must be
able to deal with any number of dimensions of any size. The loop in the else: recursive case calls _getstr() to generate the
required number of additional loops at the next level of nesting. For the 3 x 3
x 3 array from Algorithms 8, the innermost loop in the base case will add
element strings for one of the z direction vectors. The recursive case in the
previous call iterates over the vectors in the current row while the
call before that iterates rows. Rows, vectors, hyper-vectors, all are the same
to the recursive case.
Another use of a stack in program
execution is to deal with exceptions. When an exception occurs execution is
passed to code in the runtime environment to deal with it. This code manages a
walk back up the call stack executing any finally: blocks until a handler for the
exception is found. This process, which may involve stepping over some stack frames in entirety, is known as stack
unwinding. Wikipedia (2015) describes various occurrences. While executing the finally blocks or a handler another
exception may occur and so on for that exception. Progress with a previous
exception is held on a stack while the current exception is processed. Similarly a stack in the form of a linked list can be used to record the location of finally blocks and except exception handlers encountered as functions are called.
To deal with
lottery odds computations the functions nPm() and nCm() are provided in
recursive.py. Neither of these functions is recursive as such but nCm calls recursive factorial() and finds the odds of a 6 numbers win to be 1 in 13,983,816.
Knuth, D. (1968) The Art of computer programming, vol I, Fundamental algorithms, Section 2.6, Addison-Wesley
Turing, A. M. (1946) Proposals for the Development in the Mathematics Division of an Automatic Computing Engine (ACE), in Collected Works of A. M. Turing, MECHANICAL INTELLIGENCE, Ince, D. C. Open University, (edd. 1992), Elsevier Science Publishers
Wikipedia (2015) Call stack [Online], 24 April 2015. Available at https://en.wikipedia.org/wiki/Call_stack#Unwinding (Accessed 7 August 2015).
[Algorithms 13: Using Stack - recursion (c) Martin Humby 2015]