Learn
Recursion Basics
Recursion is a programming technique where a function calls itself to solve smaller instances of the same problem. You need two parts: a base case that stops recursion, and a recursive case that breaks the problem down.
For Fibonacci, your base cases are and . The recursive case uses the formula .
text
function fib(n):
if n == 0:
return 0
if n == 1:
return 1
return fib(n - 1) + fib(n - 2)
If you use this naive approach, you'll recalculate the same values repeatedly. For , you'll make over million function calls. For , your code won't finish in time.
Applications: You use recursion for tree traversals, divide-and-conquer algorithms, backtracking, and parsing nested structures.
Time complexity: because each call branches into more calls.
Space complexity: for the recursion call stack depth.