Start learning free

LESSON 257 OF 348 · RECURSION

Recursive Fibonacci in Kotlin: Two Base Cases and Two Calls

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 fibonacci(n - 1) + fibonacci(n - 2).
STEP 1 OF 2
    Ctrl + Enter to check

    KOTLIN · RECURSION

    Recursive Fibonacci in Kotlin, explained

    Problem overview

    The Fibonacci numbers start 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). The function fibonacci takes an Int n between 0 and 30 and returns F(n), using recursion.

    The sequence begins 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. So fibonacci(2) is 1, fibonacci(3) is 2 and fibonacci(4) is 3. The statement doesn't ask for any particular complexity.

    Approach: copy the definition

    The definition is already recursive, so the code can follow it directly. Two cases are answered without recursion, and every other n splits into two smaller subproblems:

    • Base case: when n is less than 2, return n. F(0) is 0 and F(1) is 1, so in both cases the answer is n itself, and one if covers them.
    • Recursive case: otherwise return fibonacci(n - 1) + fibonacci(n - 2).

    Unlike a factorial, which has a single recursive call per level, this function calls itself twice. The calls form a tree. For fibonacci(4) the tree is:

    fibonacci(4)
  fibonacci(3)
    fibonacci(2)
      fibonacci(1) -> 1
      fibonacci(0) -> 0
    fibonacci(1) -> 1
  fibonacci(2)
    fibonacci(1) -> 1
    fibonacci(0) -> 0

    The leaves return 1, 0, 1, 1 and 0, and the sums on the way up give fibonacci(2) = 1, fibonacci(3) = 2 and fibonacci(4) = 3.

    Step by step

    1. Handle the base case first. Write if (n < 2) and return n. Without this, every call would make two more calls and the recursion would never stop.
    2. Combine the two previous numbers. For every other n, return fibonacci(n - 1) + fibonacci(n - 2).

    The solution in Kotlin

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

    The Kotlin details worth a closer look:

    • Calling a member from itself. Inside the class, fibonacci(n - 1) refers to the same method. The declared return type : Int matters: a function with a block body and no declared type returns Unit, so the sum would not compile.
    • Int is enough for this range. F(30) is 832040. The largest Fibonacci number that fits in an Int is F(46) = 1836311903. F(47) would be 2971215073, so it wraps around to a negative number.
    • Several returns. The base case returns early. The last line returns the sum. Both branches end in a return, so the compiler is satisfied that every path returns an Int.

    Why it is slow, and why that is fine here

    Each call makes two more calls, and the same subproblems are solved again and again. In the tree above, fibonacci(2) is computed twice and fibonacci(1) three times. The number of calls grows exponentially: fibonacci(5) makes 15 calls and fibonacci(30) makes 2,692,537. That is acceptable for the limit of 30 here, and the statement says not to worry about complexity. At n = 45 the same code would need billions of calls.

    The time is roughly O(2^n) (more precisely, proportional to F(n) itself). The call stack depth is only n, because the deepest chain follows n - 1 repeatedly, so the space is O(n). A loop that keeps the last two numbers computes the same value in O(n) time and O(1) space, and caching results in a map removes the repeated work as well; both come up later in the course.

    Edge cases and common mistakes

    • n = 0 and n = 1. Both hit the base case and return n: 0 and 1.
    • A base case that only covers 0. fibonacci(1) would call fibonacci(0) and fibonacci(-1), and the second call never reaches a base case. The program ends with a StackOverflowError.
    • A base case that returns 1 for both. That shifts the whole sequence: fibonacci(2) would be 2.
    • Using only one previous number. Something like fibonacci(n - 1) * 2 doesn't follow the definition. The sum needs both n - 1 and n - 2.
    • Forgetting the base case's return. Writing just n on its own line computes the value and throws it away, and the function goes on to make recursive calls that never stop.

    Testing

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