Recursion in JavaScript - Practical exercises
Tags: javascript, beginners, challenge, learning
Published: 2024-02-03 21:05:59

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](https://codeguppy.com/code.html). 

To run the code in this article, paste in the [codeguppy.com editor](https://codeguppy.com/code.html) 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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/92qdszud5085kpr7xe96.png)

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


## 1. Calculate the sum of natural number up to n


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/qo7llyiioyq9a57o1aoy.png)

#### Recursive solution

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

function addTo(n)
{
    if (n == 0)
        return 0;
    
    return n + addTo(n - 1);
}
```

#### Iterative solution

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

function addTo(n)
{
    let sum = 0;
    
    for(let i = 1; i <= n; i++)
    {
        sum += i;
    }
    
    return sum;
}
```

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


#### Recursive solution

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

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

#### Iterative solution

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

function factorial(n)
{
    let prod = 1;
    
    for(let i = 1; i <= n; i++)
    {
        prod *= i;
    }
    
    return prod;
}
```

## 3. Calculate the value of n to the m power


#### Recursive solution

```javascript
println(powerNo(3, 2));

function powerNo(n, m)
{
    if (m == 0)
        return 1;
    
    if (m == 1)
        return n;
        
    return n * powerNo(n, m - 1);
}
```

#### Iterative solution

```javascript
println(powerNo(3, 2));

function powerNo(n, m)
{
    let prod = 1;
    
    for(let i = 1; i <= m; i++)
    {
        prod *= n;
    }
    
    return prod;
}
```

## 4. Find the nth Fibonacci number


#### Recursive solution

```javascript
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);

```

#### Iterative solution

```javascript
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));
```

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


#### Recursive solution

```javascript
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);
}
```

#### Iterative solution

```javascript
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;
}
```

## 6. Sort an array of numbers using bubble sort algorithm


#### Recursive solution

```javascript
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);
    }
}
```

#### Iterative solution

```javascript
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;
            }
        }
    }
}
```

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

#### Recursive solution

```javascript
//        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);
}
```

#### Iterative solution

```javascript
//        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;
}
```

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


#### Recursive solution

```javascript
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;
}
```

#### Iterative solution

```javascript
// 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;
}
```

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/cp07gwe2e20bkblzk0k3.jpg)