Recurrence Relations: Factorial

Recurrence Relation: Recursive Factorial Example video (13 minutes) (Spring 2021)

Motivation

Recurrence relations can aid in determining Big-O complexity of recursive functions. A recurrence relation is a relationship in which a function T(...) occurs on both sides of the = sign. For example, T(n) = 1 + T(n / 2).

General steps for solving a recurrence relation

1. Understand what the recursive algorithm is actually doing, and identify base case(s). Identify general recursive case. Identify how the input shrinks as progress is made towards the base case.
2. Formalize the recurrence relation. Express the base case(s) and general case in T(n) notation, or running time syntax. (See below example)
3. Iterate/expand a few times, plugging in shrinking values of n. Simplify the resulting expression.
4. Spot a pattern that emerges, which can be express in terms of "k", the number of iterations taking place.
5. Write the recurrence relation in terms of k
6. Identify a value of k, given how k and n interact in the relation, such that a base case with a known value can substituted into the relation.
7. Finally, solve the relation using the known values.

Factorial example

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

1. Understand, identify base/general cases

This function recursively calculates the factorial of a positive number n, or n!. Eg, 3! = 3 * 2 * 1 = 6;

The base case of 0 simply returns 1. (Since we don't want to multiply by 0, and multiplying by 1 preserves the result.)

Returning 1 is a constant time operation.

So T(0) = 1.

The general recursive case multiplies n by the result of the function, called on 'n - 1'.

This is a constant time operation plus an operation that has a running time linked to 'n - 1'.

So, T(n) = 1 + T(n - 1).

1. Formalize recurrence relation

We now have our base case and general recursive case:

Base: T(0) = 1

General: T(n) = 1 + T(n - 1)

1. Iterate/expand/simplify the general case relation

T(n) = 1 + T(n - 1)
T(n) = 1 + (1 + T((n - 1) - 1))
T(n) = 2 + T(n - 2)
T(n) = 2 + (1 + T((n - 2) - 1))
T(n) = 3 + T(n - 3)

1. Spot a pattern, in terms of "k" iterations

Each iteration, the leading term grows by 1, and the term subtracted from n grows by 1.

1. Write the relation in terms of k

T(n) = k + T(n - k)

1. Identify a k value that allows substitution of a base case

We know that T(0) = 1. So what value of k will let us substitute in T(0) to this relation?

With the term T(n - k) present, that question can be expressed as n - k = 0, or n = k.

Substituting in n for k ...

T(n) = n + T(n - n)
T(n) = n + T(0)

1. Solve using known values

We know that the base case T(0) = 1. Substitute this in.

T(n) = n + 1.

O(T(n)) = O(n + 1)

O(T(n)) = O(n)

The recursive function is O(n). This is intuitive, since each term between n and 0 must be accessed to calculate the factorial.

Thanks

Thanks to Brian Foster for writing up these notes.