Recursion on Recursive Data Types

Hello! Welcome back to our module on "Recursion and Structural Thinking."

In our last lesson, we explored the fundamental pattern of recursive list processing, comparing the original Lisp approach of car/cdr/cons with the modern pattern-matching style found in Haskell. We saw that despite the syntactic differences, the core idea of breaking a problem down into a base case and a recursive step remains the same.

Today, we will formalize and generalize this powerful pattern. The learning outcome for this lesson is to apply structural recursion to process recursive data types (e.g., lists, trees), recognizing it as the natural approach pioneered by the ML language family.

We will:

1. Define what a recursive data type is, using natural numbers and lists as primary examples.
2. Introduce structural recursion, where the structure of a function mirrors the recursive definition of the data it processes.
3. Apply this principle not just to lists, but to another fundamental recursive data type: trees.

Given your study of mathematical induction, you'll find the reasoning behind structural recursion very familiar. The base case of the recursion is analogous to the base case of an inductive proof, and the recursive step is analogous to the inductive step, where we assume the property holds for a smaller structure to prove it for the larger one.

1. Recursive Data and Structural Recursion

At the heart of functional programming is the idea of processing data by defining functions whose structure mirrors the structure of the data itself. This is only possible when the data types are defined recursively.

Let's start by formalizing this idea. The following reading from a Princeton course on functional programming (using OCaml, a dialect of ML) provides an excellent explanation. It begins by treating natural numbers as a recursive data type, which is a powerful way to connect this programming concept to its mathematical roots.

As you've just read, the principle of structural recursion is this: for a recursively defined data type, the function to process it should also be recursive and have a case for each part of the data definition.

• Base Case(s): For each non-recursive constructor of the data type (like 0 for natural numbers or [] for lists), the function provides a direct, non-recursive answer.
• Recursive Step(s): For each recursive constructor (like m+1 for numbers or hd::tail for lists), the function computes its result by calling itself on the smaller, structural component(s) (m or tail).

This approach guarantees that the recursion is well-founded—it will always terminate because the data structures get smaller with each recursive call until a base case is reached. While this idea was present in Lisp, the ML language family (which includes Standard ML and OCaml) was the first to make it a central, explicit design principle, supported by a powerful type system and pattern matching.

2. Structural Recursion on Lists

Let's revisit the list functions from our last lesson through the lens of structural recursion. The list data type is defined by two constructors: nil (the empty list) and cons (or :: in ML/Haskell), which takes an element and another list.

A structurally recursive function on a list must therefore have two cases:

1. A case for nil.
2. A case for h::t (a cons cell), where the recursive call is made on t.

The following resource shows classic examples of this pattern in Standard ML.

The sum function is a perfect example:

fun sum nil = 0
  | sum (h::t) = h + sum t;

• Data Definition: A list is nil OR h::t.
• Function Definition: sum of nil is 0 OR sum of h::t is h + sum t.

The structure of the code is a direct mapping of the data's definition.

This image provides a visual breakdown of how a recursive function might deconstruct a list, handling atoms and sublists differently, which is the essence of structural recursion.

Quick Check

Based on the sum example and the reading, how would you define a function product that computes the product of a list of integers? What is the correct value for the base case product nil?

fun product nil = 1
  | product (h::t) = h * product t;

3. Extending to Other Recursive Data Types: Trees

The true power of structural recursion is that it applies to any recursively defined data type. Let's move beyond the linear structure of lists to a branching structure: a binary tree.

We can define a binary tree in ML as follows:

datatype 'a tree = Leaf
                 | Node of 'a * 'a tree * 'a tree;

This definition says: "A tree of type 'a is either a Leaf (our base case), or it is a Node that contains a value of type 'a, a left subtree, and a right subtree (our recursive case)."

Following the principle of structural recursion, any function that processes this tree should have a structure that mirrors this definition:

1. A case for Leaf.
2. A case for Node(value, left, right), which will likely involve recursive calls on left and right.

Let's see this in action.

Let's write out the sum function for a tree of integers to make it explicit:

(* The data type definition *)
datatype int tree = Leaf
                  | Node of int * int tree * int tree;

(* The structurally recursive function *)
fun sumTree Leaf = 0
  | sumTree (Node(value, left, right)) = value + sumTree left + sumTree right;

• Base Case: The sum of an empty Leaf is 0.
• Recursive Step: The sum of a Node is its value, plus the sum of its left subtree, plus the sum of its right subtree.

The elegance of this approach is its safety and predictability. You handle every possible form the data can take, and the recursion is guaranteed to terminate. This pattern is fundamental to many areas of computer science that you're interested in, such as language design—compilers and interpreters constantly use structural recursion to process abstract syntax trees (ASTs), which represent the structure of the code they are compiling.

Conclusion

In this lesson, we've formalized the recursive patterns from our last session into the principle of structural recursion.

Key Takeaways:

• Recursive Data Types (like lists and trees) are defined in terms of themselves, using a set of base cases (e.g., nil, Leaf) and recursive cases (e.g., cons, Node).
• Structural Recursion is a powerful design pattern where a function's definition mirrors the recursive definition of the data it processes. This involves creating a case in the function for each constructor of the data type.
• The ML family of languages (including Standard ML and OCaml) pioneered this approach, making it a central feature supported by strong type systems and pattern matching.
• This pattern is general and can be applied to any recursive data structure, from simple lists to complex trees.

Next Lesson Preview:

So far, our recursive functions have been clear and elegant. However, as you may know from your prior experience, deep recursion can lead to a "stack overflow." In our next lesson, we will address this by exploring tail-call optimization. We will learn to identify tail-recursive functions and see how compilers for languages like Scheme and Haskell can execute them with the same efficiency as a simple loop.