Building Recurrence relations in plain readable English

In the next 4 minutes, I am gonna explain this complex topic in simple plain english. No mathematical jargons. I promise.

Parts:

1. Building Recurrence Relations in plain readable English (You are here)
2. Solving recurrence relations — In Simple Language

Formal definition for geniuses out there: (feel free to skip)

A recurrence relation is an equation that recursively defines a sequence where the next term is a function of the previous terms.

Confused? Let me explain:

It sounds esoteric. Infact, it is. But stick with me. I am sure you will understand in just 4 minutes.

Let’s say we have a sequence of numbers. Let’s say - the fibonacci sequence.

Let me write down the first 10 fibonacci numbers in the sequence:

1,1,2,3,5,8,13,21,34,55…

Now how can we calculate the 11th number in the fibonacci sequence? Well, the same way we calculated the 10th number in the sequence. Now how did we calculate the 10th number in the sequence? The same way we calculated the 9th number. Now how did we calculate the 9th number?

I’ll give you 10 seconds to guess.

Think… Can you guess?

The answer is…

** Drum rolls **

The same way we calculated the 8th number in the sequence.

We can go till we reach the very start of the sequence. Every i’th number in the sequence is calculated by simply adding the previous 2 numbers in the sequence i-1 and i-2.

fib(i) = fib(i-1) + fib(i-2)

• So every i'th value in the sequence can be recursively calculated by simply adding the (i-1)th and (i-2)th element.
• Which also means every i’th number in the sequence is related to (i-1)th and (i-2)th number in the sequence.
• Informally, every i’th number in the sequence forms a recurrence relation with the previous numbers.

How to build recurrence relations:

Now, I chose fibonacci sequence to explain the concept of recurrence relations coz almost everyone of us are aware of the fibonacci sequence. But lets slow down a little. Lets keep fibonacci aside for now and lets consider a simple recursive function that just prints number in reverse order from n to 0.

function printReverse(n) {
    if(n > 0) {
        console.log(n)
        printReverse(n-1)
    }
}

This is a simple javascript function that for a given value of n , prints every number from 0 to n in reverse order. If we call the function as printReverse(10), the output looks like:

10
9
8
7
6
5
4
3
2
1

• Lets assume printRev(n) requires T(n) time to execute.
• So how much does printRev(n-1) requires to execute? Naturally T(n-1) .
• So printRev(n-2) also requires T(n-2) time to execute. And so on. Let’s just stick to printRev(n-1) only for now.
• In the end when n=1 , printRev(1) will require T(1) time to execute.
• And when n=0, the function stops execution. Technically when n <= 0 , the function does nothing.

Let me re-write the function again with the assumed time each line requires to execute in comments:

function printReverse(n){ // If this requires T(n) time
    if(n > 0) {           // This line executes in constant time = 1
        console.log(n)    // This line executes in constant time = 1
        printReverse(n-1) // This line executes in T(n-1) time
    }
}

Therefore we can say that T(n)=summation of all the functions of times required by each line within the function.

Or simply put:

When n <= 0
    T(n) = 1 
When n > 0
    T(n) = 1 + 1 + T(n-1)
   .: T(n) = 2 + T(n-1)
   .: T(n) = T(n-1) + 2         ... 1

Now since 2 is a constant, we can represent it asymptotically as 1 in equation 1. Hence:

T(n) = 1            (for n <= 0) // This is our "base case"
T(n) = T(n-1) + 1   (for n > 0)

This is the recurrence relation formed by printRev function.

In simple words: These 2 equations mean, for every value of n , T(n) requires T(n-1) + 1 time to execute till n is more than 0 . Once n becomes equal to 0 , it means T(n) has reached its base case and requires only 1(constant) time to execute.

Lets derive the recurrence relation for fibonacci function:

This function generates the N’th fibonacci number:

function fibonacci(n) {  // If this requires T(n) time  
    if(n == 0 || n == 1) // This is a constant time operation = 1
        return 1  // This is a constant time operation = 1
    let i = fibonacci(n-1) // This requires T(n-1) time      
    let j = fibonacci(n-2) // This requires T(n-2) time
    return i+j // This is also a constant time operation = 1
}

Therefore we can say:

When n >= 0 && n <= 1:
    T(n) = 1 + 1
    Which can be asymptotically written as
    T(n) = 1
When n > 1:
    T(n) = 1 + T(n-1) + T(n-2) + 1
    .: T(n) = T(n-1) + T(n-2) + 2
    Which can be asymptotically written as:
    T(n) = T(n-1) + T(n-2) + 1

In Simple Words: T(n) requires T(n-1)+T(n-2)+1 time to execute till n is more than 1 . Once n is less than or equal to 1 , it meansT(n) has reached its base case and requires only 1(constant) time to execute.

Conclusion:

We read a complex definition of recurrence relations, and tried to understand it with a simple example. We built recurrence relations for 2 simple functions as well.

What’s Next?

Next, do check out next article on how we can analyze time complexity of recursive functions using recurrence relations using Backward Substitution.

Disclaimer:

This is just an attempt to make you understand recurrence relations in simple language. This article, by far, does not even scratch the surface of the topic. I urge you to dig deeper into the topic and learn more.