Discrete Mathematics For AIML - Chapter 5 Recursion & Recurrence Relations

Chapter 5 — Recursion & Recurrence Relations

This chapter explores recursion, recurrence relations, and divide-and-conquer algorithms, which are essential for algorithm design and efficiency analysis in AI & ML.

5.1 Recursive Definitions

Recursion is a method where a function calls itself to solve smaller instances of a problem. AI/ML Context: Recursive structures appear in tree traversal, dynamic programming, and recursive neural networks.

# Factorial example in Python
def factorial(n):
    if n == 0:
        return 1
    return n * factorial(n-1)

print(factorial(5))  # Output: 120

5.2 Recurrence Relations

A recurrence relation expresses a sequence in terms of previous terms.

Example: Fibonacci numbers: F(n) = F(n-1) + F(n-2), with F(0)=0, F(1)=1
Can be solved iteratively, recursively, or using closed-form formulas.

# Fibonacci using recursion
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(6))  # Output: 8

5.3 Divide & Conquer Algorithms

Divide and conquer splits problems into subproblems, solves them independently, and combines results.

Examples: Merge Sort, Quick Sort, Binary Search
AI/ML Context: Efficient data preprocessing, recursive feature aggregation, tree-based algorithms.

# Merge Sort Example
def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

print(merge_sort([5,2,9,1,5,6]))

5.4 Solving Recurrence Relations

Substitution method: Guess solution and prove using induction.
Iteration method: Expand recurrence to find a pattern.
Master theorem: Used to analyze divide-and-conquer algorithms like Merge Sort.

AI/ML Context: Helps predict runtime and efficiency of recursive ML algorithms, e.g., tree traversal, dynamic programming, and RNN computations.

5.5 Practical Python Applications

# Dynamic Programming Example: Fibonacci with memoization
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]

print(fibonacci_memo(50))

5.6 Why Recursion & Recurrence Relations Matter in AI/ML

Enable recursive neural networks (tree-structured data, NLP).
Dynamic programming for optimization problems (e.g., sequence alignment, shortest paths).
Analyzing algorithm efficiency and complexity for large datasets.

5.7 Exercises

Implement factorial and Fibonacci recursively and iteratively, compare runtime.
Implement Merge Sort and Quick Sort on sample datasets.
Formulate a recurrence relation for a binary search and solve it.

Hints / Solutions

Use memoization to optimize recursive solutions.
Divide-and-conquer helps in reducing runtime complexity from O(n²) to O(n log n).
Binary search recurrence: T(n) = T(n/2) + O(1), solved as O(log n).

5.8 Further Reading & Videos

"Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein — Recursion & Divide and Conquer chapters
Python recursive programming tutorials on YouTube (Corey Schafer)
Dynamic Programming and Recursion — GeeksforGeeks
Recursive Neural Networks — research papers for NLP and hierarchical models

Next Chapter: Boolean Algebra & Logic Circuits — representing logical functions, simplification, and their use in AI & ML systems.

IndianTechnoEra