Recursion: A Programming Concept

If you studied computer science or you're into programming, you most likely have come across the term Recursion. Quite a number of developer don't really use recursion, or perhaps it's the ones I know that don't use it. 🤔🤔

So, what is recursion?

Recursion is an iteration technique where a function calls itself. It's applicable when you need to call the same function repeatedly with different parameters from within a loop.

Search for Recursion on google and you get this. Now, click against the suggested recursion.

What happens? You're redirected to the same page. That's recursion with a sense of humour.

Recursion vs Loop

Let's take a look at 2 scenarios

Scenario A- Loop

const pow = (x,n)=>{
  let result = 1;

  for (let i = 0; i < n; i++) {
    result *= x;
  }
  return result;
}

console.log( pow(2, 3) ); // 8

Scenario B- Recursion

const pow = (x,n)=>{
  if (n == 1) {
    return x;
  } else {
    return x * pow(x, n - 1);
  }
}
console.log( pow(2, 3) ); // 8

What do you note between these 2 scenarios? In scenario A, we loop over the variables i.e instructions are repeatedly executed while in scenario B, the function calls itself.

To calculate pow(2, 3) the recursive steps are as below:

pow(2, 3) = 2 pow(2, 2) => 2 4 = 8

pow(2, 2) = 2 pow(2, 1) => 2 2 = 4

pow(2, 1) = 2

Recursion reduces a function call to a simpler one until the result is gotten.

It's essential to define a breakpoint (n==1 as in the example above) else your function will run indefinitely.

Differences between Recursion and Loops

1. Time: Recursion is more time consuming than loops.
2. Usage: Recursion is used when code size needs to be small, and time complexity is not an issue. A loop is used when time complexity needs to be measured against the code size.
3. Termination: Recursive function is terminated when there is no function call. A loop is terminated when the condition for the iterator ceases to be satisfied.

Application of Recursion

1. Fractal maths
2. Sorting
3. Traversing the nodes of complex or non-linear data structure
4. File trees

Conclusion

Recursion is a powerful technique and is the most direct way to solve a complex problem. However, due to its shortcomings, we will need to be very careful about how and where we apply recursion.

References

1. Recursion in Functional JavaScript
2. Understanding Recursion Using Real-World Examples
3. Difference between Recursion and Iteration
4. Recursion and stack

If you like this article, feel free to comment and share. You can also reach out to me on Twitter | LinkedIn | Github

Ciao👋🏼