15% off all plans & roadmaps Use code
See plansOpening your learning path
Progress is saved as you study.
The recursion tree method draws every call of a recursive function as a node and every recursive call as an edge from parent to child. Count all the nodes to get time. Measure the longest root-to-leaf path to get stack space. For naive fib(n) that gives O(2^n) time and O(n) auxiliary space.
| Node | One function call |
|---|---|
| Leaf | A base-case call |
| fib(4) tree | 9 nodes, deepest active path of 4 calls |
| Time (naive fib) | O(2^n), from T(n) <= 2T(n - 1) + O(1) |
| Auxiliary space | O(n), siblings are not active at the same time |
Assume you can identify:
We will analyze the naive Fibonacci definition for a nonnegative integer n:
fib(0) = 0fib(1) = 1n > 1, fib(n) = fib(n - 1) + fib(n - 2)A recursion tree shows the calls created by one initial call.
The input contract is: n is a nonnegative integer. Therefore, fib(-1) is outside this function's stated contract.
For analysis conventions used here:
Use exactly this call:
1fib(4)Start with the definition:
1fib(4) = fib(3) + fib(2)The root call creates two child calls:
1fib(4)
2├── fib(3)
3└── fib(2)Expand fib(3):
1fib(3) = fib(2) + fib(1)The tree becomes:
1fib(4)
2├── fib(3)
3│ ├── fib(2)
4│ └── fib(1)
5└── fib(2)The two fib(2) nodes are:
fib(3);fib(4).They have the same argument, but they are separate calls. Naive recursion computes both independently.
A recursion tree grows as calls go down, then values return upward.
Start at the root.
| Step | Current call | Action | Calls created or result |
|---|---|---|---|
| 1 | fib(4) | 4 > 1, so use the recursive case | create fib(3) and fib(2) |
| 2 | fib(3) | 3 > 1, so use the recursive case | create fib(2) and fib(1) |
| 3 | left fib(2) | 2 > 1, so use the recursive case | create fib(1) and fib(0) |
| 4 | fib(1) | base case | return 1 |
| 5 | fib(0) | base case | return 0 |
| 6 | fib(1) under fib(3) | base case | return 1 |
| 7 | right fib(2) | 2 > 1, so use the recursive case | create fib(1) and fib(0) |
| 8 | fib(1) | base case | return 1 |
| 9 | fib(0) | base case | return 0 |
The complete tree, including leaf values:
fib(4) expands into nine calls: leaves return 1 and 0, fib(2) = 1, fib(3) = 2, then fib(4) = 3. The two fib(2) nodes are separate calls that repeat the same work.
There are nine nodes. Therefore, fib(4) creates nine function calls in this tree.
Resolve each non-base call from its child results.
The left fib(2) receives 1 from fib(1) and 0 from fib(0).
1fib(2) = 1 + 0 = 1fib(3) now has:
1fib(3) = fib(2) + fib(1)
2 = 1 + 1
3 = 2The right fib(2) is a separate call. It again receives 1 and 0.
1fib(2) = 1 + 0 = 1Finally, the root receives the two child results.
1fib(4) = fib(3) + fib(2)
2 = 2 + 1
3 = 3The final return value is:
1fib(4) = 3The two fib(2) nodes both return 1, but each one performs its own calls to fib(1) and fib(0). The tree shows that repeated work.
At every point in the recursion tree, each node stands for one specific function call.
For example, a node labeled fib(2) represents a call that must eventually return the second Fibonacci value, 1.
The following remains true throughout the tree:
Each node
fib(k)represents one call whose returned value must equal the k-th Fibonacci value; fork > 1, its two child calls arefib(k - 1)andfib(k - 2).
fib(0) leaf returns 0.fib(1) leaf returns 1.fib(k) for k > 1 has exactly two children:
fib(k - 1)fib(k - 2)Both child arguments are nonnegative and smaller than k:
1k - 1 < k
2k - 2 < kFor k > 1, both are also at least 0. Recursive calls move toward a base case.
Do not confuse two different measurements:
For fib(4), the tree has nine nodes, but one deepest active path has four calls:
1fib(4) → fib(3) → fib(2) → fib(1)Those are different quantities.
Start with the required base values.
1If n is 0, return 0.
2If n is 1, return 1.For every larger valid input, apply the recurrence exactly:
1fib(n) = fib(n - 1) + fib(n - 2)The resulting decision structure is:
1If n is a base-case input:
2 return its known value
3Otherwise:
4 compute fib(n - 1)
5 compute fib(n - 2)
6 add the two returned values
7 return the sumThe order matters.
For fib(2), the recursive case must be:
1fib(2) = fib(1) + fib(0)
2 = 1 + 0
3 = 1The recursive case requires both calls.
Input: n, a nonnegative integer.
Return value: the n-th Fibonacci value under fib(0) = 0 and fib(1) = 1.
Mutation behavior: does not modify n or any external data.
Boundary behavior: n = 0 returns 0; n = 1 returns 1. Negative inputs are outside the stated contract.
Helper contracts: none.
11. function fib(n):
22. if n == 0:
33. return 0
44. if n == 1:
55. return 1
66.
77. leftValue = fib(n - 1)
88. rightValue = fib(n - 2)
99. return leftValue + rightValueLines 2 through 5 handle the leaves of the recursion tree.
Lines 7 and 8 create the two child calls for every non-base node.
Trace fib(4) line by line.
leftValue = fib(3)| Call | Lines checked or executed | Result |
|---|---|---|
fib(4) | line 2: false; line 4: false; line 7 | call fib(3) |
fib(3) | line 2: false; line 4: false; line 7 | call fib(2) |
left fib(2) | line 2: false; line 4: false; line 7 | call fib(1) |
fib(1) | line 2: false; line 4: true; line 5 | return 1 |
left fib(2) | line 7 completes | leftValue = 1 |
left fib(2) | line 8 | call fib(0) |
fib(0) | line 2: true; line 3 | return 0 |
left fib(2) | line 8 completes | rightValue = 0 |
left fib(2) | line 9 | return 1 + 0 = 1 |
fib(3) | line 7 completes | leftValue = 1 |
Now fib(3) continues.
| Call | Lines checked or executed | Result |
|---|---|---|
fib(3) | line 8 | call fib(1) |
fib(1) | line 2: false; line 4: true; line 5 | return 1 |
fib(3) | line 8 completes | rightValue = 1 |
fib(3) | line 9 | return 1 + 1 = 2 |
fib(4) | line 7 completes | leftValue = 2 |
rightValue = fib(2)fib(4) now executes line 8. It is a new, separate fib(2) call.
| Call | Lines checked or executed | Result |
|---|---|---|
fib(4) | line 8 | call right fib(2) |
right fib(2) | line 2: false; line 4: false; line 7 | call fib(1) |
fib(1) | line 2: false; line 4: true; line 5 | return 1 |
right fib(2) | line 7 completes | leftValue = 1 |
right fib(2) | line 8 | call fib(0) |
fib(0) | line 2: true; line 3 | return 0 |
right fib(2) | line 8 completes | rightValue = 0 |
right fib(2) | line 9 | return 1 + 0 = 1 |
fib(4) | line 8 completes | rightValue = 1 |
fib(4) | line 9 | return 2 + 1 = 3 |
The final result is:
1fib(4) returns 3Use a structural argument over the recursive calls.
For n = 0, line 2 is true and line 3 returns 0. The result matches fib(0) = 0.
For n = 1, line 4 is true and line 5 returns 1. The result matches fib(1) = 1.
Every leaf node in the recursion tree returns the correct Fibonacci value.
Assume that calls on smaller nonnegative inputs return their correct Fibonacci values.
Consider a call fib(n) where n > 1.
fib(n - 1).fib(n - 2).Both arguments are nonnegative and smaller than n. By the assumption, those calls return the correct values:
1fib(n - 1)
2fib(n - 2)Line 9 returns their sum:
1fib(n - 1) + fib(n - 2)The sum is exactly the stated Fibonacci definition for fib(n). Therefore, fib(n) returns the correct value.
Each recursive call receives a smaller argument:
1n - 1 or n - 2Starting from a nonnegative integer, repeated decreases eventually reach 1 or 0. Those base cases return without further calls.
For every nonnegative integer input, the algorithm terminates and returns the correct Fibonacci value.
For n > 1, one call to fib(n) performs:
fib(n - 1);fib(n - 2).Let T(n) represent the work for fib(n).
Since both child inputs are at most n - 1, use this upper bound:
1T(n) <= 2T(n - 1) + O(1)Unfold it:
1T(n) <= 2T(n - 1) + O(1)
2
3 <= 2(2T(n - 2) + O(1)) + O(1)
4 = 4T(n - 2) + O(1) + O(1) + O(1)
5
6 <= 2^n T(0) + a constant amount of work at up to 2^n call positionsThe total work is bounded by a constant times 2^n:
1Time: O(2^n)The tree for fib(4) shows why depth alone cannot measure time. It has calls at multiple positions on the same level, including two separate fib(2) calls.
A standard recursive execution evaluates one branch, returns, then evaluates the sibling branch.
For example, while moving down the left side of fib(4), one active path is:
1fib(4) → fib(3) → fib(2) → fib(1)The path has four simultaneously active calls before fib(1) returns.
The entire recursion tree has nine nodes, but all nine calls are not active at once. After one child returns, its stack frame is removed before the sibling call completes.
Along a deepest path, the argument decreases from n toward 0 or 1. At most a linear number of frames are active:
1Auxiliary call-stack space: O(n)fib(2) only one recursive callIncorrect assumption:
1fib(2) does not need both fib(1) and fib(0)Smallest exposing input:
1fib(2)Wrong outcome:
fib(0) gives 0.2.The required result is:
1fib(2) = fib(1) + fib(0)
2 = 1 + 0
3 = 1Correction: for every n > 1, make both calls:
1leftValue = fib(n - 1)
2rightValue = fib(n - 2)
3return leftValue + rightValueIncorrect lines:
1if n == 0:
2 return 1
3if n == 1:
4 return 1Smallest exposing input:
1fib(2)Wrong computation:
1fib(2) = fib(1) + fib(0)
2 = 1 + 1
3 = 2But the required value is 1.
Correction:
1fib(0) = 0
2fib(1) = 1O(n) timeIncorrect reasoning:
1The deepest path has O(n) calls, so the time is O(n).Exposing input:
1fib(4)Wrong analysis: it ignores multiple calls at the same depths. The fib(4) tree has two distinct fib(2) nodes and nine total calls.
Correction: time counts every node created in the recursion tree. Bound the total number of calls:
1O(2^n) timeO(2^n) auxiliary space because the tree has many nodesIncorrect reasoning:
1The tree has exponentially many nodes, so all those calls use stack space at once.Exposing input:
1fib(4)Wrong analysis: sibling calls are not simultaneously active in a standard depth-first execution. One subtree returns before its sibling subtree finishes.
Correction: follow the longest active root-to-leaf path:
1fib(4) → fib(3) → fib(2) → fib(1)The longest path gives:
1O(n) auxiliary call-stack space| Input | Required result or status |
|---|---|
fib(0) | returns 0 |
fib(1) | returns 1 |
fib(2) | returns 1 |
fib(4) | returns 3 |
fib(-1) | outside the nonnegative-integer contract |
Implement naive recursive fib(n) for a nonnegative integer n.
The executable tests will verify this contract:
1fib(0) == 0
2fib(1) == 1
3fib(2) == 1
4fib(4) == 3
5fib(6) == 8No mapped executable problem is supplied for this lesson.
1calls = 0
2
3def fib(n):
4 global calls
5 calls += 1 # one call = one node in the tree
6 if n == 0:
7 return 0
8 if n == 1:
9 return 1
10 left_value = fib(n - 1)
11 right_value = fib(n - 2)
12 return left_value + right_value
13
14result = fib(4)
15print(result, calls)1public class Main {
2 static int calls = 0;
3
4 static int fib(int n) {
5 calls++; // one call = one node in the tree
6 if (n == 0) return 0;
7 if (n == 1) return 1;
8 int leftValue = fib(n - 1);
9 int rightValue = fib(n - 2);
10 return leftValue + rightValue;
11 }
12
13 public static void main(String[] args) {
14 int result = fib(4);
15 System.out.println(result + " " + calls);
16 }
17}1#include <iostream>
2using namespace std;
3
4int calls = 0;
5
6int fib(int n) {
7 calls++; // one call = one node in the tree
8 if (n == 0) return 0;
9 if (n == 1) return 1;
10 int leftValue = fib(n - 1);
11 int rightValue = fib(n - 2);
12 return leftValue + rightValue;
13}
14
15int main() {
16 int result = fib(4);
17 cout << result << " " << calls << endl;
18}1let calls = 0;
2
3function fib(n) {
4 calls++; // one call = one node in the tree
5 if (n === 0) return 0;
6 if (n === 1) return 1;
7 const leftValue = fib(n - 1);
8 const rightValue = fib(n - 2);
9 return leftValue + rightValue;
10}
11
12const result = fib(4);
13console.log(`${result} ${calls}`);Write the root call, then give each non-base call one child per recursive call it makes. For fib(4) the root has children fib(3) and fib(2). Stop at base-case leaves, here fib(1) and fib(0).
Write the recurrence, such as T(n) <= 2T(n - 1) + O(1), and unfold it level by level. Sum the work per level, then sum the levels. For this recurrence the level sizes double, which gives O(2^n).
Time counts every node, and fib(4) has 9 of them. Space counts only calls active at once. A finished child's frame is removed before its sibling runs, so only one root-to-leaf path is on the stack.
No, it is an upper bound. The exact growth is about 1.618^n, the golden ratio to the power n. Both are exponential, and the O(2^n) bound is the one the recurrence gives directly.
Count the calls and multiply by the constant work in each call. If each call also does extra work, such as merging in merge sort, add that work per level. Then compare the result with the stack depth for space.