Start learning free

LESSON 256 OF 347 · RECURSION

Recursive Fibonacci in C#: Two Base Cases, 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

    C# · RECURSION

    Recursive Fibonacci in C#, 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 sequence begins 0, 1, 1, 2, 3, 5, 8, 13, and so on.

    The lesson asks for a recursive method, int Fibonacci(int n), that returns F(n) for 0 <= n <= 30. For n = 4 the answer is 3, because F(4) = F(3) + F(2) = 2 + 1.

    The definition is already recursive, so the code can follow it almost word for word. The lesson says not to worry about time and space, which makes this a good first look at a method that calls itself twice.

    Approach: turn the definition into code

    A recursive method needs a base case that stops the calls and a recursive case that moves toward it. Fibonacci has two starting values, so its base case covers both. For n = 0 the answer is 0, and for n = 1 it is 1. In both cases the answer equals n, so a single check for n < 2 that returns n handles them together.

    For any larger n, return Fibonacci(n - 1) + Fibonacci(n - 2). Both calls use smaller arguments, so every chain of calls ends at a base case.

    Step by step

    1. Handle the base case first. If n < 2, return n. Without it, the calls would go on to Fibonacci(-1), Fibonacci(-2) and further, never stopping.
    2. Return the sum of the two previous numbers: Fibonacci(n - 1) + Fibonacci(n - 2).

    The solution in C#

    class Solution {
    public int Fibonacci(int n) {
        if (n < 2) {
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

    How the calls unfold

    Here is Fibonacci(4), written as a tree where each line is one call:

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

    Working upward: Fibonacci(2) is 1 + 0 = 1, Fibonacci(3) is 1 + 1 = 2, and the second Fibonacci(2) is 1 again. So Fibonacci(4) is 2 + 1 = 3. This tree makes 9 calls in total.

    Notice that Fibonacci(2) is computed twice, and Fibonacci(1) three times. The method has no memory of earlier answers, so the same work repeats. The repeats multiply as n grows. Computing Fibonacci(30), which is 832040, takes 2,692,537 calls. That is fine for this lesson, whose input stops at 30, but the call count grows exponentially, and each step of n multiplies the work by about 1.6. Remembering results already computed, called memoization, or building the sequence upward in a loop, brings the cost down to linear time.

    C# details worth knowing

    • The result fits in an int. F(30) = 832040, far below 2,147,483,647. In C#, int overflow wraps silently, so with larger inputs the sums would turn wrong without any error. F(46) is the last Fibonacci number that fits in an int.
    • Two calls in one expression. The expression Fibonacci(n - 1) + Fibonacci(n - 2) evaluates its left operand first, so the left chain of calls runs to completion before the right one starts.
    • Depth is small. The call stack gets as deep as n frames, because the n - 1 branch goes down first. That is nothing to worry about for n <= 30.
    • Names. The method is Fibonacci, in PascalCase. A call spelled fibonacci would not compile in C#.

    Edge cases and common mistakes

    • Checking only n == 0. Then Fibonacci(1) calls Fibonacci(0) and Fibonacci(-1), and the second call never reaches the base case. Both starting values need to be covered, which n < 2 does.
    • Returning 1 for the base case. That gives the wrong value for n = 0. Returning n is correct for both starting values.
    • Calling Fibonacci(n - 1) twice or mixing up n - 2 and n - 1 in the sum. The two terms must be the previous two numbers.
    • Expecting speed. This version is simple, not fast. Do not use it for much larger n.

    Testing

    nresult
    00
    11
    21
    32
    43
    1055
    Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free