Fibonacci Sequence Using Recursion

The Fibonacci sequence is one of the most celebrated patterns in mathematics, and it also serves as a cornerstone example in computer science for understanding recursion. What makes the Fibonacci sequence so compelling from a programming perspective is that its mathematical definition is inherently self-referential — each number is defined in terms of previous numbers in the same sequence. This natural self-reference maps almost directly onto the concept of a recursive function, making Fibonacci an ideal subject for studying how recursion works, how the call stack behaves when a function calls itself more than once, and what performance consequences emerge from that behavior.

The Fibonacci sequence begins with two fixed starting values and then builds every subsequent value from the two that came before it. The sequence looks like this: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, and so on. The formal mathematical definition captures this pattern with two base values and one recurrence rule:

• Fibonacci(0) = 0 — the zeroth position in the sequence holds the value 0.
• Fibonacci(1) = 1 — the first position in the sequence holds the value 1.
• Fibonacci(n) = Fibonacci(n - 1) + Fibonacci(n - 2) for every n greater than 1.

Notice that the rule for computing any Fibonacci number beyond the first two is expressed purely in terms of earlier Fibonacci numbers. This is exactly what recursion exploits: to find the answer for a large problem, break it into smaller problems of the same shape, solve those, and combine the results. The two starting values — Fibonacci(0) and Fibonacci(1) — act as the stopping points that prevent the self-referential process from going on forever.

Defining the Base Cases

Every recursive function must have at least one base case: a condition under which the function returns a direct answer without calling itself again. Base cases are the foundation of any recursive solution because they anchor the chain of calls. Without them, recursion would descend infinitely, eventually causing a stack overflow error.

For the Fibonacci sequence, there are exactly two base cases, and both are necessary:

• When n === 0, return 0. This represents the zeroth element of the sequence. No further recursion is needed; the answer is simply 0.
• When n === 1, return 1. This represents the first element of the sequence. Again, the answer is known directly and no further recursion is required.

Together, these two base cases ensure that every possible chain of recursive calls will eventually reach a stopping point. Because every recursive call reduces n by either 1 or 2, and because both 0 and 1 are covered by base cases, no call chain can descend below zero. This guarantees termination for any non-negative integer input.

It is worth noting that having two base cases is a direct consequence of the recurrence relation itself. The relation references both n - 1 and n - 2, so both of those positions must have explicitly defined values — otherwise the recursion would have nowhere to stop when it reaches the very bottom of the sequence.

Implementing Fibonacci Recursively in JavaScript

Translating the mathematical definition into a JavaScript function is remarkably straightforward because the structure of the code mirrors the structure of the definition almost line for line. The function accepts a single integer n representing the position in the sequence, checks for the two base cases, and otherwise returns the sum of two recursive calls.

function fibonacci(n) {
  // Base case: the 0th Fibonacci number is 0
  if (n === 0) return 0;

  // Base case: the 1st Fibonacci number is 1
  if (n === 1) return 1;

  // Recursive case: sum of the two preceding Fibonacci numbers
  return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(4));  // 3
console.log(fibonacci(6));  // 8
console.log(fibonacci(10)); // 55

The critical line is the return fibonacci(n - 1) + fibonacci(n - 2) statement. This single line launches two separate recursive calls before the current function invocation can produce a result. The JavaScript runtime must fully resolve fibonacci(n - 1) (itself potentially triggering many more calls), then fully resolve fibonacci(n - 2), and only then can it add the two results together and return from the current frame.

This distinguishes Fibonacci recursion sharply from simpler recursive functions like computing a factorial. A factorial function makes only one recursive call per invocation:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1); // only ONE recursive call
}

The factorial call chain is a straight line — each frame waits for exactly one child to return. Fibonacci, on the other hand, creates a branching tree of calls because each frame spawns two children. This branching is what gives Fibonacci its distinctive performance characteristics and makes it an important case study.

How the Call Stack Grows with Two Recursive Calls

To understand why two recursive calls per invocation is significant, it helps to visualize the call tree that forms when fibonacci(n) is evaluated. Each node in the tree represents one function invocation. Each non-base-case node has exactly two children: one for fibonacci(n - 1) and one for fibonacci(n - 2). Leaf nodes are the base cases that return 0 or 1 without branching further.

Consider fibonacci(5). The call tree begins to expand like this:

fibonacci(5)
├── fibonacci(4)
│   ├── fibonacci(3)
│   │   ├── fibonacci(2)
│   │   │   ├── fibonacci(1)  → 1
│   │   │   └── fibonacci(0)  → 0
│   │   └── fibonacci(1)      → 1
│   └── fibonacci(2)
│       ├── fibonacci(1)      → 1
│       └── fibonacci(0)      → 0
└── fibonacci(3)
    ├── fibonacci(2)
    │   ├── fibonacci(1)      → 1
    │   └── fibonacci(0)      → 0
    └── fibonacci(1)          → 1

Two important structural properties emerge from this tree:

• The depth of the call stack at any moment equals n. The deepest branch descends from fibonacci(n) all the way down by subtracting 1 at each step until it reaches fibonacci(0) or fibonacci(1). That path has exactly n frames deep. This means for fibonacci(50), the call stack could hold up to 50 frames simultaneously — manageable in terms of stack depth, but the total number of calls is what becomes problematic.
• The total number of calls grows exponentially. Because each node doubles the work, the tree has roughly 2ⁿ nodes in total. For fibonacci(5) the tree is already 15 nodes. For fibonacci(30) it grows to over a billion calls.

At any given moment during execution, the JavaScript engine holds only the frames along one active path from root to leaf — not the entire tree at once. But the engine must visit every node eventually, which is what drives the total execution time upward so dramatically.

Performance Trade-offs of Naive Recursive Fibonacci

The naive recursive implementation of Fibonacci is elegant and easy to understand, but it is severely inefficient for large values of n. The core problem is redundant computation: the same subproblems are solved over and over again across different branches of the call tree.

Look again at the call tree for fibonacci(5). Notice that fibonacci(2) appears three times, fibonacci(3) appears twice, and fibonacci(1) and fibonacci(0) appear multiple times. Every single one of these repeated calls does the full work of recomputing the result from scratch. As n grows, the redundancy multiplies catastrophically.

The time complexity of naive recursive Fibonacci is O(2ⁿ). This is an exponential growth rate, which is among the worst possible. To put it in concrete terms:

Each increment of n roughly doubles the number of calls. This doubling behavior is the hallmark of O(2ⁿ) complexity. By contrast, a well-optimized iterative or memoized approach computes fibonacci(n) in O(n) time — linear rather than exponential — by ensuring each subproblem is computed only once.

The space complexity of naive recursive Fibonacci is O(n) because, at any one moment, the deepest live call chain holds at most n frames on the call stack simultaneously. Although the total work is exponential, the memory footprint at any instant is only linear — each frame along the currently active path occupies stack space, and once a branch resolves, its frames are popped.

Recognizing these trade-offs — exponential time complexity due to redundant recomputation — is the primary motivation for studying optimization strategies. Memoization wraps the recursive function with a cache so that once fibonacci(k) is computed for any k, the result is stored and returned immediately on any subsequent call with the same argument. An iterative approach eliminates recursion entirely, computing the sequence from the bottom up using a simple loop with two variables. Both strategies reduce the time complexity to O(n) and the space complexity to O(1) for the iterative version.

Tracing a Small Fibonacci Example by Hand

Walking through fibonacci(4) step by step is one of the clearest ways to build an intuition for how two-branch recursion works and how results bubble back up through the call stack.

Start by calling fibonacci(4). Since 4 is neither 0 nor 1, the function cannot return immediately. It must first evaluate fibonacci(3) and then fibonacci(2), and finally sum those results. So fibonacci(4) is pushed onto the call stack and pauses, waiting.

fibonacci(4) is called → needs fibonacci(3) + fibonacci(2)
  fibonacci(3) is called → needs fibonacci(2) + fibonacci(1)
    fibonacci(2) is called → needs fibonacci(1) + fibonacci(0)
      fibonacci(1) is called → BASE CASE → returns 1
      fibonacci(0) is called → BASE CASE → returns 0
    fibonacci(2) returns 1 + 0 = 1
    fibonacci(1) is called → BASE CASE → returns 1
  fibonacci(3) returns 1 + 1 = 2
  fibonacci(2) is called → needs fibonacci(1) + fibonacci(0)
    fibonacci(1) is called → BASE CASE → returns 1
    fibonacci(0) is called → BASE CASE → returns 0
  fibonacci(2) returns 1 + 0 = 1
fibonacci(4) returns 2 + 1 = 3

Let's count the calls made: fibonacci(4) once, fibonacci(3) once, fibonacci(2) twice, fibonacci(1) three times, fibonacci(0) twice — a total of 9 function invocations just to compute the 4th Fibonacci number. Already the redundancy is visible: fibonacci(2) is computed independently twice, and fibonacci(1) is computed three separate times.

The final answer bubbles up as follows. The deepest base cases return first, passing their values 1 and 0 back up to their parent fibonacci(2) frame, which sums them to get 1. That 1 travels up to fibonacci(3), which also receives a 1 from its fibonacci(1) base case, summing to 2. Meanwhile, the second independent call to fibonacci(2) goes through the same base-case resolution and returns 1. Finally, fibonacci(4) receives its two resolved children — 2 from fibonacci(3) and 1 from fibonacci(2) — and returns their sum: 3.

This trace confirms that fibonacci(4) = 3, which matches the sequence: 0, 1, 1, 2, 3. The exercise also vividly illustrates the key mechanics of two-branch recursion: calls expand outward and downward building up a tree of pending frames, base cases resolve first, and then results cascade back upward through each waiting frame until the original call finally obtains the values it needed and can complete.