Description:

In this C++ example, we give two functions for calculating Fibonacci numbers. One function is recursive and the other is iterative. As the output demonstrates, the function are computationally equivalent.

Recursion can greatly simplify code. However, recursion is generally much slower than the comparable iterative code because of the repeated function calls. In the case of the Fibonacci numbers, there is also an explicit formula, which may be even faster than the iterative code shown here.

Example

#include <iostream>

int FibonacciRecur(int iN) {
    // Stopping condition
    if (iN < 3) {
        if (iN < 1) {
            return 0;
        }
        return 1;
    }
    return FibonacciRecur(iN - 1) + FibonacciRecur(iN - 2);
}

int FibonacciIter(int iN) {
    if (iN <= 0) {
        return 0;
    }
    int iF0 = 0;
    int iF1 = 1;
    for (int i = 2; i <= iN; ++i) {
        iF1 += iF0;
        iF0 = iF1 - iF0;
    }
    return iF1;
}

int main()
{
    for (int i = 0; i < 12; ++i) {
        std::cout << "n = " << i << "  Fn = " << FibonacciRecur(i) << std::endl;
        std::cout << "n = " << i << "  Fn = " << FibonacciIter(i) << std::endl;
    }

    return 0;
}

Output:

Fibonacci Numbers Output