Rafsan's Blog

Recursion

Recursion

Syed Rafsan Raiyan's photo
Syed Rafsan Raiyan
·

6 min read

Table of contents

What is Recursion? 🎗️

Recursion is a technique in programming where a function calls itself to accomplish a certain task. It is an elegant and powerful tool that can be used to solve problems cleanly and efficiently, but it can also be difficult to understand and implement correctly. In this blog post, we will explore the concept of recursion in more detail and look at some examples of how it can be used in JavaScript.

To begin, let's consider a simple example of a recursive function that calculates the factorial of a given number. The factorial of a number is the product of that number and all the positive integers less than it. For example, the factorial of 5 is 5 4 3 2 1, or 120. A recursive solution to this problem might look like this:

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

In this example, the function checks if the input number is 0. If it is, it returns 1, which is the base case of the recursion. If the input number is not 0, the function calls itself with the argument n - 1 and multiplies the result by n. This continues until the input number is 0, at which point the base case is reached and the function returns 1.

The key to understanding recursion is to identify the base case and the recursive case. In this example, the base case is when the input number is 0, and the recursive case is when the input number is not 0. The function calls itself with a modified argument in the recursive case, and the modifications are made in such a way that the base case will eventually be reached.

Another example of recursion is the problem of finding the n-th element in the Fibonacci sequence. The Fibonacci sequence is a series of numbers in which each number is the sum of the two preceding ones, usually starting with 0 and 1. A recursive solution to this problem might look like this:

function fibonacci(n) {
  if (n === 0 || n === 1) {
    return n;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2);
  }
}

In this example, the function checks if the input number is 0 or 1. If it is, it returns the corresponding value from the Fibonacci sequence (0 or 1). If the input number is not 0 or 1, the function calls itself twice: once with the argument n - 1 and once with the argument n - 2. The function returns the sum of the results of these two recursive calls, which is the n-th element of the Fibonacci sequence.

It's important to notice that recursive functions can take much more time and space in comparison with an iterative approach. This is because in most cases each recursive call creates a new stack frame in the call stack and each new frame takes up memory. So, it's important to be careful when using recursion, especially in large inputs.

Recursion vs Iteration 🎗️

Recursion and iteration are both techniques used to solve problems in programming, but they have some key differences.

Recursion is a technique where a function calls itself to accomplish a certain task. In a recursive solution, the problem is broken down into smaller sub-problems that are similar to the original problem, and a function is called recursively to solve each sub-problem.

function factorial(n) {
  if (n === 0) {
    return 1;
  } else {
    return n * factorial(n - 1);
  }
}

On the other hand, iteration is a technique where a loop is used to repeatedly execute a block of code until a certain condition is met. An iterative solution to the factorial problem might look like this:

function factorial(n) {
  let result = 1;
  for (let i = 1; i <= n; i++) {
    result *= i;
  }
  return result;
}

One of the main differences between recursion and iteration is the way in which they solve problems. Recursion uses a divide-and-conquer approach, where the problem is broken down into smaller sub-problems and solved recursively. Iteration, on the other hand, uses a repetitive approach, where a loop is used to repeatedly execute a block of code until a certain condition is met.

Another difference is that recursion can consume more memory and time than iteration, especially in large inputs. Each recursive call creates a new stack frame in the call stack, and each new frame takes up memory. And for each recursive call, the function needs to return and add the result of the previous call, taking more time. This is not a concern with iteration which is generally more efficient in memory usage and execution time.

In general, both recursion and iteration can be used to solve the same problem and have their advantages and disadvantages. Recursion can be simpler and more elegant, making the code more readable, but it can also consume more memory and be less efficient than iteration. On the other hand, iteration is more efficient and uses less memory, but can sometimes be more complex and less readable. Choosing which one to use will depend on the specific problem and the trade-offs you are willing to make.

When should one use Recursion? 🎗️

Recursion is a powerful technique in programming that can be used to solve a wide range of problems. However, it's not always the best option. Here are a few situations in which recursion is a good choice:

  • Problems that have a recursive structure: Some problems have a natural recursive structure, where the solution can be broken down into smaller sub-problems that are similar to the original problem. Examples of such problems include tree traversals, graph traversals, and other problems that involve breaking down a complex problem into smaller, simpler sub-problems.

  • Problems that have a clear base case: Recursive solutions need a base case, an explicit stop condition, which allows the function to know when it has reached the end of the recursion and can return a final result. If a problem has a clear base case, it can be a good candidate for a recursive solution.

  • Problems that can be defined in terms of similar sub-problems: Some problems can be defined in terms of smaller, similar sub-problems. These problems are often candidates for recursive solutions, as the recursive function can call itself with modified arguments to solve each sub-problem.

  • Problems that require traversals: For example, traversing a tree or a graph, recursion can help in traversing through the nodes in a way where each branch is handled as a separate call. This is because recursion involves breaking down the problem into smaller sub-problems, each of which is similar to the original problem.

It's important to note that recursion can consume more memory and time than iteration, especially in large inputs. And it can also be harder to understand and debug, especially if the recursive calls are nested. So it's important to evaluate the specific problem and weigh the trade-offs before deciding whether to use recursion.

Conclusion 🎗️

In conclusion, recursion is a powerful and elegant technique in programming that can be used to solve a wide range of problems cleanly and efficiently. By identifying the base case and the recursive case, and by making sure that the function calls itself with modified arguments in such a way that the base case will eventually be reached, we can write recursive functions that solve complex problems with a simple and elegant solution.

Wrap Up 🎗️

If you find this helpful, leave a like, share, and follow me, at @srafsan to read more articles.

RecursionJavaScriptdata structures