DEV Community

Cover image for Recursion in JavaScript - Practical exercises
Adrian
Adrian

Posted on

Recursion in JavaScript - Practical exercises

Recursion is one of the most useful but very little understood programming techniques. Special kinds of problems can be solved easily and effectively with a recursive function (e.g., locating a file in a hierarchical file system).

This article doesn't intend to explain how recursion works ... but instead, it presents you eight classical problems implemented using a recursive and an iterative solution.

As you can probably see, for some problems, recursion comes more naturally, but for others, it should not be the first choice.

How to run the code?

Examples from this article have been developed using the codeguppy.com editor.

To run the code in this article, paste in the codeguppy.com editor the appropriate code snippet.

If you prefer to run the examples outside codeguppy.com, replace println() with console.log(), and you can run it in any environment you prefer.

Image description

Without further ado, let's see the problems and their solutions.

1. Calculate the sum of natural number up to n

Image description

Recursive solution

let sum = addTo(10);
println(sum);

function addTo(n)
{
    if (n == 0)
        return 0;

    return n + addTo(n - 1);
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

let sum = addTo(10);
println(sum);

function addTo(n)
{
    let sum = 0;

    for(let i = 1; i <= n; i++)
    {
        sum += i;
    }

    return sum;
}
Enter fullscreen mode Exit fullscreen mode

2. Calculate factorial of n. Reminder n! = 1 * 2 * ... * n

Recursive solution

let prod = factorial(10);
println(prod);

function factorial(n)
{
    if (n <= 1)
        return 1;

    return n * factorial(n - 1);
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

let prod = factorial(10);
println(prod);

function factorial(n)
{
    let prod = 1;

    for(let i = 1; i <= n; i++)
    {
        prod *= i;
    }

    return prod;
}
Enter fullscreen mode Exit fullscreen mode

3. Calculate the value of n to the m power

Recursive solution

println(powerNo(3, 2));

function powerNo(n, m)
{
    if (m == 0)
        return 1;

    if (m == 1)
        return n;

    return n * powerNo(n, m - 1);
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

println(powerNo(3, 2));

function powerNo(n, m)
{
    let prod = 1;

    for(let i = 1; i <= m; i++)
    {
        prod *= n;
    }

    return prod;
}
Enter fullscreen mode Exit fullscreen mode

4. Find the nth Fibonacci number

Recursive solution

function findFibonacci(n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;

    return findFibonacci(n - 1) + findFibonacci(n - 2);
}

let n = findFibonacci(10);
println(n);

Enter fullscreen mode Exit fullscreen mode

Iterative solution

function findFibonacci(n)
{
    let fib0 = 0;
    let fib1 = 1;

    if (n == 0)
        return fib0;

    if (n == 1)
        return fib1;

    let fib;

    for(let i = 2; i <= n; i++)
    {
        fib = fib0 + fib1;

        fib0 = fib1;
        fib1 = fib;
    }

    return fib;
}

println(findFibonacci(10));
Enter fullscreen mode Exit fullscreen mode

5. Calculate the sum of elements of an array of numbers

Recursive solution

let ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let n = sum(ar);
println(n);


function sum(ar)
{
    return _sum(ar, ar.length - 1);
}

function _sum(ar, index)
{
    if (index == 0)
        return ar[0];

    return ar[index] + _sum(ar, index - 1);
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

let ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
let n = sum(ar);
println(n);

function sum(ar)
{
    let sum = 0;

    for(let el of ar)
    {
        sum += el;
    }

    return sum;
}
Enter fullscreen mode Exit fullscreen mode

6. Sort an array of numbers using bubble sort algorithm

Recursive solution

let ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    let shouldSort = false;

    for(let i = 0; i < ar.length - 1; i++)
    {
        let a = ar[i];
        if ( a > ar[i+1] )
        {
            ar[i] = ar[i+1];
            ar[i+1] = a;
            shouldSort = true;
        }
    }

    if (shouldSort)
    {
        bubbleSort(ar);
    }
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

let ar = [23, 1000, 1, -1, 8, 3];
println(ar);
bubbleSort(ar);
println(ar);

function bubbleSort(ar)
{
    let shouldSort = true;

    while(shouldSort)
    {
        shouldSort = false;

        for(let i = 0; i < ar.length - 1; i++)
        {
            let a = ar[i];
            if ( a > ar[i+1] )
            {
                ar[i] = ar[i+1];
                ar[i+1] = a;
                shouldSort = true;
            }
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

7. Find a number in a sorted array (binary search)

Recursive solution

//        0   1   2   3   4   5   6   7   8   9
let ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

let position = findNumber(90, ar);
println(position);

// Find number n in sorted array ar
// Returns array index if found or -1 if not found
function findNumber(n, ar)
{
    return _findNumber(n, ar, 0, ar.length - 1);
}

// Find number n in sorted array ar in between indexes i1 and i2
// using recursive approach
function _findNumber(n, ar, i1, i2)
{
    if (i2 < i1)
        return -1;

    println("Checking interval: [" + i1 + ", " + i2 + "]");

    let mid = i1 + Math.floor((i2 - i1) / 2);

    if (n === ar[mid])
        return mid;

    if (n < ar[mid])
        return _findNumber(n, ar, i1, mid - 1);

    return _findNumber(n, ar, mid + 1, i2);
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

//        0   1   2   3   4   5   6   7   8   9
let ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

let position = findNumber(90, ar);
println(position);

// Find number n in sorted array ar using iterative approach
// Returns array index if found or -1 if not found
function findNumber(n, ar)
{
    let i1 = 0;
    let i2 = ar.length - 1;

    while(i1 <= i2)
    {
        println("Checking interval: [" + i1 + ", " + i2 + "]");

        let mid = i1 + Math.floor((i2 - i1) / 2);

        if (n === ar[mid])
            return mid;

        if (n < ar[mid])
        {
            i2 = mid - 1;
        }
        else
        {
            i1 = mid + 1;
        }
    }

    return -1;
}
Enter fullscreen mode Exit fullscreen mode

8. Find the maximum number in an array containing numbers or other arrays of numbers

Recursive solution

let ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

let max = findMax(ar);
println("Max  = ", max);

// Use recursion to find the maximum numeric value in an array of arrays
function findMax(ar)
{
    let max = -Infinity;

    // Cycle through all the elements of the array
    for(let i = 0; i < ar.length; i++)
    {
        let el = ar[i];

        // If an element is of type array then invoke the same function
        // to find out the maximum element of that subarray
        if ( Array.isArray(el) )
        {
            el = findMax( el );
        }

        if ( el > max )
        {
            max = el;
        }
    }

    return max;
}
Enter fullscreen mode Exit fullscreen mode

Iterative solution

// Find the maximum number in a jagged array of numbers or array of numbers
// Do not use recursion

let ar = [2, 4, 10, [12, 4, [100, 99], 4], [3, 2, 99], 0];

let max = findMax(ar);
println("Max  = ", max);

// Use a stack to find the maximum numeric value in an array of arrays
function findMax(arElements)
{
    let max = -Infinity;

    // This is the stack on which will put the first array and then 
    // all the other sub-arrays that we find as we traverse an array     
    let arrays = [];

    arrays.push(arElements);

    // Loop as long as are arrays added to the stack for processing
    while(arrays.length > 0)
    {
        // Extract an array from the stack
        ar = arrays.pop();

        // ... and loop through its elements
        for(let i = 0; i < ar.length; i++)
        {
            let el = ar[i];

            // If an element is of type array, we'll add it to stack
            // to be processed later
            if ( Array.isArray(el) )
            {
                arrays.push(el);
                continue;
            }

            if ( el > max )
            {
                max = el;
            }
        }
    }

    return max;
}
Enter fullscreen mode Exit fullscreen mode

Article reprinted from: https://codeguppy.com/blog/recursion-in-javascript-practical-examples/index.html

Image description

Top comments (0)