Recursion

Recursion is a method calling itself with a smaller input. At first it looks like magic, but the logic behind it is simple: write the problem as one piece + a smaller version of the same problem, and solve the smallest version directly. A linked list is already a recursive structure (a node + the rest of the list), so list methods are very short when written recursively. Exam questions: what the code prints, how many calls are made, and writing a short recursive method. Next week we will compute the complexity of these methods.

Golden rules:

1. Don’t write recursion without a base case. Write it first.
2. Every call must approach the base. n − 1, n / 2, p.next.
3. Trust the result. Assume size(p.next) works correctly, and just add your own step.
4. The position of the print decides the order. Before the call or after?

The base case and the recursive step

static int factorial(int n) {
    if (n <= 1) return 1;          // base case: a direct answer
    return n * factorial(n - 1);   // recursive step: shrink and call
}

The same as the definition in mathematics: $n! = n \cdot (n-1)!$ and $1! = 1$. factorial(5) returns 120, factorial(0) returns 1.

The call stack

Every method call opens a stack frame holding its own parameters and local variables. When the call ends, the frame is popped and the return value is passed to the caller. The very same stack as in week 5.

The program output of the trace of factorial(4) (indentation = depth):

factorial(4) called
  factorial(3) called
    factorial(2) called
      factorial(1) called
      factorial(1) returns 1
    factorial(2) returns 2
  factorial(3) returns 6
factorial(4) returns 24

No multiplication is done on the way down; they all wait. When the base case is reached, the return begins and the multiplications are done from the inside out: 1, 2 · 1, 3 · 2, 4 · 6.

the call stack at the deepest moment (top is up):
| factorial(1) |
| factorial(2) |  waiting for 2 * ?
| factorial(3) |  waiting for 3 * ?
| factorial(4) |  waiting for 4 * ?
| main         |

Recursion that has no base case or doesn’t approach it fills this stack and you get a StackOverflowError. With default JVM settings this happens at a call depth of a few thousand to a few tens of thousands.

Where is the print?

static void down(int n) { if (n == 0) return; System.out.print(n + " "); down(n - 1); }
static void up(int n)   { if (n == 0) return; up(n - 1); System.out.print(n + " "); }

3 2 1 
1 2 3 

down prints while descending, up prints while returning. In an output question, the first thing to ask is: is the print before or after the recursive call?

More than one call: tree recursion

If a method calls itself twice, the calls form a tree and their number grows quickly.

static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

fib(5)=5 calls=15
fib(10)=55 calls=177
fib(20)=6765 calls=21891
fib(25)=75025 calls=242785

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   │   ├── fib(1)
│   │   │   └── fib(0)
│   │   └── fib(1)
│   └── fib(2)
│       ├── fib(1)
│       └── fib(0)
└── fib(3)
    ├── fib(2)
    │   ├── fib(1)
    │   └── fib(0)
    └── fib(1)

fib(3) is computed twice, and fib(2) three times. That is why naive Fibonacci is exponential; with a loop or by storing what has been computed (memoization) it becomes O(n).

If there is a print between the two calls, an interesting pattern appears:

static void g(int n) { if (n == 0) return; g(n - 1); System.out.print(n + " "); g(n - 1); }

1 2 1 3 1 2 1 

The speed difference: n − 1 or n / 2?

static long pow(long b, int n) {       // n+1 calls
    if (n == 0) return 1;
    return b * pow(b, n - 1);
}

static long fastPow(long b, int n) {   // ~log n calls
    if (n == 0) return 1;
    long half = fastPow(b, n / 2);
    return (n % 2 == 0) ? half * half : half * half * b;
}

1024 calls=11
1024 calls=5

$b^{10} = (b^5)^2$, $b^5 = (b^2)^2 \cdot b$. Halving the input means logarithmic depth. In week 11 we will show this with a formula.

Recursion on a linked list

List = empty (null) or a node + a list. This definition turns directly into code:

static int size(Node p)  { if (p == null) return 0; return 1 + size(p.next); }
static int sum(Node p)   { if (p == null) return 0; return p.data + sum(p.next); }

static boolean contains(Node p, int x) {
    if (p == null) return false;
    if (p.data == x) return true;
    return contains(p.next, x);
}

static void printReverse(Node p) {
    if (p == null) return;
    printReverse(p.next);           // the rest first
    System.out.print(p.data + " "); // then itself
}

For the list 4 → 7 → 1 → 9, size, sum, contains(1), contains(5) and printReverse:

4 21 true false
9 1 7 4 

printReverse prints a singly linked list backward without damaging it; to do this with a loop you would have to either reverse the list or use a stack. In recursion that stack is the call stack itself.

PITFALL · Making the base case p.next == null. if (p.next == null) return 1; gives a NullPointerException on an empty list (p is null). Write the base case for the smallest input, the empty list: p == null.

An introduction to backtracking

Some problems ask you to “try all possible choices”: all subsets, all permutations, placing queens on a chessboard. The backtracking template:

solve(state):
    if the state is complete: record / print, return
    for each option:
        apply the option
        solve(new state)
        UNDO the option

All subsets

static void subsets(int[] a, int i, List<Integer> cur) {
    if (i == a.length) { System.out.print(cur + " "); return; }
    cur.add(a[i]);                 // take
    subsets(a, i + 1, cur);
    cur.remove(cur.size() - 1);    // undo
    subsets(a, i + 1, cur);        // don't take
}

[1, 2, 3] [1, 2] [1, 3] [1] [2, 3] [2] [3] []

Permutations

static void perms(String prefix, String rest) {
    if (rest.isEmpty()) { System.out.print(prefix + " "); return; }
    for (int i = 0; i < rest.length(); i++)
        perms(prefix + rest.charAt(i), rest.substring(0, i) + rest.substring(i + 1));
}

ABC ACB BAC BCA CAB CBA

N-Queens

n queens on an n × n board, none threatening another. Put one queen in each row; if a column or diagonal conflicts, skip that column, and if no column works, go back to the previous row and move its queen. The solution counts the program counted:

4-queens: 2
5-queens: 10
6-queens: 4
7-queens: 40
8-queens: 92

Backtracking is better than brute force because it cuts a branch as soon as it sees a conflict; on 8 × 8 it tries very few of the $8^8 \approx 16$ million placements.

Common mistakes

static int factorial(int n) {
    if (n <= 1) return 1;
    return n * factorial(n - 1);
}

static void down(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    down(n - 1);
}
static void up(int n) {
    if (n == 0) return;
    up(n - 1);
    System.out.print(n + " ");
}

static int mystery(int n) {
    if (n == 0) return 0;
    return n % 10 + mystery(n / 10);
}

static long pow(long b, int n) {
    if (n == 0) return 1;
    return b * pow(b, n - 1);
}
static long fastPow(long b, int n) {
    if (n == 0) return 1;
    long half = fastPow(b, n / 2);
    return (n % 2 == 0) ? half * half : half * half * b;
}

static int fib(int n) {
    if (n <= 1) return n;
    return fib(n - 1) + fib(n - 2);
}

static void g(int n) {
    if (n == 0) return;
    g(n - 1);
    System.out.print(n + " ");
    g(n - 1);
}

static int size(Node p) {
    if (p == null) return 0;
    return 1 + size(p.next);
}

static void printReverse(Node p) {
    if (p == null) return;
    printReverse(p.next);
    System.out.print(p.data + " ");
}

static int bad(int n) {
    return n + bad(n - 1);
}

static boolean isPal(String s, int lo, int hi) {
    if (lo >= hi) return true;                       // 0 or 1 characters left
    if (s.charAt(lo) != s.charAt(hi)) return false;
    return isPal(s, lo + 1, hi - 1);
}

static void subsets(int[] a, int i, List<Integer> cur) {
    if (i == a.length) { System.out.print(cur + " "); return; }
    cur.add(a[i]);
    subsets(a, i + 1, cur);
    cur.remove(cur.size() - 1);
    subsets(a, i + 1, cur);
}

static void perms(String prefix, String rest) {
    if (rest.isEmpty()) { System.out.print(prefix + " "); return; }
    for (int i = 0; i < rest.length(); i++)
        perms(prefix + rest.charAt(i),
              rest.substring(0, i) + rest.substring(i + 1));
}