Recursion explained !

Let's talk a little bit about Recursion 😎

Have you ever wondered what recursion is and how it works? If so, you are not alone. Recursion is one of the most powerful and elegant techniques in programming, but also one of the most confusing and intimidating for beginners.

In this article, I will try to explain recursion in a simple and funny way, using examples that will hopefully make you laugh and learn at the same time.✌

What is recursion?

Recursion is a method of solving problems by breaking them down into smaller and simpler sub-problems until they are so easy that they can be solved directly. Then, the solutions of the sub-problems are combined to form the solution to the original problem.

The key idea of recursion is that a function can call itself within its own definition. This is called a recursive call.

A recursive function must have two parts: a base case and a recursive case.

The base case is the simplest scenario where the function can return a value without calling itself. The base case acts as a stopping condition for the recursion.

The recursive case is where the function calls itself with a smaller or simpler input. The recursive case acts as a way to reduce the problem size and approach the base case.

An example of recursion

Let's look at an example of recursion: calculating the factorial of a positive integer n. The factorial of n, denoted by n!, is the product of all positive integers from 1 to n.

For example, 5! = 5 x 4 x 3 x 2 x 1 = 120.

How can we write a recursive function to compute n!? Well, we can use the following observation:

This is our base case.
The factorial of 1 is 1. ⇒ 1! = 1

This is our recursive case.
The factorial of n is n times the factorial of n-1.

5! = 5 * 4!
4! = 4 * 3!
3! = 3 * 2!
2! = 2 * 1!
1! = 1

Using these two facts, we can write a recursive function in pseudocode as follows:

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

Let's see how this function works for n = 5. We start by calling factorial(5). Since 5 is not equal to 1, we enter the else branch and return 5 * factorial(4). But before we can evaluate this expression, we need to know what factorial(4) is. So we make another recursive call to factorial(4). This process repeats until we reach the base case:

factorial(5) = 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1))) # base case reached
= 120

As you can see, each recursive call reduces the problem size by one, until we reach the simplest case where we can return a value directly. Then, we use that value to compute the previous call, and so on, until we get back to the original call.

A funny analogy of recursion

If you are still confused by recursion, don't worry. Here is a funny analogy that might help you understand it better.

Imagine that you are in a room with a mirror on one wall. You decide to take a selfie with your phone, but you want to capture the mirror in the background. So you stand in front of the mirror and point your phone at it.

What do you see on your phone screen? You see yourself holding your phone, but also another image of yourself holding your phone inside the mirror. And inside that image, there is another image of yourself holding your phone inside another mirror. And so on, infinitely.

This is like recursion. Each image of yourself holding your phone is like a recursive call to a function that takes a picture of yourself holding your phone. The first image is like the original call, and each subsequent image is like a smaller or simpler input.

But where is the base case? Well, there isn't one in this analogy. That's why you see an infinite sequence of images. In reality, however, there are some factors that limit the recursion, such as the size of your phone screen, the resolution of your camera, or the distance between you and the mirror.

These factors act as stopping conditions for the recursion. They prevent it from going on forever and make it possible to get a final result.

The moral of this analogy is that recursion can be fun and fascinating, but also tricky and dangerous. You need to be careful when using it!

Hope you found this article helpful, 👏👏👏.

Thank you for reading!