RECURSION
=========
Recursion is when a function calls itself to solve a smaller version of the same problem.
Every recursive function needs:
1. Base case — condition to stop recursion.
2. Recursive case — function calls itself with smaller input.

--- Factorial ---
n! = n * (n-1) * ... * 1

def factorial(n):
    if n == 0 or n == 1:   # base case
        return 1
    return n * factorial(n - 1)  # recursive case

print(factorial(5))   # 120
print(factorial(0))   # 1

# Iterative equivalent
def factorial_iter(n):
    result = 1
    for i in range(2, n + 1):
        result *= i
    return result

--- Fibonacci ---
fib(n) = fib(n-1) + fib(n-2), fib(0)=0, fib(1)=1

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

print([fib(i) for i in range(8)])  # [0, 1, 1, 2, 3, 5, 8, 13]

--- Sum of Array ---
def array_sum(arr):
    if not arr:
        return 0
    return arr[0] + array_sum(arr[1:])

print(array_sum([1, 2, 3, 4, 5]))  # 15

--- Power Function ---
def power(base, exp):
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half  # O(log n) — fast power
    return base * power(base, exp - 1)

print(power(2, 10))   # 1024
print(power(3, 5))    # 243

--- Reverse a String ---
def reverse_string(s):
    if len(s) <= 1:
        return s
    return reverse_string(s[1:]) + s[0]

print(reverse_string("hello"))  # "olleh"

--- Check Palindrome ---
def is_palindrome(s):
    if len(s) <= 1:
        return True
    if s[0] != s[-1]:
        return False
    return is_palindrome(s[1:-1])

print(is_palindrome("racecar"))  # True
print(is_palindrome("hello"))    # False

--- Tower of Hanoi ---
Move n disks from source to destination using auxiliary peg.
Minimum moves = 2^n - 1.

def hanoi(n, source, destination, auxiliary):
    if n == 1:
        print(f"Move disk 1 from {source} to {destination}")
        return
    hanoi(n-1, source, auxiliary, destination)
    print(f"Move disk {n} from {source} to {destination}")
    hanoi(n-1, auxiliary, destination, source)

hanoi(3, 'A', 'C', 'B')
# Moves disk 1 from A to C
# Moves disk 2 from A to B
# Moves disk 1 from C to B
# ... (7 total moves)

--- Binary Search (Recursive) ---
def binary_search(arr, target, low, high):
    if low > high:
        return -1
    mid = (low + high) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] < target:
        return binary_search(arr, target, mid + 1, high)
    else:
        return binary_search(arr, target, low, mid - 1)

arr = [1, 3, 5, 7, 9]
print(binary_search(arr, 7, 0, len(arr)-1))  # 3

--- Flatten Nested List ---
def flatten(lst):
    result = []
    for item in lst:
        if isinstance(item, list):
            result.extend(flatten(item))
        else:
            result.append(item)
    return result

print(flatten([1, [2, [3, 4], 5], 6]))  # [1, 2, 3, 4, 5, 6]

--- Generate All Subsets (Power Set) ---
def subsets(nums):
    if not nums:
        return [[]]
    rest = subsets(nums[1:])
    return rest + [[nums[0]] + s for s in rest]

print(subsets([1, 2, 3]))
# [[], [3], [2], [2,3], [1], [1,3], [1,2], [1,2,3]]

--- Generate Permutations ---
def permutations(nums):
    if len(nums) <= 1:
        return [nums]
    result = []
    for i, num in enumerate(nums):
        rest = nums[:i] + nums[i+1:]
        for perm in permutations(rest):
            result.append([num] + perm)
    return result

print(permutations([1, 2, 3]))
# [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

--- Recursion vs Iteration ---
Recursion: cleaner code, natural for tree/graph problems, risk of stack overflow.
Iteration: better performance, no stack overflow, sometimes harder to read.
Use recursion when the problem is naturally recursive (trees, divide-and-conquer).
Convert to iteration for very deep recursion using an explicit stack.