Personal Blogs

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 automatic.

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 stack. 

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.

Recursion

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 

def factorial(n):
    if n > 1:
        return n *  factorial(n - 1)
    else:
       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 together.

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 non-recursively:

from stack import stack as Stack

def stk_factorial(n):
    stk = Stack(n-1)    # create a stack for n-1 elements
    while n > 1:
        stk.push(n)
        n -= 1          # decrement n by 1

    result = 1
    while not stk.is_empty():
        n = stk.pop()
        result *= n     # multiply result by n
    return result

Tail recursion

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 required.

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 so far:

def tr_factorial(n, result=1):
    if n > 1:
        return tr_factorial(n - 1, n * result)
    else:
        return result

Converting this version to a loop gets:

def lp_factorial(n):
    result = 1
    while n > 1:
        result = n * result
        n = n - 1
    return result

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.

Summary

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 different lists.

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.

References

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]