Factorial and its relatives

The official topic list names the computation of factorials as one of its examples, so you should be able to write one from a blank file. It is also the smallest complete recursion there is, which makes it a good place to check that a shape you think you understand actually works.

Factorial

The factorial of a whole number is that number multiplied by every whole number below it down to 1. So 4 factorial is 4 multiplied by 3 multiplied by 2 multiplied by 1, which is 24.

The definition is already recursive, which is why this example exists. The factorial of n is n times the factorial of n - 1, and the factorial of 0 is 1.

public static long factorial(int n)
{
    if (n < 0)
    {
        throw new IllegalArgumentException("factorial of a negative number is undefined, was " + n);
    }
    if (n == 0)
    {
        return 1;
    }
    return n * factorial(n - 1);
}

Three things in there are worth naming.

The base case is 0, not 1. Stopping at 1 also produces the right answer for every positive input, and it produces the wrong answer for 0, because it would never reach its own base case and would run down through the negative numbers forever. Mathematics says 0 factorial is 1, for the same reason an empty sum is 0: it is the value that changes nothing when you multiply by it.

The negative guard is separate from the base case. Negative numbers have no factorial, and the method has no correct value to return for one, so it throws. Widening the base case to n <= 0 would stop the recursion, and it would also quietly answer 1 for an input that has no answer, which is worse than crashing.

The return type is long and it still overflows. Factorials get large very fast. On an int, 12 factorial is 479001600 and fits, and 13 factorial does not, so it silently returns a negative number. On a long you get to 20 and then the same thing happens at 21. Nothing is thrown either time. This is not a recursion problem, it is what fixed-width integers do, and a recursion is just a convenient place to run into it.

The frames, for factorial(4):

going down
  factorial(4)  waits
  factorial(3)  waits
  factorial(2)  waits
  factorial(1)  waits
  factorial(0)  returns 1

coming back
  factorial(1)  1 * 1  returns 1
  factorial(2)  2 * 1  returns 2
  factorial(3)  3 * 2  returns 6
  factorial(4)  4 * 6  returns 24

Combine on return, the same shape as adding up an array on the way back. Nothing is multiplied until the base case gives the deepest frame something to multiply.

The same shape, 3 more times

Once factorial is in your hands, several standard methods are the same 4 lines with the operator changed.

// add the whole numbers from 1 to n
public static int sumTo(int n)
{
    if (n == 0)
    {
        return 0;
    }
    return n + sumTo(n - 1);
}

// base raised to an exponent, for a whole exponent
public static long power(long base, int exponent)
{
    if (exponent == 0)
    {
        return 1;
    }
    return base * power(base, exponent - 1);
}

// how many digits a positive number has
public static int digits(int n)
{
    if (n < 10)
    {
        return 1;
    }
    return 1 + digits(n / 10);
}

The first 2 are factorial with a different operator, and their base cases return the value that changes nothing for that operator: 0 for adding, 1 for multiplying. The third one is worth reading twice, because what shrinks is not a counter. Integer division by 10 throws away the last digit, so the number itself is the thing getting smaller, and the base case is a number with one digit left.

That is the general move. Find something in the problem that gets strictly smaller and cannot go on getting smaller forever. It does not have to be an index, and on these 3 it is not.

Fibonacci, and why it is the expensive one

The Fibonacci numbers start 0, 1, and every one after that is the sum of the 2 before it: 0, 1, 1, 2, 3, 5, 8, 13. The definition is recursive, so the method writes itself.

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

It is correct and it is the standard example of a recursion that costs far more than it looks like it costs. The reason is the 2 calls. Every call makes 2 more, so the number of calls roughly doubles with each step of n, and most of them recompute answers other calls already worked out.

fib(5)
├── fib(4)
│   ├── fib(3)
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)
└── fib(3)
    ├── fib(2)
    └── fib(1)

Count the repeats in that picture. fib(3) is worked out twice, once under fib(4) and once directly under fib(5), and neither one knows the other did it. fib(2) is worked out 3 separate times.

fib(5) makes 15 calls to compute a number you could work out on your fingers. fib(30) makes about 2.7 million. Nothing is wrong with the recursion: every base case is reached, every call is smaller, and the answer is right. The work is simply repeated, over and over, for values that were already known.

This is the same thing the official topic list's efficiency sentence is pointing at, met from a different direction, and it connects straight back to the ordering lesson. A method can be correct, terminate, and still be doing a quantity of work nobody asked for.

The 2 standard repairs both exist and neither is what these problems are asking for. You can remember answers you already computed so each one is worked out once, which is called memoization. You can carry the last 2 values down in parameters, which makes it a single chain of calls with no branching, and which is the same carry-down shape the array problems use.

// carry down: one call per step, no repeated work
private static int fib(int n, int previous, int current)
{
    if (n == 0)
    {
        return previous;
    }
    return fib(n - 1, current, previous + current);
}

What factorial is actually for

A loop computes any of these in fewer keystrokes and uses one frame instead of n of them. Real code computes factorial with a loop.

The reason to have them cold is that they are the smallest complete examples of the shape. Each one is 4 lines with a base case, a shrinking argument, and a combine on the way back, and you can check one by hand in 10 seconds. Get the shape right on a problem where the answer is obvious, and you will recognize it on a problem where it is not. The problems that actually need recursion are the ones where the structure is nested or branching, and a loop would have to carry its own stack of unfinished work to imitate the call stack you are getting for free.

In the practice APE

The Practice APE Exam Instructions have no factorial problem. Both recursion problems in that set are on arrays: finding the largest value, and reversing an array in place, both worked in Recursion on an array.

The official topic list names factorial directly as an example of what may be asked for, alongside printing a linked list in reverse and other recursive algorithms at the level covered in the earlier courses. A problem built on it would look like the methods above: a public method with the precondition check, and a short body with a base case and one multiplication.

Readiness check

Work each one on paper and write the answer down before you open it.

The one thing to keep

Factorial is the smallest complete recursion: a base case at 0 returning 1, a call on n - 1, and a multiplication on the way back. Adding, raising to a power and counting digits are the same 4 lines with a different operator, and in the digit case what shrinks is the number itself rather than a counter. A guard for input the job has no answer for is a separate thing from the base case, and widening the base case to swallow it hides a wrong answer. Fibonacci is correct and expensive, because 2 calls per frame means the same values get computed again and again, which is the efficiency question showing up inside a recursion.