Abstract Data Types: Stacks and Recursion - CSCI 381 Goldberg

Administrative Updates

This material will not be on any exam.

Stacks

Overview: Recursion and Operating System Efficiency

Students in many different courses are taught recursion as an efficient means for programming and implementing different algorithms. However, what is often not mentioned is the efficiency costs for the operating system to support that mechanism. While recursion may not necessarily affect the complexity analysis of algorithms, from a practical perspective in terms of profiling time and memory resources, it does tax the system somewhat. It is important to be aware of this, as it could affect performance.

Recursion as Implemented by the Operating System

The fundamental structure that the operating system uses is that of a stack. Let us take a step back and analyze what is a stack and some variants.

We want to get very clear boundaries and understanding of what is a stack. The philosophical backdrop that a stack is a member of will take us back to ancient Greek philosophy, which differentiates form versus matter, and will lead us to the modern application to programming languages and more specifically to data structures in what is known as the abstract data type (ADT).

Philosophical Foundations: Form versus Matter

Initially, a little bit philosophical (Greek notion of form versus matter). This will lead to what is known as the abstract data type (ADT). Object-oriented technology in general facilitates this approach.

Consider the Aristotelian definition, which has four “causes” to describe an event or object. We are only going to need mainly two aspects but for completion’s sake we will mention all four aspects. These aspects are called causes in the philosophical literature: cause as a platform, a statement of purpose.

Cause	Description	Example	Also known as
material cause	out of which something is made	the wood of a chair	matter
efficient cause	the agent enabling the change	the carpenter
formal cause	the pattern or form that types are recognized by	artistic/architectural design of furniture	form
final cause	every object has a purpose, a goal in this world	dining

Form versus Matter for Data Structures

The distinction between form (functionality/operators/methods) and matter (implementation) is important for understanding abstract data types.

Stack Operators

• initiate (constructor): Allocate memory for the purposes of operating the stack
• isEmpty: Boolean predicate indicating whether or not there are data values in the stack
• Push: Place a data value on the TOP of the stack
• Pop: Remove a data value from the TOP of the stack. Pop requires a call to isEmpty before removal of any data item to ensure that a data value is present

Stack Implementation

• Array: Matrix representation
• Linked List: A list of objects, each pointing to the next one in the list

Since a stack is accessed only through the “TOP” of the stack, the stack is said to have LIFO or FILO protocol:

• LIFO = Last in, first out
• FILO = First in, last out

(as opposed to the queue data structure which is FIFO = First in, first out.)

Key Observations about Stack Operations

The key observation is that the ability to put onto (and remove from) the stack which you are interacting with, is only from the top. So the action of putting onto the top of the stack is called push and then, removing from the top of the stack is called pop.

(Obviously, one cannot remove an item from an empty stack, so either pop automatically calls the boolean predicate isEmpty or the user called this explicitly before invoking the pop operation. If isEmpty evaluate to TRUE, then a Null pointer will be returned indicating no data value/object available.)

Form and Matter Distinction in Practice

Now, how the stack behaves/operates should be independent of how the stack is implemented (such as with an array or a linked list perhaps). The distinction between form (functionality) and matter (implementation) is very relevant here.

There is a temptation to contradict the form such as in the following: although you know that you could easily perform a for loop to print all the elements of the stack array to obtain all of the stored stack data, but from the form perspective, the functional perspective of the stack, you should not be able to do that. What you technically would have to do is you would first need to remove a data element and then print it. Then remove the next element and print that data etc. (Remove here means “pop”.) Technically, an empty stack would result and you would need to then push all the elements back onto the stack to return the stack to its former state.

The danger with this temptation is that while facilitating the printing of the stack “array” may seem simple enough, once the form has been watered down, the programmer can easily use this laxity in situations where it would not be appropriate. In fact, this violation of abstract data type (form) is incorporated into a number of operating systems as will be mentioned later in the lecture today.

To be consistent with an ADT, the implementation should be shielded (encapsulated) or even hidden from the user. The programmer should not be able to use the underlying data structure implementation if it is not consistent with the “form” of the abstract data type. For completion’s sake, programming literature have a third aspect of abstract data types beyond the form and the matter. It is termed the “signature”. Here it simply means the data types and names of variables used in the implementation. That aspect will not be relevant for today’s discussion.

(Encapsulation is also known as information hiding. cf. see http://www.dba-oracle.com/t_object_encapsulation_abstract.htm)

Stack Variants

In the data structure literature, a number of variants are suggested, but they tend to go against the classic abstract data type we know as a stack. These authors tend to add more operators and methods that work and provide access to the data stored in the stack.

For example, the swap operator will allow the reversal of the first and second elements of the stack (from the top’s perspective.) Thus, the second element becomes the top and the former top is now the second data element on the stack.

Another variant operator is rotation. Here, the bottom of the stack moves to the top and all other data elements are subsequently pushed down one position in the stack or alternatively, the top of the stack is moved to the bottom of the stack and all other data elements are then effectively moved up a position amongst the stack data elements. Clearly, these would not be consistent with the class abstract stack data structure.

Another stack variant, but at least is no longer called a stack, is the deque. This version behaves simultaneously as a stack and a queue, i.e. the user can decide at each step whether to follow FILO stack protocol or FIFO queue protocol. Thus, at any step, one could interact with the top of the deque, treat it as a stack, and push or pop. Yet, immediately in the next step, the user could decide to treat the deque as a queue and insert from the beginning (top) but remove from the end of the queue (here a deque). As such, the deque is neither a stack nor a queue.

Finally, if one reads advanced hardware and advanced operating system books, we find different stacks involved in the execution by the cpu and other aspects of the processing system of a computer. Some of them are actually stacks, some of them are just data structures that collect data at large. So sometimes the word stack is used generically. But for the purposes of today’s lecture, we will be discussing and introducing what’s called the activation stack, which is involved in setting up areas of memory to support the recursive process and recursive programming when the programmer uses the recursive technique.

Recursion

Definition

The colloquial definition of recursion is: a function that (*) calls itself.

This is the standard definition, but it is sometimes worth considering a more humorous (yet insightful) alternative definition.

Recursion Joke Definition

“Recursion: see Recursion until you understand”

The phrase “until you understand” serves as the base case; otherwise, you have an infinite loop. Despite being a joke, this definition actually encapsulates the key ingredients of recursion: you have a loop, and you need to get out of the loop when you hit the base case. This is not a bad definition—it really encapsulates the key ingredients in a meaningful way.

The Heap

In computer science, there are four different applications to the term “heap”, none of which have anything to do with each other. For today’s lecture, we focus on the first definition:

• Heap: Pool of memory maintained by the Operating System memory manager to provide dynamic memory to processes during runtime execution
• Heap in heapsort: a (binary) tree whereby the value of the root is consistently greater (less than) all of its descendants
• Heap’s algorithm: for nonrecursive generation of permutations
• Heap’s law: in information retrieval, the frequency of identifying new words is less as the further one reads into a document

Memory Blocks in the Heap

In heap there are blocks of memory each assigned to a different running process. (Historically also called pages of memory.)

The heap is organized with separate memory blocks for different functions/methods. For example, a program with functions main(), f(), g(), and h() would have four separate blocks in the heap.

The Heap:

┌──────────────────────────┐  ┌──────────────────────────────┐
│        Block1            │  │         Block2               │
│        main()            │  │         f()                  │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

┌──────────────────────────┐  ┌──────────────────────────────┐
│        Block3            │  │         Block4               │
│        g()               │  │         h()                  │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

Each block contains:

• Parameter List: Parameters passed to the function/method. The parameter list is a declarative list that declares variables of given types that the programmer specified and must store the information somewhere in memory.
• Code*: The executable code (or pointer to code). Historically, the code for the method was stored entirely within the block as a self-contained unit. However, modern memory management typically saves memory by storing the code elsewhere and keeping only a pointer to the block. In C-based languages, the name of a function is itself a pointer to the function—it holds the address of where the code is located.
• Local Variables**: Variables local to the function/method. These are stored in the block during method execution. As soon as the method finishes executing, the local variables (assuming they are not static) are discarded along with the block.
• Workspace***: Temporary workspace for local calculations and scrap space. This area provides temporary memory for computations within the method.

* Whether the actual code or pointer to code

** If static, then the permanence gives it a global status (the variable persists beyond the method execution)

*** For local calculations; scrap space

Garbage Collection

What happens when the OS has no more allotted memory in the heap to allocate/assign to a method/function/procedure/process?

Garbage Collection: Any block assigned to a method that is no longer active can be reallocated to a different method.

cf. smart pointers in C++: the “pointer variable” itself keeps track of who is referencing it.

The Activation Stack

The Activation Stack is maintained by the OS memory manager and keeps track of which method is calling which method. Each time a method calls a method, a block of memory is reserved on the heap and placed on the stack. The top of the stack is the current active method.

The following diagram illustrates how the activation stack operates during nested function calls:

Activation Stack (Example: main → f() → g() → h())

Block4  h(x)  ┌─────────────────────┐
              │ ...............     │  and no more method calls
              ├─────────────────────┤
              │ ...............     │──→ Upon h's completion, the block is popped
              └─────────────────────┘    and output value returned to g(x)

Block3  g(x)  ┌─────────────────────┐
              │ ...y=h(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon g's completion, the block is popped
              └─────────────────────┘    and output value returned to f(x)

Block2  f(x)  ┌─────────────────────┐
              │ ...y=g(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon f's completion, the block is popped
              └─────────────────────┘    and output value returned to main(argc,argv)

Block1  main  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ To OS: main is an int (returns a
              └─────────────────────┘    semaphore/flag commenting on whether
                                         the program executed till completion
                                         without problems (-1))

User vs OS Perspective

To the user, main is a void (no return value); to the OS, main is an int (returns a semaphore/flag commenting on whether the program executed till completion without problems (-1)).

Indirect Recursion

Indirect recursion occurs when a function calls another function, which in turn calls the first function. The question “Isn’t a whole the sum of its parts?” highlights how complex call chains can build up on the activation stack.

The following diagram illustrates an indirect recursion scenario where f() and g() call each other:

Scenario#2: Indirect Recursion

Block4  f(x)  ┌─────────────────────┐
              │ ...............     │  and no more method calls
              ├─────────────────────┤
              │ ...............     │──→ Upon 2nd f's completion, the block is popped
              └─────────────────────┘    and output value returned to g(x)

Block3  g(x)  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon g's completion, the block is popped
              └─────────────────────┘    and output value returned to 1st f(x)

Block2  f(x)  ┌─────────────────────┐
              │ ...y=g(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon 1st f's completion, the block is popped
              └─────────────────────┘    and output value returned to main(argc,argv)

Block1  main  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ To OS: main is an int (returns a
              └─────────────────────┘    semaphore/flag commenting on whether
                                         the program executed till completion
                                         without problems (-1))

In this scenario, main() calls f(), which calls g(), which calls f() again. Each function call creates a new block on the activation stack, allowing the system to maintain the correct execution context for each invocation.

Heap Memory Layout for Indirect Recursion

The following diagram shows how the heap organizes memory blocks for the indirect recursion scenario:

The Heap:

┌──────────────────────────┐  ┌──────────────────────────────┐
│      Block1              │  │       Block2                 │
│      main()              │  │       f(), 1st instance      │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

┌──────────────────────────┐  ┌──────────────────────────────┐
│      Block3              │  │       Block4                 │
│      g()                 │  │       f(), 2nd instance      │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

* Whether the actual code or pointer to code

** If static, then the permanence gives it a global status

*** For local calculations; scrap space

Notice that f() appears twice in the heap (Block2 and Block4) as separate instances, with their own parameter lists, local variables, and workspace areas. This demonstrates how each function invocation gets its own memory block, even when the same function is called multiple times.

Direct Recursion

Direct recursion occurs when a method calls itself. This is the most straightforward form of recursion.

The following diagram illustrates a direct recursion scenario where f() calls itself repeatedly until a base case is triggered:

Scenario#3: Recursive Method Call

Block4  f(x)  ┌─────────────────────┐
              │ ...............     │  triggers a base case and no more method calls
              ├─────────────────────┤
              │ ...............     │──→ Upon 3rd f's completion, the block is popped
              └─────────────────────┘    and output value returned to 2nd f(x)

Block3  f(x)  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon 2nd f's completion, the block is popped
              └─────────────────────┘    and output value returned to 1st f(x)

Block2  f(x)  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ Upon 1st f's completion, the block is popped
              └─────────────────────┘    and output value returned to main(argc,argv)

Block1  main  ┌─────────────────────┐
              │ ...y=f(x);...       │
              ├─────────────────────┤
              │ ...............     │──→ To OS: main is an int (returns a
              └─────────────────────┘    semaphore/flag commenting on whether
                                         the program executed till completion
                                         without problems (-1))

In this scenario, main() calls f(), which calls itself, which calls itself again, until a base case is encountered. The activation stack accumulates multiple blocks for the same function, each with its own local variables and execution context.

Heap Memory Layout for Direct Recursion

The heap organization for direct recursion is similar to indirect recursion, but with multiple instances of the same function:

The Heap:

┌──────────────────────────┐  ┌──────────────────────────────┐
│      Block1              │  │       Block2                 │
│      main()              │  │       f(), 1st instance      │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

┌──────────────────────────┐  ┌──────────────────────────────┐
│      Block3              │  │       Block4                 │
│      f(), 2nd instance   │  │       f(), 3rd instance      │
├──────────────────────────┤  ├──────────────────────────────┤
│ Parameter List           │  │ Parameter List               │
├──────────────────────────┤  ├──────────────────────────────┤
│ Code*                    │  │ Code*                        │
├──────────────────────────┤  ├──────────────────────────────┤
│ Local Variables**        │  │ Local Variables**            │
├──────────────────────────┤  ├──────────────────────────────┤
│ Workspace***             │  │ Workspace***                 │
└──────────────────────────┘  └──────────────────────────────┘

* Whether the actual code or pointer to code

** If static, then the permanence gives it a global status

*** For local calculations; scrap space

All three instances of f() share the same code, but each has its own parameter list, local variables, and workspace. This is the essence of recursive programming—the same function code executed multiple times with different data and execution contexts, stacked on top of each other.

Summary: Method Calls and the Activation Stack

Three key points summarize the relationship between direct recursion, indirect recursion, and regular method calls:

• The OS does not treat any of these scenarios differently than any other. Whether it’s a regular method call, indirect recursion, or direct recursion, the activation stack mechanism works identically.
• All three scenarios are instances of “method calls”; the latter two (indirect and direct recursion) are specialized but still are method calls. The activation stack is a universal mechanism for managing all function/method invocations.
• The assumption that the top of the activation stack is the ONLY active method is technically true but unfortunately sometimes ignored by some systems.

Consider a method that uses a local variable that is not defined locally. What should be an error for using a variable not defined, but some systems instead ignore the stack policy and will actually descend the activation stack until it finds a locally declared variable of that name and will assume that that variable is the one referenced in the active top of the stack. That makes for really hard debugging.

Indirect Code

Factorial: Three Different Recursive Specifications

The factorial function can be defined in three different ways that all produce the same outputs. Each representation reveals different perspectives on recursion.

Mathematical Definition

0! = 1                          //base case
n! = n*(n-1)!                   // recursive step    //n is based on n-1; this is called top-down

Computer Theory Definition

Fact(0) = 1                     //base case
Fact(n+1) = (n+1)*Fact(n)       // recursive step    //n produces n+1; this is called bottom-up

Programming Implementation

int fact(int number) {
    if (number < 0) return -1;              //due to software engineering
    if (number == 0) return 1;              //base case
    return number*fact(number - 1);         // recursive step
                                            //n is based on n-1; this is called top-down
} // factorial

Observations

• Whereas Mathematical and Programming definitions are Top-Down, Computer Theory is Bottom-Up.
• Computer theory is definitional for all $n$ whereas the other two are trying to compute a single instance of the recursive function.
• Numerical computation (according to computer theory) of recursive functions must ALWAYS be bottom-up, as demonstrated by the activation stack (see previous section on direct recursion).

Factorial: Indirect Recursion Example

Indirect recursion can be demonstrated using factorial functions that call each other:

//fact call g
int fact(int number) {
    return g(number)
} // factorial

//g calls fact
int g(int number) {
    if (number < 0) return -1;              //due to software engineering
    if (number == 0) return 1;              //base case
    return number*fact(number - 1);         // recursive step
                                            //n is based on n-1; this is called top-down
} // g

So, fact calls g calls fact. This creates an indirect recursion pattern where the two functions call each other rather than calling themselves directly.