Recursion is a programming technique where a function solves a problem by calling itself on smaller inputs. Students need this cheat sheet to recognize when recursion is useful, how recursive calls are organized, and how to prevent infinite loops. Recursive thinking is especially important for tree structures because each subtree has the same structure as the full tree.
This reference connects recursion rules, call stacks, and tree algorithms in one place.
Key Facts
- Every recursive function needs at least one base case that stops the recursion and returns a direct answer.
- Every recursive case must make progress toward a base case, usually by calling the function with a smaller input.
- A simple recursive pattern is if base case then return answer, else return recursive result on smaller input.
- The call stack stores unfinished function calls, and each recursive call adds a new stack frame until a base case is reached.
- The factorial recurrence is factorial(n) = 1 if n = 0, otherwise factorial(n) = n * factorial(n - 1).
- The Fibonacci recurrence is fib(n) = n if n <= 1, otherwise fib(n) = fib(n - 1) + fib(n - 2).
- A binary tree node usually stores value, left child, and right child, where each child is either another node or null.
- Common binary tree traversals are preorder root-left-right, inorder left-root-right, and postorder left-right-root.
Vocabulary
- Recursion
- Recursion is a method where a function solves a problem by calling itself on smaller or simpler versions of the same problem.
- Base Case
- A base case is a condition that returns an answer without making another recursive call.
- Recursive Case
- A recursive case is the part of a function that calls the same function again with a changed input.
- Call Stack
- The call stack is the memory structure that keeps track of active function calls and their local data.
- Tree
- A tree is a hierarchical data structure made of nodes connected by edges, with one root node and zero or more child nodes.
- Traversal
- A traversal is a systematic process for visiting every node in a tree in a specific order.
Common Mistakes to Avoid
- Missing the base case is wrong because the function can keep calling itself until the program crashes with a stack overflow.
- Making the recursive input larger or unchanged is wrong because the recursion does not move toward a stopping condition.
- Returning the recursive call without combining results is wrong when the problem requires accumulation, such as sum(root) = root.value + sum(left) + sum(right).
- Confusing traversal orders is wrong because preorder, inorder, and postorder visit the root at different times and produce different outputs.
- Assuming recursion is always efficient is wrong because some recursive algorithms, such as naive Fibonacci, repeat the same work many times.
Practice Questions
- 1 Trace factorial(5) using factorial(n) = 1 if n = 0, otherwise n * factorial(n - 1). What value is returned?
- 2 For a binary tree with root A, left child B, right child C, and B having children D and E, list the preorder traversal.
- 3 How many times is fib called in the full recursion tree for fib(4), using fib(n) = fib(n - 1) + fib(n - 2) with base cases fib(0) and fib(1)?
- 4 Explain why a binary tree is considered a recursive data structure and how that affects the design of traversal algorithms.
Understanding Recursion and Recursive Tree Structures
A recursive program has two phases that students should keep separate in their minds. First, calls move downward into smaller pieces of the problem. Then results move upward as each waiting call finishes its own work.
For example, a function that adds the numbers from one through four does not get its final answer immediately. It waits for the smaller call to return, then adds its own number. This return phase explains why recursive code can seem mysterious when read quickly.
Trace it line by line. Write down each call in order, then cross them off as they return. This makes the hidden flow visible.
The call stack is more than a technical detail. Each stack frame keeps a call's local variables and its place in the program. A frame remains in memory while it waits for a deeper call.
If a function keeps calling itself without reaching a stopping point, frames keep building until the program runs out of stack space. This produces a stack overflow error. Deep recursion can cause the same problem even when the logic is correct.
A tree shaped like a long chain may require one call per node. In such cases, an iterative solution using an explicit stack can be safer.
Trees are a natural fit because a node can be treated as the root of a smaller tree. This idea helps with tasks beyond printing values. A recursive function can count nodes, find the largest value, calculate a tree's height, or test whether two trees have the same shape.
The order of work changes the meaning of the result. Inorder traversal of a binary search tree lists values in sorted order because smaller values are stored on the left and larger values on the right.
Postorder traversal is useful when a parent depends on information from its children. For instance, a program can calculate the size of folders inside a directory before calculating the total size of the folder that contains them.
Not every recursive solution is efficient. The basic Fibonacci method repeats the same calculations many times. To find a later Fibonacci number, it recomputes earlier values through many different paths.
Memoization fixes this by saving a result the first time it is found and reusing it later. Tree algorithms often avoid this particular waste because separate subtrees do not overlap, but their running time still depends on tree shape. Visiting every node takes time proportional to the number of nodes.
Finding a value in a balanced binary search tree takes far fewer steps on average than in a one sided tree. When learning recursion, test the smallest inputs first, draw small trees, and state exactly what each function returns for one node. Clear return values make recursive code much easier to build and debug.