Understanding the concept of recursion in programming

Recursion is a programming technique where a function calls itself to solve a problem.

It allows a complex problem to be divided into simpler sub-problems, until a "base case" is reached, meaning a situation where the function can return a solution without calling itself again.

This is also sometimes referred to as a "stopping condition"

What is recursion?

In programming, a recursive function consists of two essential parts:

• The base case: This is the condition that ends the recursion. Without a base case, the function would enter an infinite loop.
• The recursive call: This is the invocation of the function within itself, in order to progressively approach the base case.

One of the classic examples of recursion is calculating the factorial of a number. The factorial of n (denoted n!) is the product of all integers from 1 to n. For example, 5! = 5 * 4 * 3 * 2 * 1 = 120.

An example of use

A recursive function can be used for a great many cases that would otherwise require a classic loop, but it is also very often found when solving mathematical problems.

For example, to solve the factorial of a number

In mathematics, the factorial of a positive integer n (denoted n!) is the product of all positive integers from 1 to n.

Example: the factorial of the number 5 is denoted 5! and equals 5×4×3×2×1 = 120

And here is how one could solve the factorial of a number with a recursive loop (in pseudocode):

Function Factorial(n)
    If n equals 0 or 1
        Return 1
    Else
        Return n * Factorial(n - 1)
End Function

By mathematical convention 0!=1, which is why the stopping condition applies to both the case 0 and 1

Implementation in JavaScript

Here is how to implement the same recursive function to calculate the factorial of a number, but this time in JavaScript:

function factorial(n) {
  // Base case: the factorial of 0 or 1 is 1
  if (n === 0 || n === 1) {
    return 1;
  }
  // Recursive call
  return n * factorial(n - 1);
}

console.log(factorial(5));

If we had wanted to implement the same algorithm with a while loop, here is what it could look like:

function factorial(n) {
  let result = 1;
  
  while (n > 1) {
    result *= n;
    n--;
  }
  
  return result;
}

You'll notice that the two solutions are quite close to one another, except that the version with a loop needs an additional intermediate result variable.

Why use recursion?

Recursion mainly allows you to write cleaner and more "elegant" code, but be careful: a recursive solution is often slower than an iterative solution (loop).

Except for certain compiled languages that optimize the resolution of the "base case."

There are a few use cases where recursion is interesting in terms of syntax, such as traversing trees, linked lists, or when a problem can easily be broken down into sub-problems.

But be careful about the depth of the recursion, because the "call stack," which stores all the function calls, can fill up and your program's execution can stop entirely, this is known as a "stack overflow."

If you'd like to go further into the pros and cons of recursion, I recommend this article (in English): https://medium.com/@williambdale/recursion-the-pros-and-cons-76d32d75973a