# Function calling itself? weird!

JavaScript

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
```