nth Fibonacci Number in C++

nth Fibonacci in C++. This program: position 1 is 0, position 10 is 34.

BeginnerLoop ProgramsExample 11 of 14

nth-fibonacci-number.cpp

1#include <iostream>
2using namespace std;
3
4int main() {
5    int n, first = 0, second = 1, next;
6    
7    cout << "Enter the position (n): ";
8    cin >> n;
9    
10    if (n == 1) {
11        cout << "Fibonacci number at position " << n << " is: " << first << endl;
12    } else if (n == 2) {
13        cout << "Fibonacci number at position " << n << " is: " << second << endl;
14    } else {
15        for (int i = 3; i <= n; i++) {
16            next = first + second;
17            first = second;
18            second = next;
19        }
20        cout << "Fibonacci number at position " << n << " is: " << second << endl;
21    }
22    
23    return 0;
24}

Output

Enter the position (n): 10
Fibonacci number at position 10 is: 34

What's going on

Fibonacci here: each term is the sum of the two before it. This program treats position 1 as 0, position 2 as 1, position 10 as 34.

That's 0, 1, 1, 2, 3, 5, 8, 13, 21, 34. Some books call 34 F(9) because they start at F(0)=0. This file starts counting at 1. Read the if (n == 1) branch before arguing with the sample.

int n, first = 0, second = 1, next;

n == 1 → print 0.

n == 2 → print 1.

Else from i = 3 to n:

next = first + second;

first = second;

second = next;

Walk to 10:

i=3: next=1, (0,1) → (1,1)

i=4: next=2, → (1,2)

i=5: next=3, → (2,3)

i=6: next=5, → (3,5)

i=7: next=8, → (5,8)

i=8: next=13, → (8,13)

i=9: next=21, → (13,21)

i=10: next=34, → (21,34)

Print second. Sample: Fibonacci number at position 10 is: 34.

Naive recursion fib(n-1)+fib(n-2) is the same sequence with exponential time. This loop is O(n) and a handful of ints.

int overflows around position 47. long long if you go further.

PreviousArmstrong Number NextCalculate the Power of a Number