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

Time: Recursion is more time consuming than loops.
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.
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

Fractal maths
Sorting
Traversing the nodes of complex or non-linear data structure
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

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

Ciao👋🏼

Recursion: A Programming Concept

Comments

More from this blog

DevRel in the World of Brain-Computer Interfaces

DevRel: A Beginner's View

Bug Hunting on SAW

Creating a CRUD app with Java Spring Boot

Top Wireframe Tools for Websites & Mobile Apps

Recursion vs Loop

Differences between Recursion and Loops

Application of Recursion

Conclusion

References

Command Palette

Comments

More from this blog

Recursion vs Loop

Differences between Recursion and Loops

Application of Recursion

Conclusion

References