Click image to open full size
Computer Science
Grade 11-12
Recursion and Recursive Tree Structures Cheat Sheet
A printable reference covering recursion, base cases, call stacks, tree traversal, and recursive tree algorithms for grades 11-12.
Related Tools
Related Labs
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.