CSC300 / CSC402: Pure recursive functions [11/14]

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

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

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

What does this function do?

  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):
Building up a table
Memoizing

  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))

It can be easier to think about this from the bottom up. Imagine trying this for f(5) or f(17).

Which is easier to reason about?