DEV Community

Vansh Aggarwal
Vansh Aggarwal

Posted on

LeetCode Solution: 509. Fibonacci Number

#leetcode #dsa #programming #tutorial

Unraveling the Magic of Fibonacci: Your First Dive into Recursion with LeetCode 509! ✨

Hey fellow coders! 👋 Vansh here, ready to embark on another exciting LeetCode adventure with you. Today, we're tackling a classic that's a rite of passage for many beginners: the Fibonacci Number problem (LeetCode 509).

Don't let the mathematical name scare you! The Fibonacci sequence is incredibly elegant and a perfect entry point into one of the most powerful programming techniques: recursion. Let's dive in!

🧐 Problem Explanation: What's a Fibonacci Number?

The Fibonacci sequence is like a fascinating number story where each number is the sum of the two numbers before it. It starts very simply:

  • The 0th Fibonacci number, F(0), is 0.
  • The 1st Fibonacci number, F(1), is 1.

And then, for any number n greater than 1, we find F(n) by adding F(n-1) and F(n-2).

So, the sequence looks like this:

0, 1, 1, 2, 3, 5, 8, 13, 21, ...

Let's trace some examples to make it super clear:

  • F(2): Since 2 > 1, F(2) = F(1) + F(0) = 1 + 0 = 1.
  • F(3): Since 3 > 1, F(3) = F(2) + F(1) = 1 + 1 = 2.
  • F(4): Since 4 > 1, F(4) = F(3) + F(2) = 2 + 1 = 3.

Our Goal: Given a number n, we need to calculate and return the n-th Fibonacci number, F(n). The problem guarantees n will be between 0 and 30, which keeps things manageable!

🤔 Intuition: The "Aha!" Moment

When you look at the definition F(n) = F(n - 1) + F(n - 2), what's the first thing that pops into your mind? For me, it's that to solve for F(n), I need the solutions for F(n-1) and F(n-2).

This is the classic hallmark of recursion! A problem that can be broken down into smaller, identical sub-problems, and eventually reaches a simple, known base case.

Think of it like a set of Russian nesting dolls. To open the largest doll, you need to open the next smallest, and so on, until you get to the tiny one that's easy to open.

🪜 Approach: Let's Get Recursive!

Our approach will directly translate the mathematical definition into code using recursion.

Here's how we'll break it down:

  1. Identify the Base Cases: These are our "stopping points" – the scenarios where we already know the answer and don't need to do any further calculations.

    • If n is 0, we know F(0) is 0.
    • If n is 1, we know F(1) is 1. These two conditions are crucial because they prevent our function from calling itself infinitely!

  2. Identify the Recursive Step: For any other n (i.e., n > 1), we simply follow the formula:

    • F(n) = F(n - 1) + F(n - 2). In code, this means our fib(n) function will call fib(n-1) and fib(n-2) and sum their results.

Let's trace fib(4) with this approach:

fib(4)
  -> fib(3) + fib(2)
       |         |
       v         v
   (fib(2) + fib(1)) + (fib(1) + fib(0))
    |     |      |      |     |     |
    v     v      v      v     v     v
 (fib(1)+fib(0)) + 1 + 1 + 0
  |     |
  v     v
 (1 + 0) + 1 + 1 + 0
   1    + 1 + 1 + 0 = 3
Enter fullscreen mode Exit fullscreen mode

See how it naturally unravels back to the base cases? Pretty neat, right?

💻 Code: Bringing It to Life 

class Solution {
public:
    int fib(int n) {
        // Base case 1: If n is 0, F(0) is 0.
        if (n == 0) {
            return 0;
        }
        // Base case 2: If n is 1, F(1) is 1.
        if (n == 1) {
            return 1;
        }

        // Recursive step: For n > 1, F(n) = F(n-1) + F(n-2).
        // The function calls itself with smaller values of n.
        return fib(n - 1) + fib(n - 2);
    }
};
Enter fullscreen mode Exit fullscreen mode

⏱️ Time & Space Complexity Analysis

This is an important part of understanding any solution!

  • Time Complexity: O(2^n)

    • "Wait, what?! Exponential?" Yes, for this naive recursive solution, the time complexity is exponential. Let's look at why.
    • Notice in our trace of fib(4), we calculated fib(2) twice, fib(1) three times, and fib(0) twice. As n grows, the number of redundant calculations explodes.
    • Each call to fib(n) makes two more calls (fib(n-1) and fib(n-2)), creating a call tree. The number of nodes in this tree grows exponentially.
    • For n=30, this will still be fast enough on LeetCode because 2^30 is a large number, but the actual number of unique computations is much smaller. The constraints (n <= 30) are set to allow this simple recursive solution to pass.
    • (Quick hint for future learning: This is where memoization or dynamic programming comes in handy to optimize Fibonacci to O(n) time!)

  • Space Complexity: O(n)

    • This complexity comes from the recursion stack. Each time fib calls itself, a new "frame" is pushed onto the call stack.
    • In the worst case (e.g., calculating fib(n)), the deepest path in our recursion tree will go n levels deep (e.g., fib(n) -> fib(n-1) -> fib(n-2) ... -> fib(0)).
    • So, at most n function calls will be waiting on the stack.

💡 Key Takeaways

  1. Recursion is Powerful: It allows us to solve problems by breaking them into smaller, identical instances, often leading to very elegant and readable code.
  2. Base Cases are Critical: Without proper base cases, recursive functions will run into infinite loops (or stack overflow errors). They are the "escape route" from the recursion.
  3. Understand Complexity: While simple, naive recursion (like this fib implementation) can be inefficient for larger inputs due to repeated computations. This problem is a fantastic introduction to identifying such inefficiencies and thinking about potential optimizations (like memoization or iterative approaches).
  4. Practice Tracing: Drawing out the recursion tree, like we did for fib(4), is an invaluable skill for understanding how recursive functions execute.

That's it for LeetCode 509! I hope this helped you understand the Fibonacci sequence and the beauty of recursion a little better. Keep coding, keep learning, and I'll catch you in the next one!

Authored by Vansh2710 | Published on 2026-04-16 01:17:58

Top comments (0)