Function calling itself? weird!

Well, this is called recursion. It's a pretty interesting concept that I have not gotten much grips on yet but will try to understand it slowly. The concept itself is simple - if you can redefine your problem in terms of the same problem but on a smaller data, it can be solved using recursion. Factorial and Fibonacci numbers are two classic examples:

Factorial $$ n! = n \times (n-1)! $$

Fibonacci Numbers $$ F_n = F_{n-1} + F_{n-2} $$

What do we need?

As in the examples above, we should be able to redefine the problem in terms of definition of the original problem but on a smaller data. For factorial, the smaller data is $n-1$ while it is $n-1$ and $n-2$ for fibonacci.

Another requirement while programming a problem in terms of recursion is there must be some base case, the answer to ther problem for the smallest possible input. This is where the last function call (to the smallest input) gets its answer and starts to compute the answer to the next larger, and next larger input and so on. Missing a base case can lead to infinite recursion (neat way of saying that your program will crash!). Let's see this in the JavaScript implementation of the above problems.

JavaScript Implementation

// factorial and fibonacci using recursion
function factorial(n)
{
    if (n == 1)         // base case
        return 1;
    else 
        return n * factorial(n - 1);
}


function fibonacci(n)
{
    if (n < 3)          // base case
        return 1;
    else
        return fibonacci(n - 1) + fibonacci(n - 2);
}

Let's test these

console.log(factorial(5));
console.log(fibonacci(8));
    
120
21