Start learning free

LESSON 257 OF 348 · RECURSION

Recursive Fibonacci in TypeScript: Two Calls per Step

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

    TYPESCRIPT · RECURSION

    Recursive Fibonacci in TypeScript, explained

    Problem overview

    The Fibonacci numbers form a sequence in which each number is the sum of the two before it, starting from 0 and 1: F(0) = 0, F(1) = 1, and F(n) = F(n - 1) + F(n - 2) for n > 1. The method fibonacci receives n, between 0 and 30, and returns F(n) using recursion. The lesson does not set a time or space target.

    The sequence begins 0, 1, 1, 2, 3, 5, 8, 13. For example F(4) = F(3) + F(2) = 2 + 1 = 3.

    Approach: the definition is the code

    The formula is already recursive, so the solution is a direct translation of it. There are two base cases, F(0) and F(1). They look different, but in both of them the answer equals n, so one check covers them: if n is less than 2, return n. For any larger n, return the sum of the results for n - 1 and n - 2.

    Here is how fibonacci(4) unfolds:

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

    The results add up from the bottom: fibonacci(2) is 1 + 0 = 1, fibonacci(3) is 1 + 1 = 2, and fibonacci(4) is 2 + 1 = 3.

    Step by step

    1. Handle the base cases. If n < 2, return n. Because F(0) = 0 and F(1) = 1, both answers equal the input. Without this check each call would make two more, and the recursion would never stop.
    2. Add the two previous numbers. Return this.fibonacci(n - 1) + this.fibonacci(n - 2). The method belongs to the class, so both calls go through this.

    The solution in TypeScript

    class Solution {
    fibonacci(n: number): number {
        if (n < 2) {
            return n;
        }
        return this.fibonacci(n - 1) + this.fibonacci(n - 2);
    }
}

    Some TypeScript details:

    • Calls through this. Inside a method, fibonacci(n - 1) on its own would not find the method. this.fibonacci(n - 1) does.
    • number is enough. TypeScript has a single numeric type, a double, so there is no int to choose. The values stay far below 2^53 in this lesson: F(30) is 832040.
    • Types are erased. The number annotations help the compiler, but they vanish from the compiled JavaScript and check nothing at run time.
    • An early return replaces else. When the if returns, the rest of the function only runs for other inputs, so no else is needed.

    Reading the recursion

    When you read or debug a recursive function, check three things in order. First, does every call that is not a base case move toward a base case? Here n - 1 and n - 2 both get smaller. Second, do the base cases cover every way the inputs can end? From any n of 2 or more, subtracting 1 or 2 ends at 0 or 1, never skipping below them. Third, is the combination correct? If the smaller calls return the right values, their sum is the right value for n. When all three hold, the function is correct for every input, which is how induction works.

    Why this version is slow

    Each call makes two more, and the same subproblems are solved again and again. In the tree above, fibonacci(2) is computed twice, and fibonacci(1) three times. Counting every call, fibonacci(5) makes 15, and fibonacci(30) makes 2,692,537. The time grows exponentially, about 1.6 times for each step in n. That is acceptable for n up to 30, and the reason the lesson sets that limit. The recursion depth is only n, so the stack is never close to overflowing here.

    Remembering results already computed (memoization), or building the sequence with a loop from the bottom up, brings the time down to O(n).

    Edge cases and common mistakes

    • A base case of only n === 0. Then fibonacci(1) would call fibonacci(0) and fibonacci(-1), and the second one never ends.
    • Returning 1 for n === 0. It is easy to mix up the sequence's start. This lesson starts from F(0) = 0.
    • Calling with n - 1 twice. fibonacci(n - 1) + fibonacci(n - 1) doubles the previous number instead of adding the two before.
    • Negative input. fibonacci(-3) returns -3, because -3 < 2. The constraints exclude it.
    • Large n. On one test machine fibonacci(40) took about a second and fibonacci(45) about eleven, and every step up in n multiplies the time by roughly 1.6. This version is for small inputs.

    Testing

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