def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)Variables
n- value of the input integer (not array length)
Explanation
Two recursive calls per invocation with no memo grows the call tree to roughly 2ⁿ nodes - **O(2ⁿ)** time (more tightly Θ(φⁿ)). Despite the exponential call count, the recursion stack only goes `n` deep at any one time - **O(n)** space.