CSC300: Recursion, Briefly: Reading pure recursive functions [3/37] |
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.
01 |
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))