Practice › Recursion & Backtracking
Fibonacci Number
Easy · Recursion & Backtracking · Asked at TCS, Infosys, Wipro, Amazon
The Fibonacci sequence is F(0) = 0, F(1) = 1 and F(n) = F(n-1) + F(n-2). Print F(n).
Input
One integer n.
Output
The value of F(n).
Constraints
- 0 ≤ n ≤ 80
Plain recursion is too slow for large n — try a loop or memoization. F(80) needs a 64-bit integer.
Example 1
Input
6
Output
8
Example 2
Input
1
Output
1
Hints
- Plain recursion fib(n − 1) + fib(n − 2) recomputes the same values exponentially many times.
- Keep only the last two values and loop from 2 to n. F(80) needs a 64-bit integer.
Approach
Each Fibonacci number depends only on the previous two, so iterate with two variables: a = F(i − 1) and b = F(i). Each step does (a, b) = (b, a + b), giving O(n) time instead of O(2^n) for naive recursion. Memoised recursion gives the same O(n). F(80) ≈ 2.3 × 10^16 overflows 32-bit ints.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
long long a = 0, b = 1; // F(0), F(1)
for (int i = 0; i < n; i++) {
long long next = a + b;
a = b;
b = next;
}
cout << a << "\n";
return 0;
}Python solution
n = int(input())
a, b = 0, 1 # F(0), F(1)
for _ in range(n):
a, b = b, a + b
print(a)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long a = 0, b = 1; // F(0), F(1)
for (int i = 0; i < n; i++) {
long next = a + b;
a = b;
b = next;
}
System.out.println(a);
}
}