Fibonacci Series

The Fibonacci series is a sequence of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. Mathematically, it is defined as:

• $F(0) = 0$
• $F(1) = 1$
• For $n \geq 2$, $F(n) = F(n-1) + F(n-2)$

Recursive Approach

A naive recursive approach to calculate the $n^{th}$ Fibonacci number can be very inefficient because it involves a lot of repeated calculations. For example, to calculate $F(5)$, the function would calculate $F(4)$ and $F(3)$, but to calculate $F(4)$, it would again calculate $F(3)$ and $F(2)$, and so on. This results in an exponential time complexity of $O(2^n)$.The recursive approach is straightforward but inefficient due to repeated calculations.

def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

Dynamic Programming Approaches

Top-Down Approach (Memoization)

Memoization is a technique that involves storing the results of expensive function calls and returning the cached result when the same inputs occur again.

def fibonacci_memo(n, memo={}):
	if n in memo:
	    return memo[n]
	if n <= 1:
	    return n
	memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
	return memo[n]

Bottom-Up Approach (Tabulation)

Tabulation is the iterative counterpart of memoization where results are built iteratively from the base cases up to the final desired result.

def fibonacci_tabulation(n):
	if n <= 1:
	    return n
	fib_table = [0] * (n+1)
	fib_table[1] = 1
	for i in range(2, n+1):
	    fib_table[i] = fib_table[i-1] + fib_table[i-2]
	return fib_table[n]

Comparing Performance

The table below summarizes the time complexities of the different approaches to calculating the Fibonacci sequence.

Method	Time Complexity	Space Complexity
Recursive	$O(2^n)$	$O(n)$
Memoization (Top-Down)	$O(n)$	$O(n)$
Tabulation (Bottom-Up)	$O(n)$	$O(n)$

Optimal Space Optimization

An even more space-efficient approach is to use two variables to store the last two Fibonacci numbers and update them as we iterate through to $n$.

def fibonacci_optimized(n):
    a, b = 0, 1
    for i in range(2, n+1):
        a, b = b, a + b
    return b if n else a

This method reduces the space complexity to $O(1)$ while maintaining the $O(n)$ time complexity.

Conclusion

Dynamic programming provides efficient solutions for computing Fibonacci numbers, especially when compared to the naive recursive method. Depending on the requirements, you can choose between memoization for simplicity, tabulation for an iterative approach, or the optimized method for minimal space usage.