Recursion

Recursion can be a bit of mind bender.

But only because it gets a lot of power out of very simple pieces that you already understand.

Method calls

We’re used to calling methods to solve sub-problems

public int hypotenuse(int a, int b) {
  // Call Math.pow to do exponentation
  int a_2 = Math.pow(a, 2);
  int b_2 = Math.pow(b, 2);

  // Call Math.sqrt to do compute square root
  return Math.sqrt(a_2 + b_2);
}

Human computation

Each human handles one method call.

As a human method call your job is to know how to execute your code for a given argument and return a value to the human who asked you.

If your code requires you to call a method you need to find an appropriate human method and ask them for the answer you need.

Human computation: hypotenuse(3, 4)

Cast: hypotenuse, Math.pow, and Math.sqrt.

public int hypotenuse(int a, int b) {
  // Call Math.pow to do exponentation
  int a_2 = Math.pow(a, 2);
  int b_2 = Math.pow(b, 2);

  // Call Math.sqrt to do compute square root
  int sum = a_2 + b_2;
  return Math.sqrt(sum);
}

Factorial

n! = n × n - 1 × n - 2 … × 1

Or in math class:

factorial(0) = 1
factorial(n) = n × factorial(n - 1)

Factorial method

We can easily translate the mathematical definition into Java code:

public int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

Human computation: factorial(4)

Cast: Five factorials

public int factorial(int n) {
  if (n == 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

This can also be written with a loop

public int factorial(int n) {
  int f = 1;
  for (int i = 1; i <= n; i++) {
    f *= i;
  }
  return f;
}

In general loops can easily be translated into recursion but not the other way around.

Now let's do Fibonacci

Mathematical definition:

fibonacci(0) = 0
fibonacci(1) = 1
fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2)

In Java:

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

Human computation: fibonacci(4)

Cast: Four fibonaccis.

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

Can Fibonacci be turned into a loop?

Yes, but it’s not quite as obvious how because of the tree structure.

public int fib(int n) {
  int a = 0;
  int b = 1;
  for (int i = 0; i < n; i++) {
    int tmp = a;
    a = b;
    b += tmp;
  }
  return a;
}

Recurive data structures

Let’s define a class that can represent a file on our hard drive.

There are two kinds of files.

Single files are things like a document or a video that have a direct size.

Folders contain other files and have a size determined by the sum of sizes of the files they contain.

File

public abstract class File {
  private String name;

  public File(String name) {
    this.name = name;
  }

  public abstract int getSize();
}

SingleFile

public class SingleFile extends File {
  private int size;

  public SingleFile(String name, int size) {
    super(name);
    this.size = size;
  }

  public int getSize() { return size; }
}

Folder

public class Folder extends File {
  private File[] contents;

  public Folder(String name, File[] contents) {
    super(name);
    this.contents = contents;
  }

  public int getSize() {
    // implementation on next slide
  }
}

Folder.getSize

public int getSize() {
  int size = 0;
  for (File f: contents) {
    size += f.getSize();
  }
  return size;
}

We’re using a loop to iterate over contents but we’re using recursion by calling getSize() on each of the files directly contained in this folder.

Any elements of contents that are also Folders will take care of computing their own size from their own contents.

Can we write getSize without recursion?

Sure. Anything’s possible.

But unlike fibonacci where we’re essentially moving through a linear sequence this is really a tree and if we don’t want to use recursion we need some other data structure to keep track of where we are in the tree.

Recursion: loops for trees

You know how to write a for loop to loop over a linear structure like an array, String, or ArrayList.

You know how to write nested for loops to iterate over a 2d structure like a String[][].

To iterate over a tree structure the natural way to do it is with recursion.

The structure of recursion

Every non-infinite recursion has two parts:

• One or more base cases

• One or more recursive cases

Base cases

In a recursive method, the base cases are the problems we can solve without any further recursive method calls.

You can think of the base cases as the smallest problems the method or recursive procedure knows how to solve.

Also the ones where they can’t be solved recursively.

What is the base case of factorial?

factorial(0)

What are the base cases of fibonacci?

Two base cases:

fib(0) and fib(1).

What are the base cases of getSize()?

The getSize method in SingleFile.

Recursive cases

Recursive cases are the rest—whenever the method invokes itself.

The recursive calls have to be used to to solve a smaller problem than the current problem so that eventually we will end up at a base case.

factorial recursive case

factorial(n - 1)

Clearly, n - 1 is clearly smaller than n so this meets our criteria.

fibonacci recursive cases

Two recursive cases:

fibonacci(n - 1) and fibonacci(n - 2)

And again, both n - 1 and n - 2 are smaller than n so they are both moving toward the base cases.

getSize recursive cases

The getSize method in Folder is recursive since it calls getSize on each File in contents.

We can think of the “size” of the problem as the number of layers of sub-folders in a File, with SingleFiles having zero.

Then each recursive call reduces this size by one, so solving a smaller problem.

Why recursion works

The call stack keeps track of where we are in the recursion.

Each method call has its own set of arguments.

Factorial visualization

Factorial visualization