ReviseAlgo Logo

Foundations

Recursion

Master the mental model of recursion—base cases, recursive calls, call stack execution, and tree traversal intuition.

Last Updated: July 31, 2026 • 25 min read

1. Introduction

What is Recursion?

Recursion is a programming technique where a method or function calls itself to solve a smaller sub-problem of the same problem.

Why is it Important?

Many complex data structures—such as Trees, Graphs, Tries, and Divide & Conquer algorithms (MergeSort, QuickSort)—are naturally recursive. Writing recursive solutions often breaks down complex multi-step logic into clean, concise code.

Where is it Used?

  • File Systems: Navigating nested directories and subfolders on your computer.
  • Web Browsers: Rendering nested HTML DOM elements (

    ... ).

  • JSON Parsing: Parsing nested JSON objects and arrays.

    • 2. Mental Model

    Imagine a Line of People in a Movie Theater.

    You are sitting in the back row (Person 4) and want to know your row number, but it's too dark to count. 1. You ask the person in front of you (Person 3): "What row are you in?" 2. Person 3 asks Person 2. Person 2 asks Person 1. 3. Person 1 is in the front row and knows immediately: "I am in Row 1!" (Base Case). 4. Person 1 tells Person 2: "I am in Row 1." 5. Person 2 adds 1: "I must be in Row 2!" and tells Person 3. 6. Eventually, Person 3 tells you: "I am in Row 3!" You add 1 and conclude: "I am in Row 4!"

    Recursion pushes questions down until someone knows the direct answer (Base Case), then passes results back up the chain!

    3. Concept: Anatomy of a Recursive Function

    Every valid recursive function must have two mandatory components:

    1. Base Case (The Stop Condition)

    The simplest possible condition that can be answered directly without further recursive calls.
  • Without a base case, recursion runs infinitely until the program crashes with a StackOverflowError.

    • 2. Recursive Step (The Progress Condition)

    The function calls itself with a smaller or simpler input, moving closer to the base case.

    Trace Example: Factorial of N (N!)

    Factorial of 3 (3! = 3 × 2 × 1 = 6):

    4. Visuals

    Call Stack Lifecycle for factorial(3)

    5. Real-World Examples

  • Folder Directory Traversal: To calculate total folder size, sum the file sizes in the current folder, then recursively call getFolderSize() on each subfolder.
  • Organization Chart: Finding all employees under a VP requires listing direct reports, then recursively listing direct reports of those managers.

    • 6. Interview Perspective

    How Interviewers Ask This Topic

    Interviewers use recursion to test tree traversals (DFS), combinations, and backtracking.

    Common Mistakes

    Warning: 1. Missing or Flawed Base Case: Forgetting n <= 1 leads to infinite recursion (factorial(-1), factorial(-2)) causing StackOverflowError.
    > 2. Not Making Progress: Calling solve(n) instead of solve(n - 1) will loop forever.
    > 3. Redundant Calculations: In plain recursive Fibonacci fib(n-1) + fib(n-2), the same values are recomputed millions of times, blowing up complexity to O(2ⁿ)!

    Important Interviewer Tips

  • Draw the Recursion Tree on the whiteboard before coding.
  • State both time complexity (number of nodes in the recursion tree) and space complexity (maximum depth of call stack).

    • 7. Summary

  • Recursion solves a problem by having a function call itself on smaller inputs.
  • Must contain a Base Case (when to stop) and a Recursive Step (making progress).
  • Uses Call Stack Memory equal to the maximum recursion depth.
  • Foundation for Trees, Graphs, Backtracking, and Dynamic Programming.

    • 8. Quiz

    Question 1: What happens if a recursive function does not have a base case? Answer: The function will call itself infinitely until call stack memory is exhausted, throwing a StackOverflowError crash.
    Question 2: What are the two mandatory components of every recursive algorithm? Answer: 1. Base Case (stop condition) and 2. Recursive Step (moving toward the base case with smaller input).
    Question 3: In a recursive function with depth N, what is the auxiliary space complexity? Answer: O(N) auxiliary space, because N stack frames are stored concurrently on the call stack at maximum depth.
    Question 4: What is the base case in a function that calculates the sum of numbers from N down to 1? Answer: When N <= 1 (or N == 0), return N (or 0) without making further recursive calls.
    Question 5: Why is plain recursive Fibonacci O(2ⁿ) time complexity? Answer: Because each function call spawns 2 additional recursive calls, forming a binary recursion tree of depth N with roughly 2ⁿ total call nodes.