Javascript zero to hero. Recursion.

Recursion is a concept that is not native to javascript. It is a concept that spans multiple programming languages. It is a way to solve complex problems by dividing the problems into smaller and smaller problems until the subproblem is small enough for you to tackle directly. Recursion is a concept widely used in many areas of computer science, such as data structures, algorithms, and even building programming languages.

In this blog post, we will discuss recursion, how it works, and how it can be implemented in JavaScript. We will also look at some common examples of recursive functions and their applications.

What is Recursion?

Recursion is a programming technique in which a function calls itself to solve a problem. A function that calls itself sometimes even more than once is said to be recursive.

To understand recursion you need to understand two concepts. base case and recursive case. The base case is the point at which the recursion stops. The recursive case is when the function will have to recall itself.

How Recursion Works

The process of breaking a problem down into smaller subproblems is called the recursion tree.

The recursion tree is a tree-like structure that represents the recursive calls made by the function. Each node represents a call to a function. The root node represents the initial call to the function, and the leaf nodes represent the base cases.

Implementing Recursion in JavaScript

To implement recursion in js we need to define a function that recalls itself. The function should include a base case that will stop the recursion. Here is an example of a recursive function that calculates the factorial of a number:

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

In the function above the base case is when n === 0 the function returns 1 which is the factorial of 0. The recursive case is when n is greater than 0. Implying that the function will be called until n === 0. The function returns the result of the function call with the current value of n.

Here is an example of how to call the factorial function:

console.log(factorial(5)); // Output: 120

This code will output 120 which is the factorial of 5.

Some more examples.

1. fibonnacci sequence

The Fibonacci series is a sequence of numbers in which each number is the sum of the two preceding numbers. The first two numbers in the series are 0 and 1.

Here is an example of a recursive function that generates the Fibonacci series:

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

In this function, the base case is when n is less than or equal to 1. The function returns n, which is either 0 or 1. The recursive case is when n is greater than 1. The function calls itself with n - 1 and n - 2 as the arguments and adds the results.

Here is an example of how to call the fibonacci function:

console.log(fibonacci(6)); // Output: 8

This function call will return 8 which is the 6th number of the fibonnacci sequence.

Binary Search

Binary search is a common algorithm for finding a certain value in a sorted array. The algorithm works by dividing the array in half and recursively searching in the appropriate half until the element is found or the search is unsuccessful.

function binarySearch(array, target, start, end) {
  if (start > end) {
    return -1;
  }
  
  let mid = Math.floor((start + end) / 2);
  
  if (array[mid] === target) {
    return mid;
  } else if (array[mid] < target) {
    return binarySearch(array, target, mid + 1, end);
  } else {
    return binarySearch(array, target, start, mid - 1);
  }
}

If this function confused you you are not alone. Here is a detailed explanation.

In this function, the base case is when start is greater than end. The function returns -1, indicating that the element was not found. The recursive case is when the middle element in the array is not equal to the target element. The function recursively searches in the appropriate half of the array based on whether the middle element is less than or greater than the target element.

Here is an example of how to call the binarySearch function:

This code will output 3, which is the index of the target element in the array.

Conclusion

Recursion is not an easy concept to wrap your head around. But when you finally get that “oooooh” moment trust me the dopamine that will be floating inside your brain is worth anything. Keep learning.