The answer
Although it makes O(2^N) total calls, the maximum depth of the tree at any one time is N. Therefore, the space complexity is O(N).
Space Complexity of the Call Stack in Recursion
What is the space complexity of a naive recursive Fibonacci?
More FAQs in Space Complexity of the Call Stack in Recursion
Yes, every recursive function call allocates memory on the system's Call Stack to store local variables and return addresses.
The space complexity is equal to the maximum depth of the recursion tree at any given time.
A loop executes within a single function frame, continuously reusing the same O(1) memory space for its variables, avoiding the Call Stack buildup entirely.
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.