DEV Community

Cover image for Practice recursion in JavaScript with these 8 coding challenges for beginners
Adrian
Adrian

Posted on • Updated on

Practice recursion in JavaScript with these 8 coding challenges for beginners

Introduction

Recursion is one of the most useful but very little understood programming technique. There are special kind of problems that can be solved very easy and elegant with a recursive function (e.g. locating a file in an hierarchical file system).

This article doesn't intend to offer an explanation of how recursion works ... but insted in presents you 8 classical problems implemented both using a recursive solution as well as an iterative solution.

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

How to run the code?

Examples from this article have been developed using the codeguppy.com editor. However just by replacing println() with console.log() you can run it in any environment you prefer.

Alt Text

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

1. Calculate the sum of natural number up to n

Alt Text

Recursive solution



var 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



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

function addTo(n)
{
    var sum = 0;

    for(var 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

Alt Text

Recursive solution



var 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



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

function factorial(n)
{
    var prod = 1;

    for(var 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

Alt Text

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)
{
    var prod = 1;

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

    return prod;
}


Enter fullscreen mode Exit fullscreen mode

4. Find the nth Fibonacci number

Alt Text

Recursive solution



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

    if (n == 1)
        return 1;

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

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



Enter fullscreen mode Exit fullscreen mode

Iterative solution



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

    if (n == 0)
        return fib0;

    if (n == 1)
        return fib1;

    var fib;

    for(var 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

Alt Text

Recursive solution



var ar = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
var 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



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

function sum(ar)
{
    var sum = 0;

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

    return sum;
}


Enter fullscreen mode Exit fullscreen mode

6. Sort an array of numbers using bubble sort algorithm

Alt Text

Recursive solution



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

function bubbleSort(ar)
{
    var shouldSort = false;

    for(var i = 0; i < ar.length - 1; i++)
    {
        var 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



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

function bubbleSort(ar)
{
    var shouldSort = true;

    while(shouldSort)
    {
        shouldSort = false;

        for(var i = 0; i < ar.length - 1; i++)
        {
            var 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)

Alt Text

Recursive solution



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

var 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 + "]");

    var 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
var ar = [10, 20, 30, 40, 50, 60, 70, 80, 90, 100];

var 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)
{
    var i1 = 0;
    var i2 = ar.length - 1;

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

        var 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

Alt Text

Recursive solution



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

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

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

    // Cycle through all the elements of the array
    for(var i = 0; i < ar.length; i++)
    {
        var 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

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

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

// Use a stack to find the maximum numeric value in an array of arrays
function findMax(arElements)
{
    var 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     
    var 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(var i = 0; i < ar.length; i++)
        {
            var 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

If you like this article please follow @codeguppy on Twitter for more programming fun.

Top comments (0)