What you will learn
How a program is laid out in memory across heap, stack, static, and code segments
How a stack frame stores arguments, locals, the return value, and the return address
The three building blocks of every recursion: structure, base case, and recursive relation
Head and tail recursion as distinct templates, with passing by value versus reference
Multiple recursion: branch into k calls and derive O(k^N) time from the recursion tree
Multidimensional recursion: state as n dimensions with O(k^(n·N)) complexity
Why this course
Tracing recursion in your head is how most people first try to understand it, and it stops working four levels deep. The frames pile up faster than the brain can hold them, the deeper calls produce values that never connect back to the original problem, and the only thing left is hoping the base case happens to be right. Replacing the trace with a model of what the call stack actually does in memory is what makes recursion clickable.
This course replaces tracing with a model. You start with how memory is partitioned across heap, stack, static, and code segments, watch stack frames push and pop in LIFO order, then build recursion as the natural consequence of a function calling itself. After that you work through the four patterns (head, tail, multiple, and multidimensional) that account for almost every recursive interview problem.
Requirements
The course assumes you can write basic code in one mainstream language. No prior data structures experience is required.
- Comfort with functions, loops, and conditionals in at least one language.
- Familiarity with basic Big-O notation (O(N), O(log N), O(2^N)).
- A willingness to think about what a function call costs in memory, not only in syntax.
Overview
Recursion is a function that solves a problem by calling itself on a smaller version of the same problem. It is the only natural way to express problems whose structure repeats at smaller scales: factorials, Fibonacci, tree traversals, divide-and-conquer sorts, every backtracking puzzle, almost every dynamic-programming recurrence. The same code mechanism (a function calling itself) compiles down to repeated call and ret instructions, and the same memory mechanism (a fixed-size stack region) bounds how deep that recursion can go. Recursion is not a trick. It is the shape of an entire family of algorithms.
Representation of recursion
The course covers both halves of the problem: how the call stack runs a recursive function in memory, and how to recognise which of the four standard recursion patterns a given problem fits into.
Fundamentals
The course opens with the memory model. A running process is divided into four regions: a code segment holding compiled instructions, a static segment for globals, a heap that grows on demand, and a stack that holds one frame per active function call. Each call pushes a stack frame containing the stack pointer, frame pointer, local variables, arguments, return value, and return address. When a function returns, its frame is popped and execution resumes at the return address inside the caller's frame. The course traces this for compiled languages (C, C++) and for interpreted ones (Python, JavaScript), so you can see what happens under both the compilation pipeline and the tokenise / parse / bytecode-execute pipeline that an interpreter follows.
From there the course builds nested function calls. You see why the topmost frame is always the function currently executing, why a stack overflow happens when call depth or huge local arrays exhaust the fixed stack region the OS allocates per process, and why these failures are not always obvious from reading the source. By the time the recursion section begins, the call stack is no longer a black box.
Recursion itself is introduced through the ATM queue example. A person at the back of the queue asks the person ahead what position they hold, adds one, and returns it. The first person already knows their position is one. That single story contains every component the course later names: a recursive structure (each person asks the one ahead), a base case (the first person), and a recursive relation (position = ahead.position + 1). From there you implement the same idea as a self-calling function, learn when to pass arguments by value versus reference, and draw the recursion tree that every later pattern analysis depends on.
Problem solving
After the fundamentals come the patterns. Almost every recursive problem you will see in an interview fits one of four templates, and identifying which template a problem fits is the actual work. Once you have done that, the implementation writes itself from the template.
k recursive calls and aggregate their results, producing the O(k^N) time complexity that a recursion tree makes obvious. Fibonacci Number, Zigzag Sequence, Climb Stairs, Catalan Number.n dimension values, explore allowed shifts to multiple base cases, and derive O(k^(n·N)) complexity from the multidimensional recursion tree. Binomial Coefficient, Lattice Paths, Ackermann Function, Egg Dropping.Each pattern is taught in three layers. First an Understanding lesson walks the technique through a problem where the pattern is obvious. Then an Identifying lesson teaches you the signals (the shape of the recursive equation, the number of branches, the dimensionality of the state) that tell you a new problem fits the template. Then four problems give you progressively harder applications. The course finishes on multidimensional recursion through Egg Dropping, the classic puzzle that sets up the two-dimensional recurrence you will meet again in the dynamic-programming course.
How this course is different
Most recursion material on the internet either skips the call stack or skips the patterns. This course closes both gaps.
Who this course is for
The course suits anyone who needs to write recursive code with confidence rather than guess at base cases.
- New programmers who can write loops but freeze the moment a function calls itself.
- Self-taught and bootcamp graduates who can solve recursive problems they have seen before but cannot derive a recursion from a problem they have not.
- Working developers who use recursion through library code (tree walks, JSON traversal) but cannot reason about the call depth a function will reach on real input.
- Engineers preparing for FAANG and Big Tech interviews, where recursion sits underneath every tree, graph, backtracking, and dynamic programming question.
- Returning engineers who learned recursion in university through factorial and Fibonacci and want a refresher that names the patterns properly.
- Anyone who can write a recursive function but cannot explain why its base case is correct.
Continue your DSA journey
Recursion is the prerequisite for half of the curriculum. After this course, the natural next steps depend on which family of problems you want to tackle.
- Singly linked list: Linked-list problems are a clean playground for head and tail recursion. Reversing a list, finding the kth-from-last node, and merging two sorted lists all collapse into one of the templates in this course.
- Binary tree: A binary tree traversal is multiple recursion on the children of each node. Once head, tail, and multiple recursion click, recursive preorder, inorder, and postorder traversal stop feeling memorised and become consequences of where the work sits relative to the recursive calls.
- Graph: Depth-first search on a graph is recursion with a visited set. The cycle-detection and topological-sort algorithms in the graph course rely on exactly the head and tail recursion templates taught here, with one extra piece of bookkeeping for already-visited nodes.
- Backtracking: Backtracking is recursion plus an unmark-on-exit step. Every backtracking problem (permutations, combinations, N-queens, sudoku) is a multiple-recursion problem whose state is mutated before each branch and restored after. The four templates in this course transfer directly, with one additional mechanic.
- Dynamic programming: Every DP problem starts life as a recursive recurrence. Memoisation is multiple or multidimensional recursion with a cache; tabulation is the same recurrence unrolled. The recursion trees you learn to draw in this course are the diagrams you optimise in the DP course.
Frequently asked questions
N depends on the answer for one or more smaller subproblems. Tree traversal, divide and conquer, backtracking, and most DP recurrences fit this shape and are natural to express recursively. Use iteration when the problem walks a sequence in a single direction without nested sub-results, like counting, summing, or in-place reversal. The deciding question is whether the algorithm needs the language runtime to track state across multiple unresolved subproblems for you. If yes, recursion is the right tool. If not, a loop is simpler and avoids stack overhead.