Delving into Algorithm Analysis - Deducing the Mathematical Representation of a Determined Study Case (III) [Recursive Algorithms and Recursive Relations]

We have seen previously how could represent an iterative algorithm as a mathematical function.
But how are we going to do so for recursive algorithms?
Let's take a look at the renowned recursive algorithm below:

void hanoiTowers(int n, char left, char center, char right) {
     if (n == 0) {     // Base Case
          return;
     } else {          // General Case
           hanoiTowers(n - 1, left, right, center);
           printf("\nDisk: %d from %c to %c", n, left, center);
           hanoiTowers(n - 1, right, center, left);
     }
}

We notice that there are two unconditional recursive calls inside the hanoiTowers() routine.

I invite you to attempt to execute the following algorithm, once with n = 10 and once with n = 30:

void hanoiTowers(int n) {
     if (n == 0) {     // Base Case
          return;
     } else {          // General Case
           hanoiTowers(n - 1);
           hanoiTowers(n - 1);
     }
}

When n = 10, this algorithm executed in a few milliseconds, but when n = 30, it took 12 seconds. (intel Core i5 - 4 Threads, 6 GB memory).

Actually, the conventional technique (recursive relations) to solve this is like the following:

Where c is constant representing the running time it takes to execute the printf() statements.

We will assume that a = 1, and c = 1

Thus, this algorithm running time is non polynomial (very expensive algorithm).

Now, it is known how to infer "mathematical representation" of both recursive and iterative algorithms, let's dig into time complexity a little bit, in the next posts.