Recursive Functions with Examples -1

 

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.

What is 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.

Examples of Simple Recursive Functions

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);
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.
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.
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
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);