Common Recursion Examples using Javascript

In the previous post, we understood the concept of recursion. In this post, we will use our knowledge to look at some common recursion examples.

These examples will use Javascript as the programming language. However, the overall concept can apply to any other programming language.

Example 1- Function to find power of the base to an exponent

Basically, this function should mimic the Math.pow() function. It should take two inputs i.e. the base and the exponent and return the power. For example 2 to the power of 2 should be 4. Similarly, 2 to the power of 4 should be 16.

Below is the recursive way to write this function.

function power(base, exp){
    if (exp === 0) return 1;

    let result = base;

    result = result * power(base, exp - 1)

    return result
}

If you remember from our previous post about recursion, a recursive function has two important aspects – a base case and calling itself with different input.

In the above example, the below is the base case:

if (exp === 0) return 1;

The call to itself should have different input. Basically, in this case, we reduce the exponent by 1.

result = result * power(base, exp - 1)

The variable result acts as an accumulator to collect the final output.

Example 2 – Factorial of a Number

Another common recursion example is to find the factorial of a number.

As the name itself implies, this function should return the factorial of a number. For example, the factorial of 4 is 24. The factorial of the number 0 should be considered as 1.

Below is the implementation of such a function in a recursive manner:

function factorial(num){

    if (num === 0) return 1
    if (num === 1) return 1;

    let fact = num;

    fact = fact * factorial(num-1);
    return fact;
}

Here, the base case is to return 1 when the number is 0 or 1.

The other important aspect is calling the factorial function with (num -1) for every subsequent call. The fact variable acts as an accumulator.

Example 3 – Product of Array

Another one of the common recursion examples is to find the product of all the values in an array.

For example if there is an array such as [1, 2, 3] the product of all the values in the array is 6.

Below is the implementation.

function productOfArray(arr){
   if(arr.length === 0) return 1

    let product = arr[0];

    product = product * productOfArray(arr.slice(1))

    return product;
}

What is base case here?

Basically, when we have completely gone through the array and its length is 0, we return 1.

For each call, we use slice to return a portion of the array. In other words, we remove the first element and pass the rest of the array to the recursive call. The variable product accumulates the product of the numbers that is eventually returned from the recursive function.

Example 4 – Finding the number at a particular position in he Fibonacci Sequence

Fibonacci Sequence is as follows:

1 1 2 3 5 8

Basically, in a fibonacci sequence, a number is the sum of the numbers at the previous two positions.

So our function should accept a number and return the number at that position. For example, if our input is 4, the function should return 3 i.e. the number at the 4th position in the sequence.

Below is the recursive implementation to solve this:

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

Here, our base case is simple to understand. The first two numbers in a fibonacci sequence are always 1. So if n <=2, we simply return 1.

Then, we call the fib() function with n-1 and n-2 and add the output. This helps us ultimately find the number at a particular position in the fibonacci sequence.