Recursion simplified

Recursion is a process in which a function calls itself. This function is called a recursive function. A simple example of recursion is candy inside a matryoshka doll.

Matryoshka dolls are a set of wooden dolls of decreasing size placed one inside another. To get the candy, we would take the following steps as shown in the diagram below:

This procedure is recursive.

Features of a recursive function

function recurse() {
    if (condition) {
        //base case
    } else {
        recurse(); //recursive case
    }
}

A recursive function has two parts:

Recursive case: A recursive case is a part of the function that calls itself. Without a recursive case, a recursive function will not exist.
Base case: A base case is a terminating condition that tells the function when to stop calling itself. If omitted, the recursive function will run continuously and eventually crash your program.

Example of recursion

A good example of recursion is factorial.

Factorial is the product of an integer and all the positive integers below it. For example

the factorial of 9 is 9! = 9 x 8 x 7 x 6 x 5 x 4 x 3 x 2 x 1
the factorial of 3 is 3! = 3 x 2 x 1 = 6

This is what the code will look like in JavaScript

function factorial(num) {
    if (num == 1 || num == 0) {
        return 1;  //base case
    } else {
        return num * factorial(num - 1);   //recursive case
    }
}

factorial(3);
//6

From the above code we can see that the function calls itself again factorial(num - 1) but this time, minus one which makes it recursive.

Now, let's examine what happens when we pass 3 into the function argument

Since 3 is not equal to 1 or 0it will skip the base case and proceed to the recursive case which, results in 3 * factorial(3 - 1)
```
3 * factorial(2)
```
factorial(2) will go through the same process. 2 is not equal to 1 or 0 it will skip the base case and proceed to the recursive case which, will result in 2 * factorial(2 - 1)
```
2 * factorial(1)
```
factorial(1) will go through the same process but will return 1 since it fulfills our base case.
```
return 1
```

At this stage, we have decreased the argument by one on each function call and, our base case is true. The function will return in order from inner to outer because recursion is a group of nested function calls.

factorial(1) returns 1

factorial(2) returns 2 * factorial(1) or 2 * 1

factorial(3) returns 3 * factorial(2) or 3 * 2 * 1

3 * 2 * 1 = 6

Below is a diagram showing the procedure. Recursion can also solve the problems below:

Alternative to recursion

Iteration is an alternative to recursion. Iteration is the process of executing a set of instructions repeatedly. Any recursive function can be written iteratively and vice versa.

Let us solve the factorial problem iteratively

function factorialize(num) {
  if (num === 0 || num === 1)
    return 1;
  for (var i = num - 1;  i >= 1;  i--) {
    num *= i;
  }
  return num;
}
factorialize(3);
//6

We can see that recursion is an easy way to write and understand code compared to iteration, but recursion is not always the best option.

Recursion takes more memory space by building stacks which, eventually makes the program slow, while iteration use state variables for stacking and counting.

Some problems are simple to solve using recursion, especially when the efficiency of the program is not a concern. In such a case, recursion is a more preferred option.

Advantages of recursion

The following are reasons why you should use recursion.

Recursion makes code easy to understand.
It is a direct way to solve complex problems.
It makes code clean and precise.
It is an alternative to iteration.
It helps manipulate the tree structures of an object.

Disadvantages of recursion

Recursion requires more memory space because all the function calls store in the recursion call stack.
Recursion is slow compared to iteration because it consumes more memory space.
Poorly written recursive function leads to stack overflow. A stack overflow occurs when a function calls itself repeatedly until it exceeds the memory(call stack) allocated to it.

Conclusion

Recursion is a process in which a function calls itself.
A recursive function must have a base case and a recursive case.
A base case tells the function when to stop.
A recursive case is a part of the function that calls itself.
Factorial is the product of an integer and all the positive integers below it.
Recursive functions can be written iteratively and vice versa.
Recursion makes code precise and easy to understand.

Articles by Efe