Skip to main content
Engineering LibreTexts

14.9: One More Example

  • Page ID
    18883
  • 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.

    • Was this article helpful?