Algorithms
Recursion Fundamentals
Difficulty: Beginner
The mathematical definition factorial(n) = n factorial(n - 1) defines a function in terms of itself, with factorial(0) = 1 as the stopping point. That two-line definition is also a complete program if your language lets a function call...
Recursion Fundamentals
The mathematical definition factorial(n) = n * factorial(n - 1) defines a function in terms of itself, with factorial(0) = 1 as the stopping point. That two-line definition is also a complete program if your language lets a function call itself. Recursion is what turns self-referential definitions into runnable code, and many problems (tree traversal, graph search, divide and conquer, dynamic programming) describe themselves most naturally that way.
Recursion Fundamentals breaks down how that machinery actually works. You will learn to identify a base case (when the recursion stops) and a recursive case (how the problem reduces to a smaller instance), trace the call stack as frames are pushed and popped, and reason about return values flowing back up the chain. Examples run through factorial, naive Fibonacci, sum of an array, and integer power, plus a first look at recursion-tree intuition, tail recursion, stack overflow, and the O(depth) space cost of deep recursion.
In How to Read Code (JS & Python), you saw functions call other functions. Debugging by Tracing taught you to follow those calls step by step. Recursion is the case where the function on the call stack is the same function, again and again, with smaller inputs each time.
Next, Backtracking (Intro) extends recursion with an explicit undo step to systematically explore combinatorial search spaces.
Topics:
What You'll Learn
By the end of this lesson, you will be able to:
Explain what recursion is and identify the base case and recursive case in a recursive function.
Implement classic recursive algorithms: factorial, Fibonacci, and sum of array.
Trace the call stack during recursive execution, showing frame creation and return value propagation.
Explain why every recursive function needs a base case and what happens without one (stack overflow).
Analyze the time and space complexity of recursive functions, including the O(depth) call stack space.
Compare recursion with iteration and explain when each approach is more natural.
Why This Matters
01
Recursion is the foundation for tree traversals, graph algorithms, dynamic programming, divide and conquer, and backtracking.
02
Many data structures (trees, linked lists, graphs) are inherently recursive — a tree is a node with subtrees, each of which is a tree.
03
Recursion teaches you to think in terms of subproblems, which is the core skill for solving complex algorithmic challenges.
04
Interview problems frequently require recursive thinking, even when the optimal solution uses iteration or memoization.
Key Terms
8 terms you'll encounter in this lesson
Recursion
A technique where a function solves a problem by calling itself on a smaller input, reducing the problem until it reaches a base case.
Base case
The simplest case that the function can answer directly without recursion. It stops the recursive calls from continuing indefinitely.
Recursive case
The case where the function calls itself with a smaller or simpler input, making progress toward the base case.
Call stack
A stack data structure maintained by the runtime that tracks active function calls. Each recursive call adds a frame; each return removes one.
Stack frame
A record on the call stack containing a function call's local variables, parameters, and return address. Created on call, destroyed on return.
Stack overflow
An error that occurs when the call stack exceeds its maximum size, typically caused by infinite or excessively deep recursion.
Recursion tree
A visual representation of all recursive calls as a tree, where each node is a function call and children are the subcalls it makes.
Tail recursion
A form of recursion where the recursive call is the very last operation in the function. Some languages optimize tail calls to avoid stack growth.
Related Problems
Coding problems that put this lesson's concepts into practice
Heads Up
Common misconceptions to watch out for
"Recursion is always slower than iteration"
Recursion is not inherently slower. The algorithm matters, not the mechanism. A recursive binary search and an iterative binary search both take O(log n) time. However, recursion uses O(depth) extra stack space, and function call overhead can make it slower for very deep recursion.
"Forgetting the base case causes an infinite loop"
It causes a stack overflow, not an infinite loop. Each recursive call adds a frame to the call stack. Without a base case, calls keep stacking until memory runs out, crashing the program.
"Recursive functions always use exponential time"
The time complexity depends on the branching factor and depth. Factorial recursion is O(n), not exponential. Naive Fibonacci is O(2^n) because it branches twice at each level and recalculates overlapping subproblems — but with memoization it becomes O(n).