Recursion #

Warmup #

└── foo
    ├── fred.txt
    └── bar
       ├── thud.txt
       └── waldo.txt

void printFiles(String folder){
    foreach child in children(folder){
        if(isFile(child)){
            print(child)
        } else {
            printFiles(child)
        }
    }
}

Recursive method #

Definition. A method is recursive if it calls itself, directly or indirectly.

For instance (in pseudocode):

    myMethod() {
        ...
        myMethod()
        ...
    }

    myMethod1() {
        ...
        myMethod2()
        ...
    }

    myMethod2() {
        ...
        myMethod1()
        ...
    }

Usage #

In theory, a recursive algorithm can be rewritten using loops only (and conversely).

However, in practice, some problems are easier to solve recursively. In particular, this is the case of many problem that involve tree-like structures (e.g. a folder, a JSON or XML document, an algebraic expression, etc.), and more generally graphs.

The following methodology can be used to solve a variety of problems:

Methodology. To solve a problem recursively:

• (Base case). If the input $I$ is minimal (e.g. of size 0 or size 1), then solve the problem directly.
• (Inductive case). Otherwise:
  1. Decompose $I$ into smaller inputs $I_1$, .., $I_k$.
  2. Solve the problem (recursively) for $I_1$, .., $I_k$.
  3. Combine the results (if needed).

In other words, in the inductive case, solve the problem for $I$ under the assumption that it can be solved for $I_1$, .., $I_k$.

Example: binary trees #

Definition. An ordered tree is a tree where the children of each node are totally ordered.

Definition. A binary tree is an ordered tree where each node has exactly two (possibly null) children.

Example. This is a binary tree:

int sum(Node root){
    // base case
    if (root == null){
        return 0
    }
    // inductive case
    return root.value + sum(root.leftChild) + sum(root.rightChild)
}

int height(Node root){
    //base case
    if (root == null){
        return 0
    }
    // inductive case
    return 1 + max(
                height(root.leftChild),
                height(root.rightChild)
    )
}

Processing order #

1
2
3
4
5
6
7
8

traverse(Node root){
    // inductive case only (do nothing in the base case)
    if (root != null){
        print(root.label)
        traverse(root.leftChild)
        traverse(root.rightChild)
    }
}

1
2
3
4
5
6
7
8

traverse(Node root){
    // inductive case only (do nothing in the base case)
    if (root != null){
        traverse(root.leftChild)
        print(root.label)
        traverse(root.rightChild)
    }
}

1
2
3
4
5
6
7
8

traverse(Node root){
    // inductive case only (do nothing in the base case)
    if (root != null){
        traverse(root.leftChild)
        traverse(root.rightChild)
        print(root.label)
    }
}

Definition. In the above exercises, the three node processing orders are respectively called pre-order traversal, in-order traversal and post-order traversal.

These three algorithms can be adapted to solve a variety of problems.

Hint. In-order traversal processes nodes in left-to-right order (when projected to a line).

Node leftMost(Node root, char label){
    // Base case.
    if(root == null){
        return null
    }

    // Inductive case.
    // Explore the left subtree first.
    Node candidate = leftMost(root.leftChild, label)
    // If the call succeeded, then we found the leftmost occurrence in the tree.
    if(candidate != null){
        return candidate
    }
    // Otherwise the next candidate (from left to right) is the current node.
    if (root.label == label) {
        return root
    }
    // If both attempts failed, then explore the right subtree.
    return leftMost(root.rightChild, label)
}

Syntax #

A recursive method often has the following structure (in pseudocode):

myMethod(Type input) {

    // base case
    if(<input is minimal>) {
        ...
    // inductive case
    } else {
      ...
      myMethod(smallerInput_1)
      ...
      myMethod(smallerInput_2)
      ...
      ...
      myMethod(smallerInput_k)
      ...
    }
}

Observation. Termination is guaranteed if the input of each recursive call is strictly smaller than the current input.

Auxiliary recursive method #

A recursive method is often an auxiliary method. For instance, some problems with an array as input can be solved recursively by dividing the array in sub-segments, as follows (in pseudocode):

solveProblem(Type[] array) {
    if(array.length != 0){
        // the initial segment is the whole array
        solveProblemRec(array, 0, array.length - 1)
    }
}

solveProblemRec(Type[] array, int startIndex, int endIndex)
    // base case (segment of length 1)
    if(startIndex == endIndex) {
        ...
    // inductive case
    } else {
        // middle index (rounded down)
        int middleIndex = (startIndex + endIndex) / 2
        ...
        // recursive call on the left subsegment
        solveProblemRec(array, startIndex, middleIndex)
        ...
        // recursive call on the right subsegment
        solveProblemRec(array, middleIndex + 1, endIndex)
        ...
    }
}

Multiple return values #

It is frequent for a recursive method to return multiple values. For instance, in a binary tree, return the least label (in alphabetical order) and the maximal depth at which it occurs.

In Java 14 or later, this can be easily achieved by returning a record. For instance:

record Result(Character leastLabel, int depth){};

Result leastLabelAndDepth(Node root) {

    // Base case.
    if (root == null) {
        return new Result(null, 0);
    }
    // Inductive case.
    // Recursive calls.
    Result leftResult = leastLabelAndDepth(root.leftChild);
    Result rightResult = leastLabelAndDepth(root.rightChild);

    // Initialize the return values with the values returned by the left recursive call.
    char leastLabel = leftResult.leastLabel;
    int depth = leftResult.depth;
    // If the least label in the right subtree is < to the least label in the left subtree
    if (rightResult.leastLabel < leastLabel) {
        leastLabel = rightResult.leastLabel;
        depth = rightResult.depth;
    // If the least labels in the right and left subtrees are identical
    } else if (rightResult.leastLabel == leastLabel) {
        depth = Math.max(depth, rightResult.depth);
    }
    // If the root's label is < to the least label seen so far
    if (root.label < leastLabel) {
        leastLabel = root.label;
        depth = 0;
    }
    return new Result(leastLabel, depth + 1);
}