How does the video construct a recursion tree to analyze the recursive computation of $f(7)$?

Conditions

• The recurrence relation is $f(n) = f(n-1) + f(n-2)$.
• The base cases are $f(1) = 1$ and $f(2) = 1$.
• The target computation is $f(7)$.

Reasoning, step by step

1. Set the target computation $f(7)$ as the root node of the tree.
2. Apply the recursive formula to split $f(7)$ into two child nodes: $f(6)$ and $f(5)$.
3. Continue splitting each non-base-case node into two children (e.g., $f(6)$ splits into $f(5)$ and $f(4)$).
4. Repeat this process until all leaf nodes reach the base cases $f(1)$ or $f(2)$.
5. Observe the resulting inverted binary tree to see the full sequence of recursive calls.

Example

The instructor draws a recursion tree with $f(7)$ as the root node, branching downward to $f(6)$ and $f(5)$, then further decomposing $f(6)$ into $f(5)$ and $f(4)$, and so on, forming an inverted binary tree.

Common misconceptions

• Believing that the recursion tree only represents the top-down problem decomposition and ignores the bottom-up result aggregation.
• Assuming that the tree stops expanding at a fixed depth rather than stopping when the base cases $f(1)$ or $f(2)$ are reached.

Watch the explanation

Explore next

• Why is computing the Fibonacci sequence directly via recursion highly inefficient?
• How to analyze the time complexity of a recursive algorithm using a recursion tree?
• What pattern governs the number of nodes per level in the recursion tree?