The Central Idea
A recursive rule often replaces one problem with one or more smaller problems of the same type.
A recursion tree records this expansion.
The original problem appears at the root:
\[ P(n). \]If solving \(P(n)\) requires solving two smaller problems
\[ P(n-1) \quad\text{and}\quad P(n-2), \]then those become two children of the root.
What the Tree Represents
A recursion tree is not merely a decorative diagram.
Each node represents one recursive instance.
Each edge represents a recursive dependency.
Each level records another stage of recursive expansion.
Each leaf represents an instance where recursion stops.
The Root
The root is the starting problem.
For a recurrence such as
\[ T(n)=T(n-1)+T(n-2)+1, \]the root corresponds to
\[ \boxed{T(n)}. \]Expanding the recurrence reveals the recursive children.
Children and Branches
The recurrence
\[ T(n)=T(n-1)+T(n-2)+1 \]creates two recursive children:
\[ T(n-1) \]and
\[ T(n-2). \]The two outgoing edges form two branches from the root.
Leaves
A leaf is a node that is not expanded further.
Leaves usually correspond to base cases.
For example, if recursion stops when
\[ n=0 \quad\text{or}\quad n=1, \]then nodes labeled \(T(0)\) and \(T(1)\) are leaves.
Base Cases Stop the Tree
Without base cases, a recursive definition may continue expanding indefinitely.
A complete recursive process therefore combines:
- one or more recursive rules;
- one or more stopping conditions.
In a recursion tree, the stopping conditions determine where branches end.
A One-Branch Recursion Tree
Consider
\[ T(n)=T(n-1)+1 \]with base case \(T(0)\).
The recursive structure is a chain:
\[ T(n) \to T(n-1) \to T(n-2) \to \cdots \to T(0). \]A recursion tree does not need to branch into several children. A chain is the simplest tree-shaped recursion.
Depth of a One-Branch Recursion
In
\[ T(n)=T(n-1)+1, \]the argument decreases by \(1\) at each step.
Starting at \(n\), the recursion reaches \(0\) after \(n\) reductions.
Therefore, the tree has depth proportional to
\[ \boxed{n}. \]Binary Branching
A recurrence can produce two recursive children at each node.
For example,
\[ T(n)=2T(n-1)+1 \]can be interpreted as two recursive calls of size \(n-1\), plus one unit of local work.
Each internal node therefore has two children until a base case is reached.
Levels
The root is usually called level \(0\).
Its children are level \(1\).
Their children are level \(2\), and so on.
Grouping nodes by level helps us measure how recursive work accumulates.
Example: Number of Nodes per Level
Suppose every internal node creates exactly two children.
Then the number of nodes by level is
\[ 1,\ 2,\ 4,\ 8,\ldots \]Level \(k\) contains
\[ \boxed{2^k} \]nodes, as long as every branch is still active.
Total Nodes in a Complete Binary Tree
If a complete binary recursion tree has levels
\[ 0,1,\ldots,h, \]then the total number of nodes is
\[ 1+2+4+\cdots+2^h. \]This geometric sum is
\[ \boxed{2^{h+1}-1}. \]Recursive tree structure therefore connects directly with sequence sums.
Work at a Node
A recurrence often contains work performed in addition to the recursive calls.
For example,
\[ T(n)=2T(n-1)+3. \]The term
\[ 3 \]represents local work at the current node.
A recursion tree can attach this local cost to every node.
Work by Level
Suppose every node performs one unit of local work and level \(k\) has \(2^k\) nodes.
Then level \(k\) contributes
\[ \boxed{2^k} \]units of work.
Summing level costs gives the total work represented by the tree.
Recursion Trees as Recurrence Expansions
Consider
\[ T(n)=2T(n-1)+1. \]Expand one level:
\[ T(n) = 2[2T(n-2)+1]+1. \]Therefore,
\[ T(n)=4T(n-2)+3. \]The coefficient \(4\) corresponds to four recursive nodes two levels below the root.
Expand Another Level
Continuing,
\[ T(n) = 4[2T(n-3)+1]+3. \]Thus,
\[ T(n)=8T(n-3)+7. \]The coefficients
\[ 1,\ 2,\ 4,\ 8 \]match the number of active recursive nodes across successive levels.
Fibonacci Recursion Tree
A naive recursive evaluation of Fibonacci numbers follows
\[ F_n=F_{n-1}+F_{n-2}. \]The root \(F_n\) branches into
\[ F_{n-1} \]and
\[ F_{n-2}. \]Each of those may branch again until a base case is reached.
Example: Expand \(F_5\)
The first level is
\[ F_5 \to F_4,\ F_3. \]Expand again:
\[ F_4 \to F_3,\ F_2, \] \[ F_3 \to F_2,\ F_1. \]Notice that \(F_3\) and \(F_2\) can occur more than once in the tree.
Repeated Subproblems
A recursion tree can reveal that the same subproblem is solved repeatedly.
In naive Fibonacci recursion, the value
\[ F_3 \]may be recomputed in several branches.
This duplication is not obvious from a short recurrence formula, but it is immediately visible in the tree.
Why Repeated Subproblems Matter
Recomputing identical subproblems increases the total amount of work.
If a recursive process repeatedly reaches the same state, it may be more efficient to store the result and reuse it.
This idea leads to memoization and dynamic programming, though those algorithmic methods are beyond the main scope of this lesson.
Tree versus Directed Acyclic Graph
A recursion tree treats repeated calls as separate nodes, even if they refer to the same subproblem.
If identical subproblems are merged into one shared node, the structure is no longer necessarily a tree.
It may instead become a directed acyclic graph.
This distinction explains why memoized computation can have a much smaller dependency structure than naive recursion.
Divide-and-Conquer Recursion
Another common pattern divides a problem into smaller pieces.
For example,
\[ T(n)=2T\left(\frac n2\right)+n. \]Each problem of size \(n\) creates two subproblems of size \(n/2\), while the current node performs \(n\) units of additional work.
First Levels of a Divide-and-Conquer Tree
At level \(0\), there is one problem of size
\[ n. \]At level \(1\), there are two problems of size
\[ \frac n2. \]At level \(2\), there are four problems of size
\[ \frac n4. \]The number of nodes grows while the size of each subproblem shrinks.
Work per Level in a Balanced Example
For
\[ T(n)=2T\left(\frac n2\right)+n, \]level \(0\) contributes
\[ n. \]Level \(1\) has two nodes, each contributing \(n/2\):
\[ 2\cdot\frac n2=n. \]Level \(2\) has four nodes, each contributing \(n/4\):
\[ 4\cdot\frac n4=n. \]Thus, the nonrecursive work is constant across levels in this example.
Tree Height in Halving Recurrences
Suppose problem size is repeatedly halved:
\[ n,\ \frac n2,\ \frac n4,\ \frac n8,\ldots. \]After \(h\) halvings, the size is
\[ \frac{n}{2^h}. \]Reaching size \(1\) requires
\[ \frac{n}{2^h}=1. \]Therefore,
\[ 2^h=n. \]So the height grows logarithmically with \(n\).
Balanced versus Unbalanced Trees
A recursion tree is balanced when branches have similar depths and subproblem sizes.
It is unbalanced when some branches shrink or terminate much faster than others.
Fibonacci recursion is naturally unbalanced because one branch uses
\[ n-1 \]while the other uses
\[ n-2. \]Unequal Subproblem Sizes
Consider
\[ T(n)=T(n-1)+T\left(\frac n2\right)+1. \]One branch decreases slowly, while the other shrinks quickly.
The resulting recursion tree has branches with very different shapes and depths.
A recursion tree helps us see that asymmetry directly.
Branching Factor
The branching factor is the number of recursive children created by a node.
For
\[ T(n)=3T(n-1)+1, \]each internal node creates three recursive children.
If the branching continues uniformly, level \(k\) contains
\[ \boxed{3^k} \]nodes.
General Uniform Branching
If every internal node creates \(b\) children, then the number of nodes at level \(k\) is
\[ \boxed{b^k}. \]The total number of nodes through level \(h\) is
\[ 1+b+b^2+\cdots+b^h. \]When \(b\neq1\), this geometric sum is
\[ \boxed{ \frac{b^{h+1}-1}{b-1} }. \]Leaf Count in a Complete \(b\)-ary Tree
If every branch reaches the same depth \(h\), then the bottom level contains
\[ \boxed{b^h} \]leaves.
Leaf counts often correspond to the number of base-case calls made by a recursive process.
Local Work versus Recursive Work
In a recurrence such as
\[ T(n)=2T(n/2)+n, \]there are two conceptually different sources of work:
- recursive work contained in the child calls;
- local work \(n\) performed at the current node.
A recursion tree separates these contributions visually.
Accumulating Cost across the Tree
To estimate total recursive work, we can:
- determine the cost at each node;
- sum node costs across each level;
- sum the level costs across the full depth;
- include leaf costs.
This level-by-level accumulation turns a recursive equation into a sequence of simpler sums.
Recursion Trees and Geometric Sums
Uniform branching often creates geometric level counts.
For example,
\[ 1,\ 2,\ 4,\ 8,\ldots \]or
\[ 1,\ 3,\ 9,\ 27,\ldots. \]Therefore, recursion trees naturally connect recursive algorithms with geometric sequences and finite geometric sums.
Recursion Trees and Arithmetic Level Costs
Not every level cost is geometric.
Some recurrences produce level costs such as
\[ n,\ n-1,\ n-2,\ldots \]or other arithmetic patterns.
The tree helps identify the relevant sequence before summing it.
Recursion Tree for a Simple Sum Recurrence
Consider
\[ S(n)=S(n-1)+n \]with
\[ S(0)=0. \]Expanding gives
\[ S(n) = n+(n-1)+(n-2)+\cdots+1. \]Therefore,
\[ \boxed{ S(n)=\frac{n(n+1)}{2} }. \]The Tree Can Reveal a Closed Form
The recurrence
\[ S(n)=S(n-1)+n \]produces a one-branch recursion tree whose node costs are
\[ n,\ n-1,\ n-2,\ldots,1. \]Summing those costs yields the closed form
\[ \frac{n(n+1)}{2}. \]Thus, recursion trees can connect recursive definitions to explicit sums and closed forms.
Recursion Trees and Counting
A recursive counting argument can also be represented as a tree.
Each branch represents a choice or case.
Leaves represent completed objects or terminal configurations.
Counting leaves may therefore count the number of recursively generated possibilities.
Example: Binary Choices
Suppose a process makes one of two choices at each of \(n\) stages.
The recursion tree has branching factor \(2\) and depth \(n\).
Therefore, the number of leaves is
\[ \boxed{2^n}. \]This is the same count obtained from the multiplication principle.
Example: Three Choices per Stage
If each stage has three independent choices and there are \(n\) stages, then the recursion tree has
\[ 3^n \]leaves.
Again, tree structure and the fundamental counting principle agree.
Recursion Trees and Decision Trees
Recursion trees and decision trees are closely related but emphasize different ideas.
A decision tree usually represents choices.
A recursion tree usually represents recursive subproblems or calls.
In some problems, the same tree can be interpreted both ways.
Recursion Trees and State Transitions
A state-transition trajectory usually follows one next state at each step.
A recursion tree may branch into several subproblems from one state.
Therefore, a trajectory describes one path through time, while a recursion tree can describe many simultaneously required recursive branches.
Paths through a Recursion Tree
A root-to-leaf path records one chain of recursive descent.
The path length measures how many recursive transitions occurred before a base case was reached.
Different paths may have different lengths in an unbalanced recursion tree.
Maximum Depth
The maximum depth is the length of the longest root-to-leaf path.
It describes the deepest chain of recursive dependence.
In a one-branch recurrence such as
\[ T(n)=T(n-1)+1, \]the maximum depth is approximately \(n\).
Minimum Depth
In an unbalanced tree, some branches may terminate earlier.
The minimum depth is the shortest root-to-leaf path.
Comparing minimum and maximum depth helps describe how balanced or unbalanced the recursion is.
Base-Case Thresholds
A recursive process may stop not only at \(n=0\), but whenever
\[ n\le c \]for some threshold \(c\).
Changing the threshold changes the bottom of the recursion tree but usually does not change the basic branching structure above it.
Tree Expansion Need Not Be Infinite
A recursive definition may look self-referential, but if each branch moves toward a base case, the recursion tree is finite for a fixed input.
The key requirement is progress toward termination.
Recursive Rules That Fail to Shrink
Consider a rule such as
\[ T(n)=T(n+1)+1. \]If no other mechanism stops the process, the argument moves away from a smaller base case.
The corresponding recursion tree does not naturally terminate.
Recursive definitions must be designed so that branches eventually reach a stopping condition.
Recursion Trees as Proof Organizers
A recursion tree can help organize inductive or recursive reasoning.
If every node satisfies a property provided its children do, then the tree structure suggests a bottom-up proof from leaves to root.
This viewpoint connects recursion trees with structural induction.
Bottom-Up Evaluation
Although a recursion tree is often expanded top-down, values can be evaluated bottom-up.
First evaluate the base-case leaves.
Then combine them to evaluate their parents.
Continue upward until the root value is determined.
Top-Down Expansion versus Bottom-Up Evaluation
Top-down expansion answers:
"What subproblems does this problem depend on?"
Bottom-up evaluation answers:
"Once smaller results are known, how do they combine to produce the larger result?"
Both perspectives describe the same recursive structure.
Common Error: Confusing Tree Nodes with Sequence Terms
A recursion tree node represents a recursive instance or call.
The same sequence term or subproblem may appear at several distinct nodes.
Therefore, the number of tree nodes is not generally the number of distinct sequence values.
Common Error: Forgetting Base Cases
A recursion tree must stop at leaves.
If the base cases are omitted, the expansion can appear to continue forever even when the intended recursive definition should terminate.
Common Error: Counting Only Leaves
In some analyses, internal nodes also perform work.
Counting leaves alone can therefore underestimate the total recursive work.
Always identify whether cost is attached to leaves, internal nodes, or both.
Common Error: Assuming Every Level Has the Same Number of Nodes
Uniform branching creates predictable level sizes.
But unbalanced recurrences may terminate some branches early.
In those cases, later levels may contain fewer active nodes than a complete tree formula predicts.
Common Error: Multiplying Branching Factor without Checking Depth
A branching factor of \(2\) does not automatically mean there are \(2^n\) leaves.
The number of leaves depends on both the branching structure and how many levels each branch survives.
Common Error: Treating Repeated Subproblems as Distinct Mathematical Values
In a naive Fibonacci recursion tree, several nodes may ask for the same value \(F_k\).
These are separate calls but not distinct mathematical subproblems.
Recognizing this distinction is essential when comparing naive recursion with stored-result methods.
Common Error: Assuming a Recursion Tree Is Always Balanced
A recurrence such as
\[ T(n)=T(n-1)+T(n-2)+1 \]produces branches that shrink at different rates.
Treating the tree as perfectly balanced can distort level counts and depth estimates.
A Reliable Procedure for Drawing a Recursion Tree
- Write the original recursive instance at the root.
- Apply the recurrence once to identify its children.
- Repeat the expansion for non-base-case children.
- Stop branches at base cases.
- Label levels consistently.
- Record local work at each node when relevant.
- Look for repeated subproblems or regular branching patterns.
A Reliable Procedure for Level Analysis
- Count the number of active nodes at level \(k\).
- Determine the size of each subproblem at that level.
- Determine local work per node.
- Multiply node count by local work when costs are uniform.
- Sum across levels.
- Add leaf costs if necessary.
A Reliable Procedure for Detecting Repeated Subproblems
- Label every node by its recursive argument or state.
- Compare labels across branches.
- Mark identical subproblem labels.
- Distinguish repeated calls from distinct mathematical subproblems.
- Consider whether stored results could eliminate recomputation.
A Reliable Procedure for Tree-Based Counting
- Identify what each branch represents.
- Determine the branching factor at each stage.
- Determine the stopping depth or base cases.
- Count leaves when each leaf represents one completed outcome.
- Check whether different paths can represent the same outcome.
Practice 1: One-Branch Tree
Consider
\[ T(n)=T(n-1)+1, \]with base case \(T(0)\).
How many recursive reductions occur before reaching the base case?
Practice 2: Binary Level Counts
A complete recursion tree has branching factor \(2\).
How many nodes are on levels \(0,1,2,3,4\)?
Practice 3: Complete Binary Tree Total
A complete binary recursion tree has levels \(0\) through \(5\).
How many total nodes does it contain?
Practice 4: Three-Way Branching
Every internal node creates three children, and all branches reach depth \(4\).
How many leaves are there?
Practice 5: Fibonacci Repetition
Expand the first two levels of a naive recursion tree for \(F_5\) using
\[ F_n=F_{n-1}+F_{n-2}. \]Identify one repeated subproblem.
Practice 6: Balanced Halving Tree
Consider
\[ T(n)=2T(n/2)+n. \]What is the total nonrecursive work on level \(2\)?
Practice 7: Tree Height
A recursive process repeatedly halves its input until the input reaches \(1\).
If \(n=32\), how many halvings are required?
Practice 8: Sum Recurrence
Expand
\[ S(n)=S(n-1)+n \]down to the base case \(S(0)=0\), and write the resulting finite sum.
Practice 9: Translated Counting Tree
A process makes one of two choices at each of \(6\) independent stages.
How many leaves are in the complete decision/recursion tree?
Practice 10: Repeated Subproblems
Why can a recursion tree contain more nodes than there are distinct subproblems?
Practice Answers
Practice 1
The argument decreases
\[ n,\ n-1,\ n-2,\ldots,0. \]Therefore, there are
\[ \boxed{n} \]recursive reductions before reaching \(T(0)\).
Practice 2
A complete binary tree has \(2^k\) nodes on level \(k\).
\[ \boxed{1,\ 2,\ 4,\ 8,\ 16}. \]Practice 3
Total nodes:
\[ 1+2+4+8+16+32. \]Therefore,
\[ \boxed{63}. \]Practice 4
A complete three-way tree has
\[ 3^4 \]leaves at depth \(4\).
\[ \boxed{81}. \]Practice 5
First level:
\[ F_5\to F_4,\ F_3. \]Second level:
\[ F_4\to F_3,\ F_2, \] \[ F_3\to F_2,\ F_1. \]Repeated subproblems include
\[ \boxed{F_3} \]and
\[ \boxed{F_2}. \]Practice 6
Level \(2\) has four subproblems of size
\[ \frac n4. \]Therefore, total local work is
\[ 4\cdot\frac n4=n. \]Hence,
\[ \boxed{n}. \]Practice 7
Solve
\[ \frac{32}{2^h}=1. \]Since
\[ 32=2^5, \]we have
\[ \boxed{h=5}. \]Practice 8
Repeated expansion gives
\[ S(n) = n+(n-1)+(n-2)+\cdots+1+S(0). \]Since \(S(0)=0\),
\[ \boxed{ S(n)=1+2+\cdots+n }. \]Practice 9
Two choices at each of six stages gives
\[ 2^6. \]Therefore,
\[ \boxed{64} \]leaves.
Practice 10
A recursion tree records every recursive call separately.
The same mathematical subproblem may be reached along several different branches, so identical subproblem labels can appear at multiple nodes.
Therefore, node count measures calls, not necessarily distinct subproblems.
What to Remember
A recursion tree makes recursive dependence visible.
- The root is the original recursive problem.
- Children represent recursive subproblems.
- Leaves represent stopping or base cases.
- Levels represent successive stages of recursive expansion.
- Branching factor controls how the number of active nodes can grow.
- Tree depth measures the longest chain of recursive descent.
- Level costs can be summed to estimate accumulated work.
- Repeated subproblems appear as repeated node labels in different branches.
- Balanced and unbalanced recurrences produce different tree shapes.
- Recursion trees connect naturally with geometric sums, counting, closed forms, and state dependence.
- Top-down expansion and bottom-up evaluation are complementary views of the same recursive structure.
Where We Go Next
Recursion trees reveal how recursive structure expands into branches, subproblems, and leaves. Many important sequences also have direct combinatorial meanings: their terms count objects, paths, tilings, arrangements, or other discrete structures.
The next lesson, Combinatorial Interpretations of Sequences, connects sequence values with counting problems and shows how recurrences can arise naturally by decomposing collections of discrete objects into cases.