« Calculate nth fibonacci number.

Problem:

Calculate nth fibonacci number.

The Fibonacci numbers are the numbers in the following integer sequence.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

Fn = Fn-1 + Fn-2

with seed values

F0 = 0 and F1 = 1.

Input Format:

A single integer ‘N’

Output Format:

A single integer representing nth fibonacci number

Constraints:

1 <= N <= 10^5

Sample Input :

n = 2

Sample Output :

1

Sapmle Input :

n = 9

Sample Output

34

Solution:

Copy
1#include <iostream>
2#include <iomanip>
3#include <algorithm>
4#include <string>
5#include <cstring>
6#include <vector>
7#include <cmath>
8#include <map>
9#include <climits>
10// climits for INT_MIN
11#include <unordered_map>
12using namespace std;
13
14int fib(int n)
15{
16    if (n == 0)
17    {
18        return 0;
19    }
20
21    if (n == 1)
22    {
23        return 1;
24    }
25    return fib(n - 1) + fib(n - 2);
26}
27
28int main()
29{
30    int i;
31    cin >> i;
32    cout << fib(i) << endl;
33    return 0;
34}