Some Random Notes

2. Fibonacci does not follow $f(g(n))$

5 min read

Should I use recursion there?

The standard Fibonacci sequence doesn’t just transition from to a single . Instead, a single input branches out into multiple sub-problems: Because one call splits into two separate branches, it forms a tree of execution rather than a simple straight line.

Should we use recursion for Fibonacci?

For naive recursion? No. If you write standard, straightforward recursion for Fibonacci, you should avoid it for anything other than very small numbers.

  • The Problem: It leads to massive **redundant calculations**. To compute , it calculates multiple times, and even more.
  • The Cost: The time complexity blows up exponentially to , meaning a modest input like will cause your program to freeze or crash due to millions of duplicate function calls.

Better Alternatives for Fibonacci

While naive recursion fails here, you still have two great ways to handle it:

  • 1. Recursion with Memoization (Top-Down Dynamic Programming): You can keep the recursive structure if you store the results of each in a cache (like an array or hash map) the first time you calculate it. If the function is called again for the same , it instantly returns the cached answer instead of recomputing. This brings the time complexity down to a fast .
  • 2. Iteration (Bottom-Up Approach): Most programmers prefer an iterative loop for Fibonacci. You simply start from and and loop upward to , keeping track of only the last two numbers. This takes time and uses constant space without risking stack overflow.

Explosion

Question

If Fibonacci is exploding so fast, why do we use recursion with graph and trees ? Won’t similar explosion occur in these cases too

Computational recurrence relations** (like Fibonacci) differ from structural data traversals (like trees and graphs).

Answer

Trees don’t explode because every node has a unique path, but general graphs do explode unless you explicitly protect them

Why Trees Don’t Explode ( Time)

In a tree, even though a node branches out into multiple children (e.g., a binary tree splits left and right), those children are distinct, physical objects in memory.

  • No Convergence: A tree is strictly hierarchical. Once a branch splits, those sub-branches never merge back together. There is one, and only one, unique path from the root to any given node.
  • Work = Number of Nodes: If a tree has nodes, a recursive traversal visits each node exactly once. The time complexity is linear: .
  • No Overlapping Subproblems: The left child of Node A is a completely separate entity from the left child of Node B. They don’t share underlying states.

Why Graphs Actually Do Explode

Unlike trees, graphs do have convergence and cycles. Multiple paths can lead to the exact same node, and nodes can point back to their parents. If you write naive recursion (like a basic Depth-First Search) on a general graph without keeping track of where you’ve been, it will explode or trigger an infinite loop. To prevent this, graph algorithms must use a visited set (or state tracking):

def dfs(node, visited):
    if node in visited:
        return
    visited.add(node)
    for neighbor in node.neighbors:
        dfs(neighbor, visited) # Prevents explosion and infinite loops

Without that visited check, a graph with cycles will infinitely circle around, blowing up the stack just like naive Fibonacci.

Why Fibonacci is Special (The Root Cause of the Explosion)

Fibonacci feels like a function call tree, but mathematically, its input is just a 1D integer ().

  • In Fibonacci, when calls and , the branch also calls .
  • The breakdown: Different branches of the execution are redundantly computing the exact same integer state. This means Fibonacci is actually a Directed Acyclic Graph (DAG) of dependencies masquerading as a tree. Because multiple execution paths converge on the exact same sub-problem (), it explodes exponentially.

Summary

  • Trees: Branch out, but never merge. Every node is unique No explosion ().
  • Graphs: Branch out and merge/cycle. They will explode unless you track visited nodes Explosion managed by state tracking.
  • Fibonacci: Branches out and repeatedly hits the exact same integer state. It explodes because it lacks a “visited/memoized” cache.

When to Use vs. Avoid Recursion in Coding Exercises

Recursion is a powerful mental model for breaking down problems that exhibit self-similarity (e.g., trees, graphs, divide-and-conquer algorithms). However, in production systems and performance-critical coding exercises, its utility depends heavily on the execution environment and memory constraints.

When to Use Recursion

  • Hierarchical Data Structures: Processing Trees, Tries, Graphs, or JSON documents where nodes branch naturally.
  • Divide and Conquer: Algorithms like Merge Sort, Quick Sort, or Binary Search where the problem space is halved at each step, yielding stack depth.
  • Backtracking & Combinatorics: Generating permutations, combinations, or solving pathfinding mazes where maintaining explicit state stacks manually becomes overly complex.

When to Avoid Recursion

  • Linear Iteration / String Manipulation: As seen with the palindrome problem, if a problem can be solved with a simple linear scan or two pointers, recursion introduces unnecessary overhead.
  • Heavy Memory Overhead ( Space): Every recursive call pushes a new frame onto the call stack, storing return addresses, parameters, and local variables. Deep recursions risk a StackOverflowError.
  • Language Limitations (Java): Java does not natively optimize tail recursion (Tail Call Optimization / TCO). Even if a recursive call is the absolute last statement in a method, Java allocates a new stack frame every time, compounding performance penalties.
  • String Allocation Traps: Combining recursion with immutable object creation (like Java’s String.substring()) changes time complexity from to due to repeated heap allocations and character copying.

Backlinks