Start learning free

LESSON 281 OF 414 · RECURSION

Recursive Fibonacci in Scala

Practice O(2n) Read the full explanation

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

F(0) = 0, F(1) = 1
F(n) = F(n - 1) + F(n - 2), for n > 1.

Write a recursive function that given n, returns F(n).

Example 1:

Input: n = 2
Output: 1
Explanation: F(2) = F(1) + F(0) = 1 + 0 = 1.

Example 2:

Input: n = 3
Output: 2
Explanation: F(3) = F(2) + F(1) = 1 + 1 = 2.

Example 3:

Input: n = 4
Output: 3
Explanation: F(4) = F(3) + F(2) = 2 + 1 = 3.

Constraints:
  • 0 <= n <= 30
Note:

Don't worry about the time and space complexities of your algorithm.


Hints:

Inside the function, we should first check the base case: if n is less than 2, then we should return n.

If n >= 2, since F(n) = F(n - 1) + F(n - 2), we should return the sum of the recursive calls for n - 1 and n - 2.
STEP 1 OF 2
    Ctrl + Enter to check

    SCALA · RECURSION

    Recursive Fibonacci in Scala, explained

    Problem overview

    The Fibonacci sequence starts with F(0) = 0 and F(1) = 1, and every later number is the sum of the two before it: F(n) = F(n - 1) + F(n - 2) for n > 1. The method fibonacci takes an Int named n, between 0 and 30, and returns F(n) using recursion.

    The first terms are 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55. So fibonacci(2) is 1, fibonacci(3) is 2, and fibonacci(4) is 3.

    The statement says not to worry about time and space, so the goal is a clear translation of the definition into code.

    Approach: the definition is the algorithm

    The formula already describes a recursive method. It has two base cases, F(0) and F(1), which can be answered immediately, and a recursive case that combines the answers for n - 1 and n - 2. Both arguments are smaller than n, so every chain of calls moves toward a base case and ends.

    The two base cases have a convenient shared property: for n equal to 0 or 1, the answer is n itself. One check, n < 2, covers both.

    Step by step

    1. If n < 2, return n. This handles F(0) = 0 and F(1) = 1. Without it, each call would make two more calls forever, and the program would crash.
    2. Otherwise, return fibonacci(n - 1) + fibonacci(n - 2).

    For fibonacci(4), the calls expand like this:

    fibonacci(4)
  fibonacci(3)
    fibonacci(2)
      fibonacci(1) = 1
      fibonacci(0) = 0
    fibonacci(1) = 1
  fibonacci(2)
    fibonacci(1) = 1
    fibonacci(0) = 0

    Adding from the bottom: fibonacci(2) is 1 + 0 = 1, fibonacci(3) is 1 + 1 = 2, and fibonacci(4) is 2 + 1 = 3.

    The solution in Scala

    class Solution {
    def fibonacci(n: Int): Int = {
        if (n < 2) {
            return n
        }
        return fibonacci(n - 1) + fibonacci(n - 2)
    }
}

    Scala details

    A method that calls itself must declare its result type, which is why the signature says : Int. The compiler won't infer it for a recursive method.

    The last expression of a method is its value, so return can be left out. The same method can be written as a single expression:

    def fibonacci(n: Int): Int =
  if (n < 2) n else fibonacci(n - 1) + fibonacci(n - 2)

    Here if / else is an expression that produces a value. The lesson's version spells out return, and the two behave the same.

    An Int is 32 bits and overflow wraps silently. Fibonacci numbers fit comfortably for the allowed inputs: fibonacci(30) is 832040. The first number that does not fit in an Int is F(47), but a recursive calculation of that size would take far too long anyway.

    Complexity

    Each call that isn't a base case makes two more calls, so the number of calls grows exponentially: roughly like 1.6 to the power n. Counting the calls directly gives 15 for fibonacci(5) and 2,692,537 for fibonacci(30). That is fine for n up to 30, and it explains the limit in the constraints. The time is exponential, and the stack holds at most n calls at a time, so the space is O(n).

    The slowness comes from repeated work. In the expansion of fibonacci(4) above, fibonacci(2) is computed twice and fibonacci(1) three times. Storing results that were already computed, or building the sequence from the bottom up with a loop, brings the time down to O(n). This lesson shows the plain version so that you see the recursion first.

    Edge cases and common mistakes

    • Forgetting the base case. The calls never stop, and the program ends with a StackOverflowError.
    • Handling only n == 0. Then fibonacci(1) calls fibonacci(0) and fibonacci(-1), and the second one never reaches a base case. Both 0 and 1 must be base cases.
    • Using the wrong threshold. With n <= 2 returning n, fibonacci(2) would return 2 instead of 1.
    • Returning the sum of the calls on n. The recursive calls must use n - 1 and n - 2. Calling with n again repeats the same problem and never ends.
    • Negative input. The constraints keep n at 0 or above. Since -1 < 2, a negative n would simply return n itself, which is not a Fibonacci number.

    Testing

    • fibonacci(0) returns 0 and fibonacci(1) returns 1.
    • fibonacci(2) returns 1.
    • fibonacci(10) returns 55.
    • fibonacci(30) returns 832040.
    Keep going with ScalaAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free