14.9: One More Example

Another common recursively-defined mathematical function is the Fibonacci sequence, which has the following definition:

\[\begin{align*} & fibonacci(1) = 1 \\[4pt] & fibonacci(2) = 1 \\[4pt] & fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2) \nonumber \end{align*} \]

Translated into Java, this function is:

public static int fibonacci(int n) {
    if (n == 1 || n == 2) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

If you try to follow the flow of execution here, even for small values of n, your head will explode. But if we take a leap of faith and assume that the two recursive invocations work correctly, it is clear that their sum is the result.