Data Structures and Algorithms: Recursion

Introduction

Recursion is a programming technique where a function calls itself repeatedly until it reaches a base case, which is the point at which the problem is solved.

There are two steps to recursion:

1. Base case
2. Recursive case

Solving a problem with recursion

We can use recursion to solve the problem of finding the factorial of any given integer.

Base Case

To solve this with recursion, first we must create our base case. We will use the base case to prevent the function from running forever, at which point it will stop calling itself to return a result.

Given that the factorial of a number n is the product of all positive integers less than or equal to n, the function will stop calling itself once n is equal to 1. At this point the return value will be 1.

if(n === 1) {
   return 1;
}

Recursive Case

The second part is recursive case, where the function will call itself until it reaches the base case.
In order to find the factorial, the function will be call itself whilst decrementing the value of n.

n * factorial(n - 1);

The recursive case can be divided into 3 steps:

1. Pre: where an operation is performed before recursing, for example, multiplying the function by n.
2. Recursion: where the function is called.
3. Post: where n operation is performed after recursing, for example, logging the value of n.

With the base case and recursive case defined, we can now write out the function to find the factorial of an integer.

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

Conclusion

Recursion can be a useful tool for breaking down complex programming problems. It is often used as an alternative to iteration(for and while loops) and is very useful for traversing trees and graphs.