The answer
Because every function call spawns exactly two more function calls, causing the total number of operations to double at every level of depth.
Understanding the Recursion Tree Method
Why is the naive Fibonacci sequence O(2^N)?
More FAQs in Understanding the Recursion Tree Method
A Recursion Tree is a visual diagram where each node represents a function call, and the branches represent the subsequent recursive calls made from that function.
You sum up the amount of non-recursive work done across all nodes at every level of the tree.
You use Dynamic Programming (Memoization). By caching the result of a node, you prevent the tree from recalculating overlapping branches, collapsing O(2^N) into O(N).
Still have questions?
Browse all our FAQs or reach out to our support team
Want to upskill yourself?
Your learning library
Small steps. Big possibilities.
Find your next course. Build something great.