Recurrence Relation

A recurrence relation defines a function by its value at a particular input in terms of its values at smaller inputs.

Recurrence relations are used to describe recursive functions. The relation defines each term in a sequence in terms of the preceding terms.

For example, the Fibonacci sequence can be defined as:

F(n) = F(n-1) + F(n-2)

This relates F(n) to the two preceding terms F(n-1) and F(n-2).

Recurrence relations are useful for analyzing recursive algorithms, proving correctness and calculating time complexity.

Solution

Here is an implementation of Fibonacci using a recurrence relation:

Java

1
2
3
4
int fibonacci(int n) {
  if (n <= 1) return n;
  return fibonacci(n-1) + fibonacci(n-2); 
}

C++

1
2
3
4
int fibonacci(int n) {
  if (n <= 1) return n;  
  return fibonacci(n-1) + fibonacci(n-2);
}

Python

1
2
3
4
5
def fibonacci(n):
  if n <= 1:
    return n

  return fibonacci(n-1) + fibonacci(n-2)

This defines F(n) in terms of F(n-1) and F(n-2), recursively calling itself on smaller inputs.

Recurrence relations define the core logic of recursive functions concisely.

Description: Recurrence Relation

A recurrence relation is an equation that uses recursion to define a sequence based on its preceding terms. The sequence can be numbers, functions, or any other objects. The classic example is the Fibonacci sequence, defined by ( F(n) = F(n-1) + F(n-2) ) with base cases ( F(0) = 0 ) and ( F(1) = 1 ).

Solution:

We will implement code to solve the Fibonacci sequence using two methods: the naive recursive approach and a more optimized dynamic programming approach.

Java

Naive Recursive Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
public class RecurrenceRelation {
    public static int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // Output: 55
    }
}

Dynamic Programming Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
public class RecurrenceRelation {
    public static int fibonacci(int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        
        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }

        return dp[n];
    }

    public static void main(String[] args) {
        System.out.println(fibonacci(10));  // Output: 55
    }
}

C++

Naive Recursive Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

int main() {
    cout << fibonacci(10) << endl;  // Output: 55
}

Dynamic Programming Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <vector>
using namespace std;

int fibonacci(int n) {
    vector<int> dp(n + 1, 0);
    dp[0] = 0;
    dp[1] = 1;
    
    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    
    return dp[n];
}

int main() {
    cout << fibonacci(10) << endl;  // Output: 55
}

Python

Naive Recursive Approach

1
2
3
4
5
6
def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(10))  # Output: 55

Dynamic Programming Approach

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def fibonacci(n):
    dp = [0] * (n + 1)
    dp[0] = 0
    dp[1] = 1

    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]

print(fibonacci(10))  # Output: 55

Key Takeaways

Recurrence relations define elements based on previous elements in a sequence.
The naive recursive approach can be very inefficient for large inputs.
Using dynamic programming, we can optimize the solution to be more efficient.
The core logic remains similar across Java, C++, and Python, differing primarily in syntax.