Start learning free

LESSON 251 OF 338 · RECURSION

Recursive Fibonacci in Go

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

    GO · RECURSION

    Recursive Fibonacci in Go, 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 named n, between 0 and 30, and returns F(n) using recursion.

    For n = 4 the sequence runs 0, 1, 1, 2, 3, so the answer is 3. Written as a calculation: F(4) = F(3) + F(2) = 2 + 1 = 3.

    Approach: the definition is already a recursive function

    A recursive function solves a problem by calling itself on smaller versions of the same problem. The Fibonacci definition has exactly that shape. To get F(n) you need F(n - 1) and F(n - 2), and each of those is another Fibonacci number with a smaller index.

    Every recursive function needs two parts:

    • A base case that returns an answer directly, without calling itself. Here it covers F(0) and F(1).
    • A recursive case that calls the function on smaller inputs and combines the results. Here it adds F(n - 1) and F(n - 2).

    Each recursive call must move closer to a base case. Here the argument shrinks by 1 or 2 on every call, so it eventually drops below 2. Without a base case the function would call itself until the program runs out of stack space and crashes.

    Step by step

    1. Handle the base case first. For n equal to 0 or 1 the answer is n itself, because F(0) = 0 and F(1) = 1. One check, n < 2, covers both, and it must come before any recursive call.
    2. Return the sum of the two previous numbers. For every other n, call fibonacci(n - 1) and fibonacci(n - 2) and add the results.

    The solution in Go

    func fibonacci(n int) int {
    if n < 2 {
        return n
    }
    return fibonacci(n-1) + fibonacci(n-2)
}

    A few Go details:

    • A Go function can call itself by name, with no special syntax.
    • The parameter and the result are both int, which is 64 bits here. F(30) is 832040, far below any limit.
    • The final return is required. Go rejects a function with a result type if some path through it can end without a return.
    • The if needs no else. When the condition is true the function returns, so the code below only runs for n >= 2.

    How the calls unfold

    Each call to fibonacci(n) with n >= 2 makes two more calls, so the calls form a tree. For fibonacci(4):

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

    The calls at the bottom return first, and their results flow upward: fibonacci(2) is 1, fibonacci(3) is 2, and fibonacci(4) is 3. Notice that fibonacci(2) is computed twice. That repeated work is the cost of this simple version.

    Cost and its limit

    The lesson doesn't ask for efficiency, but it helps to know the cost. The number of calls grows roughly by a factor of 1.6 each time n increases by 1, which is exponential. Counting the calls gives these totals:

    nResultCalls
    213
    439
    1055177
    308320402692537

    About 2.7 million calls for n = 30 is still quick, which is why the constraint stops at 30. For much larger n the same code would take far too long. The usual remedies are to remember results already computed or to build the sequence upward with a loop.

    Edge cases and common mistakes

    • Missing base case. Without the n < 2 check, fibonacci(1) would call fibonacci(0), then fibonacci(-1), and so on without end.
    • Base case that covers only one value. Checking just n == 0 sends fibonacci(1) into fibonacci(-1). Both starting values need to stop the recursion.
    • Wrong value in the base case. Returning 1 for every n < 2 shifts the sequence and makes F(0) wrong. Returning n is correct for both.
    • Calling with the same argument. Writing fibonacci(n) + fibonacci(n-1) never shrinks the first call, so it recurses forever.

    Testing

    Try these inputs in the editor above: fibonacci(0) should give 0, fibonacci(1) gives 1, fibonacci(2) gives 1, fibonacci(10) gives 55 and fibonacci(30) gives 832040.

    Keep going with GoAbout 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free