Recursive algorithms

Definition

Recursive algorithms are based on the mathematical concept of recursion, which is defined as the repetitive execution of a process or procedure.

If you still do not know what recursion is, click here and visit the article where we explain in detail about it.

As simply as possible, a recursive algorithm is an algorithm that has a recursive function in its body, a function that has a call to itself. See the code below for an example of a recursive function named func(). Note that on line 4 there is a very suspicious function call. This is a call to the func() function itself.

1.public void func(int n) {
2.    if(n==0) return;
3.    func(n-1);
4.}

Although not very meaningful (and even meaningless at first glance), this recursive calling mechanism is useful and very powerful for solving many computational problems.

So whenever you see an algorithm that has function calls to itself, you’ll know it’s a recursive algorithm.

Structure of a recursive algorithm

The big problem with recursive functions lies in their infinite execution flow. As the function calls itself, it ends up creating an endless call cycle. Notice in the image below the illustration of this problem.

For this reason, recursive functions have a structure composed of elements that allow you to control when these recursive calls are interrupted. These elements are:

• Base case – a conditional that allows you to define when the function will stop calling itself.
• Recursive Step – code of the algorithm that contains the recursive call(s).

To understand this structure, let’s look at an algorithm that calculates the sum of the first n natural numbers. For example, if you enter the value 6, the algorithm should answer 21, because 6+5+4+3+2+1 = 21.

See below the recursive implementation of the algorithm. The variable n (line 1) receives the value whose sum will be calculated. Note in lines 2 and that the base case is defined by a conditional, which imposes a stop condition on recursive calls. The rest of the function content (line 4) is the recursive step.

1.public int sum(int n) {
2.    if(n==1) // base case
3.            return 1;
4.    return n + sum(n-1); // recursive step
5.}

Recursive algorithm vs. iterative algorithm

For every recursive algorithm there is a corresponding iterative (non-recursive) algorithm that can solve the same problem. The term iterative refers to those algorithms that use repetition structures. Ex .: “for”, “while”, “do-while”.

To visualize the difference between recursive and iterative implementations, let’s look at the algorithm that calculates the Factorial. This algorithm calculates the product of the first n positive natural numbers. For example: if a value 5 is entered, the algorithm must answer “120”, because 5×4×3×2×1 = 120.

Below is the difference between the recursive and iterative implementations of the algorithm that calculates the factorial of a given n number.

1.public int fat(int n) {
2.    if(n==1) // base case
3.            return 1;
4.    return n * fat(n-1); // recursive step
5.}

1.public int fat(int n) {
2.    int fat = n;
3.    for(int i = 1; i < n; i++) {
4.            fat = fat*i;
5.    }
6.    return fat;
7.}

It can be seen that the main advantage of recursive algorithms over iteratives is the clarity and readability of the generated algorithm. Not that iteratives are messy, but because of their very nature and standardized structure, recursive algorithms end up providing a higher level of elegance for expressing solutions.

Let’s look at another example. This time with algorithm that calculates the nth term of the Fibonacci sequence.

If you still don’t know what is “the Fibonacci sequence” is, click here and go to the article about recursion. He has a session that talks about this sequence.

Notice in the code below how the iterative implementation of Fibonacci is quite large, but note that the recursive version remains simple and lean.

1.public int fib(int n) {
2.    if(n==1 || n==2) // base case
3.            return 1;
4.    return fib(n-1) + fib(n-2); // recursive step
5.}

1.public static int fib(int n){
2.    int F = 0; // current
3.    int pre = 0; // previous
4.    for (int i = 1; i <= n; i++) {
5.        if (i == 1) {
6.            F = 1;
7.            pre = 0;
8.        } else {
9.            F += pre ;
10.            pre = F - pre;
11.        }
12.    }
13.    return F;
14.}

The high memory consumption of recursive algorithms

Despite this aesthetic advantage, the recursive algorithms have a HUGE disadvantage (compared to iteratives algorithms) in the “use of computational resources” category.

Because each recursive call creates a new instance of the function, computational memory consumption can be devastating. A true time bomb if not used with caution.

The image below illustrates what happens in recursive calls to the algorithm that calculates the sum of the first n natural numbers (seen in the previous section). In this example we are illustrating the summation of the first 3 numbers. Note that each new call creates a new instance of the function and, consequently, new variables allocated in computer memory. That is, the amount of memory allocated is three times larger!

1.public int sum(int 3) {
2.    if(3==1)
3.        return 1;
4.    return n + sum(2);
5.}

1.public int sum(int 2) {
2.    if(2==1)
3.        return 1;
4.    return n + sum(1);
5.}

1.public int sum(int 1) {
2.    if(1==1)
3.        return 1;
4.    return n + sum(0);
5.}

Thus, the amount of memory consumed by executing a recursive algorithm is directly proportional to the amount of repetitions. If in the algorithm illustrated above we wanted to calculate the sum of the first 1000 natural numbers, it would be 1000 recursive calls and 1000 times more memory consumed.

The execution of a recursive algorithm

Another major difficulty you may have with recursive algorithms is understanding how they actually execute. For example: to track your execution using trace table technique.

Despite their elegance and syntactic simplicity, recursive algorithms retain great complexity in the way they are executed, as they create a hierarchical structure during their execution (a tree of recursive calls), and this is the main feature that hinders their correct understanding.

To understand how this happens in practice, let’s look at the illustrated execution of the generic recursive algorithm, a useless algorithm that only makes recursive flames for no practical purpose. Note in the code below:

1.public void func(int n) {
2.    if(n==0)
3.            return;
4.    func(n-1);
5.}

Let’s simulate the execution of this algorithm for a value n=3. Notice in the illustration below that execution creates a hierarchical structure. Creates a 4-level recursive call tree, each representing a subsequent recursive call.

Note that the value n=3 is submitted to the func() function (level 0). From that point on, the value of n (initially equal to 3) decreases with each new recursive call until the base case where n=0 (level 3) is reached.

After reaching the base case, recursive calls are returned to previous calls, performing a process called unstacking.

Multiple recursive calls

Another factor that impacts the complexity of a recursive algorithm is the amount of recursive calls in the recursive step. Note in the code below a generic algorithm that has 2 recursive calls (lines 4 and 5).

1.public void func(int n) {
2.    if(n==0) // base case
3.        return;
4.    func(n-1); // recursive pass
5.    func(n-1); // recursive pass
6.}

Let’s simulate the execution of this algorithm for a value n=3. Notice in the illustration below that execution creates a hierarchical tree-like structure. Note that each tree node generates another 2 nodes. This is because the two recursive calls (lines 4 and 5 of the above code) give rise to two distinct recursive call streams. As if they were two new dimensions originating from the same call.

These observations show us two very important properties of recursive algorithms:

1. the number of children generated from each of the recursive call tree nodes equals the number of recursive calls in the recursive step of the algorithm.
2. the number of nodes in the entire tree is equal to the total number of recursive function calls.

Now your turn to demonstrate your knowledge!

Exercise 1

Draw the recursive call tree for the recursive algorithm below (consider n=2):

1.public void func(int n) {
2.    System.out.println("new call");
3.    if(n==0)
4.        return;
5.    func(n-1);
6.    func(n-1);
7.    func(n-1);
8.}

Exercise 2

Draw the recursive call tree for the recursive algorithm below (consider n=3):

1.public void func(int n) {
2.    System.out.println("new call");
3.    if(n<=0)
4.        return;
5.    func(n-1);
6.    func(n-2);
7.    func(n-3);
8.}