Recursive Tracing

Table of contents

1. Recursion
2. Language Generator
3. Recursive cases

Recursion

Throughout the course so far, we’ve seen that the choice of data abstraction affects how we solve programming problems. For example, we learned about certain templates for solving list problems, stack problems, queue problems: each of which required us to engage differently with how we organize code to manipulate data in a program.

For the remaining half of the course, we’ll study an equivalent paradigm shift in the context of functional abstraction. Earlier, we presented a narrow definition of functional abstraction focusing on the relationship between client and implementer.

The Balance class defines public methods so that other programs written by anyone, anywhere, at anytime before or after it can rely on its functionality as long as they know how to interface with it.

A more general definition for functional abstraction considers all algorithms as having three parts.

1. All algorithms take parameters as input.
2. All algorithms perform computation with the given parameters.
3. All algorithms return results based on the computations.

Recursive algorithms represent a style of solving problems by combining solutions to smaller subproblems.

1. Recursive algorithms take parameters as input.
2. Recursive algorithms perform computation with the given parameters.
   1. Identify smaller subproblems that can be solved independently.
   2. Solve each smaller subproblem with recursive calls.
   3. Combine the result of each subproblem to compute the complete result.
3. Recursive algorithms return results based on the computations.

Language Generator

It turns out that humans use recursion in everyday English. English grammar allow syntactic recursion with phrases embedded within phrases.¹ (In the following examples, brackets denote recursive structure.)

Conjunction

[[John and Mary] and Bill]

Clausal complements

[John thinks that [Mary said that [the girl cried]]]

Possessives

[[[[John]’s mother]’s brother]’s house]

[the house of [the brother of [the mother of [John]]]]

In syntactocentric linguistics, recursive syntax (embedding phrases within phrases) has been hypothesized to be the critical feature of human language capacity. Although this claim has been challenged in recent decades, generating understandable human language remains a key challenge for computer programming given the infinite expressiveness of human language. Can we define a program to generate all possible English sentences?

Language Generator

Recursive algorithms present one direct approach for answering this question. But before we try to tackle that question, we’ll study recursive algorithms for problems that we already know how to solve in order to build a foundation for answering these bigger questions in the future.

Recursive cases

Say we want to implement writeStars, a method that takes an integer n and prints out n asterisks * followed by a new line. We can solve this by defining an iterative algorithm.

// pre : n >= 0
// post: Prints a line containing the given number of stars
public static void writeStars(int n) {
    for (int i = 0; i < n; i++) {
        System.out.print("*");
    }
    System.out.println();
}

In order to solve the writeStars problem using recursion, we’ll temporarily disallow ourselves from using iteration. (This is not a general rule. Many recursive algorithms use recursion together with iteration to solve problems.)

One way to solve this problem without using any loops is to write out every possible case using if statements. But this gets tedious very quickly. How do we even cover all possible values of n?

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        System.out.println();
    } else if (n == 2) {
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } else if (n == 3) {
        System.out.print("*");
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } ...
}

This is where recursion can help. Notice the n == 3 case contains the same code from n == 2 but with an extra asterisk at the beginning. We can factor-out the repeated code and call the n == 2 case with writeStars(2).

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        System.out.println();
    } else if (n == 2) {
        System.out.print("*");
        System.out.print("*");
        System.out.println();
    } else if (n == 3) {
        System.out.print("*");
        writeStars(2);
    } ...
}

Notice the n == 2 case also contains the same code as the n == 1 case! And the n == 1 case also contains the same code as the n == 0 case!

public static void writeStars(int n) {
    if (n == 0) {
        System.out.println();
    } else if (n == 1) {
        System.out.print("*");
        writeStars(0);
    } else if (n == 2) {
        System.out.print("*");
        writeStars(1);
    } else if (n == 3) {
        System.out.print("*");
        writeStars(2);
    } ...
}

More generally, every case except for n == 0 can be rewritten with two statements.

public static void writeStars(int n) {
    if (n == 0) {
        // Base case
        System.out.println();
    } else {
        // Recursive case
        System.out.print("*");
        writeStars(n - 1);
    }
}

This recursive program has two parts: a base case and a recursive case.

Base case

A simple input that is computed directly.

Recursive case

A complex input that is computed with recursive calls to smaller subproblems.