publication

Recursive Functions in JavaScript: 10 Examples

Miquel Canal

Tuesday 24, November 2020
  • Software Engineering
  • JavaScript

What is a recursive function?

A recursive function is a function designed to call itself directly or indirectly. Using recursion, a problem can be solved by returning the value call of the same particular function.

A recursive function needs to be terminated at some point. The return of a recursive function is usually based on internal conditions which forwards the logic down to a new iteration until the base case is met.

Base cases in recursive functions.

In recursive functions, the base case is that iteration of a recursive function that does not need an additional recursion to solve a problem.

Base cases are mandatory on recursive functions. Without a base case a recursive function will never terminate leading it to an infinite loop.

1 - Linear sum

Sum all values from 0 to given number and display the result.

function sum(number) {
    if (number===0) {
        return 0;
    }
    return number + sum(number-1);
}

sum(10);

2 - Linear sum for even numbers

Sum all even numbers from 0 to given number and display the result.

function sumEven(number) {
    if (number===0) {
        return 0;
    } else if (number%2 !== 0) {
        return sumEven(number-1);
    }
    return number + sumEven(number-1);
}

sumEven(10);

3 - Number exponent (power)

Returns the value of exponent operation from given number and grade.

function pow(number, power) {
    if (power===1) {
        return number;
    }
    return number * pow(number, power-1);
}

pow(2,2);

4 - Factorial of a number

Returns the product of a given number from 1 to N.

function factorial(number) {
    if (number===1) {
        return 1;
    }
    return number*factorial(number-1);
}

factorial(3);

5 - Pascal Triangle

Display Pascal’s triangular array of the binomial coefficients.

Pascal Triangle
function pascal(row, column) {
    if (column>row) {
        return 0;
    }
    if (column<=1 || row<=1) {
        return 1;
    }
    return pascal(row-1, column) + pascal(row-1, column-1);
}

function triangle(number) {
    let string = "";
    for (let row=1; row<=number; row++) {
        for(let column=1; column<=row; column++) {
            string += `${pascal(row, column)} `;
        }
        string += "\n";
    }
    console.log(string);
}

triangle(10);

6 - Fibonacci sequence

Displays the Fibonacci sequence from a given number starting with 0.

Fibonacci Sequence
function fib(number) {
    function calc(number) {
        if (number<=1) {
            return number;
        }
        return calc(number-1) + calc(number-2);
    }
    let string = '';
    for(let i=1; i<=number; i++) {
        string += `${calc(i)} `;
    }
    console.log(string);
}

fib(10)

7 - Sieve of Eratosthenes

Sieve of eratosthenes

An ancient algorithm for finding all prime numbers up to a given number.

function soe(n) {
    let a = []
    let p = 2
    for (let i=p; i<=n; i++) {
        a.push(i)
    }
    console.log(compose(p, a, n).filter(m => m !== 0).join('-'));
}

function compose(p, a, n) {
    if (p*p > n) {
        return a
    }
    a = a.map(m => m!==p && m%p===0 ? 0 : m)
    p = a.find(m => m!==0 && m>p)
    return compose(p, a, n)
}

soe(100);

8 - Object search

Search a given value on properties of nested objects.

function search(obj, value) {
    if (typeof obj !== 'object') {
        return obj === value
    }

    for (const key in obj) {
        if (obj.hasOwnProperty(key) && search(obj[key], value)) {
            return true;
        }
    }
    return false;
}

search({
    level_1: {
        level_2: {
            level_3: {
                level_4: {
                    level_5: {
                        value: 20
                    }
                }
            }
        }
    }
}, 20);

9 - Leaf nodes on Binary Tree

Returns the leaf nodes of a given binary tree.

Binary Tree
function search_leaf(tree) {
    if (!tree.left && !tree.right) {
        return tree.value
    }
    if (tree.left) {
        let l = search_leaf(tree.left)
        if (l) { console.log(l) }
    }
    if (tree.right) {
        let l = search_leaf(tree.right)
        if (l) { console.log(l) }
    }
}

search_leaf({
    "value": 8,
    "left": {
        "value": 3,
        "left": {
            "value": 1,
            "left": null,
            "right": null
        },
        "right": {
            "value": 6,
            "left": {
                "value": 4,
                "left": null,
                "right": null
            },
            "right": {
                "value": 7,
                "left": null,
                "right": null
            }
        }
    },
    "right": {
        "value": 10,
        "left": null,
        "right": {
            "value": 14,
            "left": {
                "value": 13,
                "left": null,
                "right": null
            },
            "right": null
        }
    }
});

10 - Leaf nodes on Binary Search Tree

Returns the leaf nodes on a Binary Search Tree.

Binary Search Tree
function binary_search_tree(array) {
    if (array.length===1) {
        console.log(array[0]);
        return;
    }
    const base = array[0]
    const right = array.findIndex(n => n>base)
    binary_search_tree(array.slice(1,right))
    binary_search_tree(array.slice(right))
}

binary_search_tree([890,325,290,530,965]);

References

PM2 - Production Manager for Node.js

PM2 - Production Manager for Node.js

PM2 is a process manager for node.js applications. A powerful tool that will facilitate common system administration tasks for node apps.

The 12-Factor methodology

The 12-Factor methodology

The twelve-factor app is a methodology used to build software-as-a-service apps that are easy to scale up without significant changes to tooling or architecture.

Code Reusability in Software Programming

Code Reusability in Software Programming

What is code reusability? This article reviews the concepts around code reuse and how to apply them to software development.

This site uses cookies to ensure a great experience. By continue navigating through the site you accept the storage of these cookies.