Recursion

Recursion is a method calling itself with a smaller input to solve a problem. In the exam it comes in two forms: “What is printed?” (tracing the call stack to find the output order) and “write a recursive method” (without loops). The key to both is the same: seeing that each call works like a separate copy with its own variables.

Golden rules:

1. No recursion without a base case. In the smallest case, the method returns without calling itself.
2. Each call must get closer to the base case. Like n - 1, n / 10, substring(1).
3. Each call has its own variables. The n in one call does not affect the n in another.
4. Lines after the call run in reverse order. The last call made finishes first.

Base case and recursive step

The definition of factorial is already recursive: $n! = n \cdot (n-1)!$, and $0! = 1! = 1$.

static long factorial(int n) {
    if (n <= 1) return 1;            // base case
    return n * factorial(n - 1);     // recursive step
}
System.out.println(factorial(5) + " " + factorial(0) + " " + factorial(20));

120 1 2432902008176640000

We used long because factorial grows very fast; with int, 13! overflows. 20! is the largest factorial that fits in a long.

The call stack

Each method call adds a frame (stack frame) to the stack: the parameters, the local variables and the information “where do I continue when I return”. When the method returns, its frame is removed from the stack. In recursion, many frames of the same method sit on the stack at the same time.

If we add indentation to factorial and print every call and return:

factorial(4)
  factorial(3)
    factorial(2)
      factorial(1)
      return 1
    return 2
  return 6
return 24

stack (top = currently running)
                       ┌────────────┐
                       │ f(1) → 1   │   base case, returns
                  ┌────┴────────────┤
                  │ f(2) → 2 * 1    │
             ┌────┴─────────────────┤
             │ f(3) → 3 * 2         │
        ┌────┴──────────────────────┤
        │ f(4) → 4 * 6 = 24         │
        └───────────────────────────┘

Output order: before or after?

Most tracing questions rest on this one idea: lines written before the recursive call run on the way down, lines written after it run on the way back (in reverse order).

static void printBefore(int n) {
    if (n == 0) return;
    System.out.print(n + " ");      // print first
    printBefore(n - 1);
}
static void printAfter(int n) {
    if (n == 0) return;
    printAfter(n - 1);
    System.out.print(n + " ");      // print on the way back
}
static void both(int n) {
    if (n == 0) return;
    System.out.print("<" + n);
    both(n - 1);
    System.out.print(n + ">");
}
printBefore(3); System.out.println();
printAfter(3);  System.out.println();
both(3);        System.out.println();

3 2 1 
1 2 3 
<3<2<11>2>3>

For methods that make two calls, draw a tree. tree(n) first calls tree(n-1), then prints n, then calls tree(n-1) again:

tree(3)
├─ tree(2)
│  ├─ tree(1) → "1"
│  ├─ "2"
│  └─ tree(1) → "1"
├─ "3"
└─ tree(2) → "121"
result: 1213121

Classic examples

Fibonacci

$F(0) = 0$, $F(1) = 1$, $F(n) = F(n-1) + F(n-2)$.

static int fib(int n) {
    if (n < 2) return n;
    return fib(n - 1) + fib(n - 2);
}
for (int i = 0; i <= 10; i++) System.out.print(fib(i) + " ");

0 1 1 2 3 5 8 13 21 34 55 

Short and readable, but very slow: it computes the same values again and again. We measured the total number of calls with a counter:

The number of calls grows roughly as $O(2^n)$. A loop does the same job in $O(n)$ steps. The answer to the exam question “why is it slow”: repeated subproblems.

Powers

static double power(double base, int exp) {
    if (exp == 0) return 1;
    if (exp < 0) return 1 / power(base, -exp);
    return base * power(base, exp - 1);          // exp calls
}
static long fastPower(long b, int e) {
    if (e == 0) return 1;
    long half = fastPower(b, e / 2);             // halve the problem
    return (e % 2 == 0) ? half * half : half * half * b;
}
System.out.println(power(2, 10) + " " + power(3, 0) + " " + power(2, -2));
System.out.println(fastPower(2, 30) + " calls=" + pcalls);

1024.0 1.0 0.25
1073741824 calls=6

The plain version would make 31 calls for $2^{30}$; the version that halves finished in 6 calls (30, 15, 7, 3, 1, 0). This $O(\log n)$ idea is also in binary search.

Palindrome

static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));
}
System.out.println(isPalindrome("racecar") + " " + isPalindrome("abca") + " "
                   + isPalindrome("") + " " + isPalindrome("noon"));

true false true true

Binary search

Compare the searched value with the middle element of a sorted array; if it is smaller, repeat the same thing in the left half, if larger, in the right half. Each call halves the search range. (In week 13 we will compare it with the loop version.)

static int binarySearch(int[] a, int key, int low, int high) {
    if (low > high) return -1;                       // range is empty: not found
    int mid = (low + high) / 2;
    System.out.println("  low=" + low + " high=" + high + " mid=" + mid + " a[mid]=" + a[mid]);
    if (a[mid] == key) return mid;
    if (key < a[mid]) return binarySearch(a, key, low, mid - 1);
    return binarySearch(a, key, mid + 1, high);
}
int[] a = {3, 8, 15, 21, 30, 42, 57, 66, 80};
System.out.println("found at " + binarySearch(a, 57, 0, a.length - 1));
System.out.println("found at " + binarySearch(a, 10, 0, a.length - 1));

  low=0 high=8 mid=4 a[mid]=30
  low=5 high=8 mid=6 a[mid]=57
found at 6
  low=0 high=8 mid=4 a[mid]=30
  low=0 high=3 mid=1 a[mid]=8
  low=2 high=3 mid=2 a[mid]=15
found at -1

The trace lines are printed before the “found at” line: the concatenation in println’s argument can only be done when binarySearch has completely finished.

Other patterns

static int sumDigits(int n) {               // 9045 → 9+0+4+5
    if (n < 10) return n;
    return n % 10 + sumDigits(n / 10);
}
static int sumArray(int[] a, int i) {       // array + index parameter
    if (i == a.length) return 0;
    return a[i] + sumArray(a, i + 1);
}
static int countX(String s) {               // shrink the String letter by letter
    if (s.isEmpty()) return 0;
    return (s.charAt(0) == 'x' ? 1 : 0) + countX(s.substring(1));
}
System.out.println(sumDigits(9045));
System.out.println(sumArray(new int[]{4, 7, 1, 8}, 0));
System.out.println(countX("xaxbxx"));

18
20
4

Recursion or loop?

PITFALL · skipping the base case. If the method m2(n) returns n + m2(n - 2) and the base case is n == 0, odd numbers never see 0 (7, 5, 3, 1, −1, …) and the stack overflows. That is why writing n <= 0 is safer. When you write a base case, ask “does every input reach this?”

A method without a base case (return n + bad(n - 1);) compiles but throws StackOverflowError when it runs; that is exactly what happened in the test run. A method where not every path returns does not compile at all: missing return statement.

Common mistakes

static void printBefore(int n) {
    if (n == 0) return;
    System.out.print(n + " ");
    printBefore(n - 1);
}
static void printAfter(int n) {
    if (n == 0) return;
    printAfter(n - 1);
    System.out.print(n + " ");
}
// in main:
printBefore(3); System.out.println();
printAfter(3);

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

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

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

static int mystery(int a, int b) {
    if (b == 0) return a;
    return mystery(b, a % b);
}
// in main:
System.out.println(mystery(48, 18) + " " + mystery(17, 5));

static String reverse(String s) {
    if (s.isEmpty()) return s;
    return reverse(s.substring(1)) + s.charAt(0);
}
// in main:
System.out.println(reverse("stack"));

static int m2(int n) {
    if (n <= 0) return 0;
    return n + m2(n - 2);
}
// in main:
System.out.println(m2(7) + " " + m2(6));

static int sum(int n) {
    if (n == 0) return 0;
    else if (n > 0) return n + sum(n - 1);
}

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

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

public static boolean isPalindrome(String s) {
    if (s.length() <= 1) return true;                       // base case
    if (s.charAt(0) != s.charAt(s.length() - 1)) return false;
    return isPalindrome(s.substring(1, s.length() - 1));    // the middle
}