Recurrence relation is an equation that recursively defines a sequence, where the next term is a function of the previous terms. Recurrence relations are commonly used to describe the runtime of recursive algorithms in computer science and to define sequences in mathematics.

What is a Recurrence Relation?

A Recurrence Relation defines a sequence where each term is given as a function of one or more of its preceding terms. Formally, a recurrence relation for a sequence ????????an​ is an equation that expresses an​ in terms of a_n−1​, a_n−2​,…, a_n−k​, where k is a fixed integer.

Understanding Recurrence Relations:

A general form of a recurrence relation can be written as:

• T(n) = a * T(n/b) + f(n)

Here:

• T(n) is the function we’re defining.
• a is the number of subproblems in the recurrence.
• n/b is the size of each subproblem.
• f(n) is the cost outside the recursive calls, often related to dividing the problem and combining the results.

Solving Recurrence Relations:

Solving a recurrence relation involves finding a closed-form or an iterative expression that does not depend on itself. Common techniques include:

1. Substitution Method: Guess the form of the solution and use mathematical induction to find constants.
2. Recurrence Trees: Visualize the recurrence relation as a tree and calculate the total work done at each level.
3. Master Theorem: Provides a direct way to solve recurrences of the form T(n) = a * T(n/b) + f(n).

Example Recurrence Relations:

1. Binary Search:
   • Recurrence: T(n) = T(n/2) + O(1)
   • Explanation: The problem size is halved at each step, and there is a constant time overhead for each division.
2. Merge Sort:
   • Recurrence: T(n) = 2T(n/2) + O(n)
   • Explanation: The problem is divided into two halves, each of size n/2, and merging the two halves takes linear time.

Implementing Recurrence Relations in Python:

To illustrate solving a recurrence relation, let’s implement a generic recursive algorithm with memoization. We’ll use the example of Merge Sort to show the recurrence relation in action.

1. Fibonacci Sequence in Python:

# recursuve function to find the nth fibonacci number
def fibonacci_recursive(n):
    if n <= 1:
        return n
    else:
        return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)


print(fibonacci_recursive(10))  # Output: 55

Complexity Analysis:

• Time Complexity: Since, each fibonacci_recursive(n) results in two function calls: fibonacci_recursive(n – 1) and fibonacci_recursive(n – 2), the recurrence relation for the number of calls is: T(n) = T(n – 1) + T(n – 2) + O(1). Solving the recurrence relation gives the time complexity as: O(2^n).
• Auxiliary Space: The depth of the recursion stack is n because the function recurses down by 1 each time until reaching the base case. Thus, the auxiliary space of the recursive Fibonacci function is O(n).

2. Factorial in Python:

# function to find factorial of n
def factorial_recursive(n):
    if n == 0:
        return 1
    else:
        return n * factorial_recursive(n - 1)

Complexity Analysis:

• Time Complexity: Since, each factorial_recursive(n) results in only one function call: factorial_recursive(n -1), the recurrence relation for the number of calls is: T(n) = T(n – 1) + O(1). Solving the recurrence relation gives the time complexity as: O(n).
• Auxiliary Space: The depth of the recursion stack is n because the function recurses down by 1 each time until reaching the base case. Thus, the auxiliary space of the recursive Fibonacci function is O(n).

Recurrence relations are a fundamental concept in computer science and mathematics. Understanding how to implement and solve them in Python allows for efficient problem-solving and algorithm analysis.