 Accéder à Open-Campus   # Data Structures : Recursion

Publié le 14/02/2020 à 15:08:54 Noter cet article:
Avis favorable du comité de lecture

### What is Recursion ?

The literal meaning of the word Recursion is self-recall, and that meaning alone is enough to define it. Simply put, it's a type of method that calls itself. This method has a structure and basics that must be implemented in this method.

### General structure of the recursion methods

```public void Test1(int i){

//Lines of code

if(){
//the basic condition or case that stops the self-call
}
Test1(/*any Value To pass*/); //the self call

//Lines of code
}```

The important thing that must not be forgotten is the basic condition, which is a condition that puts an end to the method recall. This condition is similar to the one we put to end a loop. If this condition isn't met, we'll face an endless call that will cause the application to breakdown.

To better understand the meaning of Recursion, let's review some examples:

### Examples

#### Factorial (X!)

Factorial(X) is the sum of multiplying all numbers from 1 to X. This calculation problem can be simply solved through recursion like shown below :

```    public  int  Factorial (int x){

if(x == 0){
return 1;
}
else {
return  x *  Factorial (x-1);
}
}
```

This method takes an integer (int) as input and gives out another integer as an output.

First, we have to determine the basic case. In this example it will be when the multiplied number is 0 then the result is 1. Which means that when 0 is sent to the method the output will be 1.

If the method does not receive a 0, the method will follow the other option. The value of i wil be stored and multiplied by it's previous value.

`x*(x+1)`

with 'i' being the current value of 'x' and 'x+1' it's previous value since we're substracting 1 for each iteration.

The method will then call itself again with an update 'x-1' .This update is crucial otherwise the method will keep calling itself forever since it won't be able to meet the required condition to stop the loop when. That condition is met only when :

` x == 0`

Let's look at this example to clear things up. Let's suppose that we called the method like this :

`System.out.println(Factorial(4));`

In the first call 4!= 0, so we follow the next step:

`4 * Factorial(4-1)`

Second call will give us this result:

`3 * Factorial(4-1)`

Then the third call:

`2 * Factorial(2-1)`

And finally, the fourth call:

`1 * Factorial(1-1)`

During the fifth call, i==0, so our condition is fulfilled. The value 1 will be returned to the last call.

One of the things to keep in mind, is that in case the method has called itself more than one time, the calls will be kept in a stack so that the last call gets the first answer. Let's take a look at the figure below: #### Sum of X

Like we did in the previous example, we're going to create a method that takes an integer value ('X') and calculate the sum of all numbers from 0 to X.

```
public int SUM(int x)
{
if(x == 0)
{
return 0;
}
else
{
return x + SUM(x -1);
}
}
```

#### Displaying numbers

Here, the user selects the value of X and we're displaying numbers from X to 1 in a descending order

```    public void printInt(int x)
{
if(x == 1)
{
System.out.println(1);
}
else
{
System.out.println(x);
printInt(x-1);
}
}
```

However, if we wanted to display the numbers in an ascending order. All we have to do is change the order of the last 2 lines like shown below :

```    public void printInt(int x)
{
if(x == 1)
{
System.out.println(1);
}
else
{
printInt(x-1);
System.out.println(x);
}
}
```

### Conclusion

The use of recursion in an algorithm has both advantages and disadvantages. The main advantage is the simplicity of instructions, while the disadvantage is that recursive algorithms can be memory consuming, rendering them impractical for larger instances.

### Sources

https://en.wikipedia.org/wiki/Recursion            SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels