C++ Program to For Fibonacci Number

Fibonacci sequence is a series of numbers where each number is the sum of the two preceding ones, usually starting with 0 and 1. That is, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, and so on. Writing a C++ program to find the nth Fibonacci number involves understanding the iterative or recursive approach to generate the sequence.

Iterative Approach

The iterative method is more efficient than the recursive one, especially for large numbers, because it doesn’t involve deep function call stacks and thus avoids potential stack overflow issues and excessive memory use.

#include <iostream>

using namespace std;

int fibonacciIterative(int n) {

    if (n <= 1) {

        return n;

    }

    int previous = 0, current = 1;

    for (int i = 2; i <= n; i++) {

        int next = previous + current;

        previous = current;

        current = next;

    }

    return current;

}

int main() {

    int n;

    cout << “Enter the value of n: “;

    cin >> n;

    cout << “The ” << n << “th Fibonacci number (iterative) is: ” << fibonacciIterative(n) << endl;

    return 0;

}

Recursive Approach

The recursive method is a straightforward implementation of the Fibonacci definition but can be less efficient due to repeated calculations and deep recursion for large n. It’s a good demonstration of the concept of recursion, though.

#include <iostream>

using namespace std;

int fibonacciRecursive(int n) {

    if (n <= 1) {

        return n;

    } else {

        return fibonacciRecursive(n-1) + fibonacciRecursive(n-2);

    }

}

int main() {

    int n;

    cout << “Enter the value of n: “;

    cin >> n;

    cout << “The ” << n << “th Fibonacci number (recursive) is: ” << fibonacciRecursive(n) << endl;

    return 0;

}

Explanation

• Iterative Approach:

This method initializes the first two Fibonacci numbers, 0 and 1, and iteratively computes the next numbers in the sequence by summing the last two numbers until the nth number is found.

• Recursive Approach:

This method applies the Fibonacci series definition directly by using a function that calls itself to calculate the sum of the two preceding numbers until the base cases (n = 0 or n = 1) are reached.

Choosing Between Iterative and Recursive

• Efficiency:

The iterative approach is more efficient and is generally preferred for computing Fibonacci numbers, especially as n gets large.

• Educational Value:

The recursive approach is often used for educational purposes, to illustrate recursion, despite its inefficiency for larger n due to repeated computations and risk of stack overflow.