Fibonacci Number Interview Question for Apple

## Fibonacci Numbers: Recursive and Iterative Solutions

The Fibonacci numbers are a classic example used in computer science to illustrate recursion and dynamic programming. Given `n`, we want to calculate `F(n)`. Let's explore a couple of approaches.

### 1. Naive Recursive Approach

The most straightforward implementation is a direct translation of the Fibonacci definition.

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

# Example Usage
n = 10
print(f"F({n}) = {fibonacci_recursive(n)}")  # Output: F(10) = 55

2. Optimal Iterative Approach

The recursive approach is simple but highly inefficient due to redundant calculations. A better solution is to use an iterative approach, building up the Fibonacci numbers from the base cases.

def fibonacci_iterative(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

# Example Usage
n = 10
print(f"F({n}) = {fibonacci_iterative(n)}")  # Output: F(10) = 55

3. Dynamic Programming (Memoization) Approach

Memoization is a top-down dynamic programming technique where we store the results of expensive function calls and reuse them when the same inputs occur again. This avoids redundant calculations.

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

# Example Usage
n = 10
print(f"F({n}) = {fibonacci_memoization(n)}") # Output: F(10) = 55

Big(O) Run-time Analysis:

Naive Recursive Approach: The time complexity is O(2^n) because each call to fibonacci_recursive(n) results in two more calls, forming a binary tree structure. Many of these calls are redundant, recalculating the same Fibonacci numbers multiple times.
Iterative Approach: The time complexity is O(n) because we iterate from 2 to n once to compute the Fibonacci number.
Memoization Approach: The time complexity is O(n) because we compute each Fibonacci number only once and store it in the memo dictionary. Subsequent calls for the same n take O(1) time.

Big(O) Space Usage Analysis:

Naive Recursive Approach: The space complexity is O(n) due to the call stack. In the worst case, the maximum depth of the recursion is n.
Iterative Approach: The space complexity is O(1) because we only use a fixed number of variables (a, b).
Memoization Approach: The space complexity is O(n) due to the memo dictionary storing computed Fibonacci numbers and also O(n) for the call stack.

Edge Cases:

n = 0: Both the recursive and iterative approaches correctly return 0.
n = 1: Both approaches correctly return 1.
Negative n: The Fibonacci sequence is not typically defined for negative numbers in this context. The code assumes non-negative n. If negative values were required, the definition would need to be extended (e.g., using F(-n) = (-1)^(n+1) * F(n)).
Large n: For very large n, the recursive approach will cause a stack overflow due to the excessive number of function calls. The iterative approach is much more robust for large n values and memoization can further optimize it.