Fibonacci Sequence

The Fibonacci sequence is named after Leonardo Fibonacci. By definition first two numbers of the series are 0 and 1 and all the subsequent numbers are sum of the previous two numbers.

0     1     1     2     3     5     8     13     21     34     55 ...

Fibonacci Sequence, C++ implementation

int Fibonacci(int n)
{
    if (n == 0)
    {
        return 0;
    }
  
    if (n == 1 || n == 2)
    {
        return 1;
    }
    return Fibonacci(n - 1) + Fibonacci(n - 2);
}

NOTE: In the above implementation it returns zero if n is equal to zero and return 1 if n is less than or equal to 2. Those are the base cases which cause the recursion to stop.