Recursion (Fibonacci) Algorithm Tutorial

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 $F_0 = 0$ and $F_1 = 1$. The recursive case uses the formula $F_n = F_{n-1} + F_{n-2}$.

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 $n = 30$, you'll make over $2$ million function calls. For $n = 50$, 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: $O(2^n)$ because each call branches into $2$ more calls.

Space complexity: $O(n)$ for the recursion call stack depth.