CSC300: Pure recursive functions [10/13]

A function is pure if it does not change any non-local variables, read files or network connections, or make any output.

Pure functions are like functions in math: they always do the same thing.

To understand the execution of a pure recursive function, it is easiest to start at the base case and work your way up.

  public static int f (int n) {
    if (n <= 0) return 1;
    int nMinus1 = f (n-1);
    return n * nMinus1;
  }

Bottom up (from the base case):

  f(0) = 1
  f(1) = 1 * f(0) = 1
  f(2) = 2 * f(1) = 2
  f(3) = 3 * f(2) = 6
  f(4) = 4 * f(3) = 24
  f(5) = 5 * f(4) = 120

Top down (from the initial argument):

  f(3) = 3 * f(2) 
       = 3 * (2 * f(1)) 
       = 3 * (2 * (1 * f(0)))
       = 3 * (2 * (1 * 1))