C++ Program Execution Stucked

Question

In my program,user will be asked for 2 different options.

I chose option 2..iterative and key in any value which will then lead to the output.

However,when i choose the 1st option which is recursive,it wont output anything that its value is above 30.Meaning to say,you will see an output if key in a value of 30..& there will be no output if were to key in the value of 40 or 50.

Can anyone please test on your compiler too?Its ok if something wrong with my compiler but if there is something wrong with my code.

#include<iostream>
using namespace std;

/* Fibonacci: recursive version */
int Fibonacci_R(int n)
{
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else return Fibonacci_R(n - 1) + Fibonacci_R(n - 2);
}

// iterative version
int Fibonacci_I(int n)
{
    int fib[] = { 0, 1, 1 };
    for (int i = 2; i <= n; i++)
    {
        fib[i % 3] = fib[(i - 1) % 3] + fib[(i - 2) % 3];
        cout << "fib(" << i << ") = " << fib[i % 3] << endl;
    }
    return fib[n % 3];
}

int main()
{
    int a, opt;
    cout << "Please choose the available option:\n";
    cout << "1)Recursive\n";
    cout << "2)Iterative\n";
    cin >> opt;
    if (opt == 1)
    {
        cout << "Please input value:\n";
        cin >> a;
        Fibonacci_R(a);
        cout << endl << "From recursive function" << endl;
        for (int i = 1; i <= a; ++i)
            cout << "fib(" << i << ") = " << Fibonacci_R(i) << endl;
        cout << endl;
    }
    else
    if (opt == 2)
    {
        cout << "Please input value:\n";
        cin >> a;
        Fibonacci_I(a);
    }
    system("pause");
    return 0;
}

Answer 1

When implementing an algorithm, I like to mentally evaluate the algorithm, to see what the computer is doing.

  fib(30)
= fib(29)  +  fib(28)
= fib(28)  +  fib(27)  +  fib(27)  +  fib(26)
= fib(27)  +  fib(26)  +  fib(26)  +  fib(25)+  fib(26)+  fib(25) +  fib(25)+  fib(24)

I notice that this algorithm seems really really inefficient. To calculate fib(30) it require 2^30 calculations! That's 1073741824!

Even worse, if I increase the number by 1, the time/operations to get a result doubles!

It will probably run forever with a large enough number! (Well until I fall asleep or my CPU burns up atleast)

---

Optimization

However, I notice that a lot of the calculations are redundant. To calculate fib(30), it must calculate fib(29) and fib(28). To calculate fib(29), it calculates fib(28) again. So inefficient!

When I see these kind of calculations the first thing that springs to mind is a technique call memoization. It caches results from a previous calculation and stores them for later use.

Using that in this case will reduce the number of calculations to something around 60 operations (?) at the cost of using more memory.

Example: What is memoization and how can I use it in Python?

Answer 2

It is not stuck, it just takes too long. It is because the complexity of recursive calculation. I assume that this school example was meant to show why recursive approach is inferior most of the time and should not be used.

Suppose you want to calculate Fibonacci_R(10). You will need to call Fibonacci_R(8) and Fibonacci_R(9). For calculation of Fibonacci_R(9) you will need to call Fibonacci_R(8) and Fibonacci_R(7). Which means you are calling Fibonacci_R(8) twice. If you continue along you will find that you are calling Fibonacci_R(7) three times - two times for Fibonacci_R(8) and once for Fibonacci_R(9)... you call Fibonacci_R(6) five times - two times for Fibonacci_R(8) and three times for Fibonacci_R(7)... etc. This is really hard when you start not with 10 but with 30. This will make your processor burn if you increase the number even more. Do not try it at home or make sure you have fire extinguisher at hand.

Btw. recursive algorithm is usually inferior not because of the complexity but because of limited memory stack which is used to store the variable and return address when calling a function.

Answer 3

A condition needed to be set for "int a" so while true, the "Fibunacci_R" function could execute. So; I used a "do/while" condition/loop at the point where "Fibunacci_R" is called and it worked

#include <iostream>
using namespace std;

/* Fibonacci: recursive version */
int Fibonacci_R(int n)
{
    if (n <= 0) return 0;
    else if (n == 1) return 1;
    else return (Fibonacci_R(n - 1) + Fibonacci_R(n - 2));
}

// iterative version
int Fibonacci_I(int n)
{
    int fib[] = { 0, 1, 1 };
    for (int i = 2; i <= n; i++)
    {
        fib[i % 3] = fib[(i - 1) % 3] + fib[(i - 2) % 3];
        cout << "fib(" << i << ") = " << fib[i % 3] << endl;
    }
    return fib[n % 3];
}

int main() {
    int a, opt;
    cout << "Please choose the available option:\n";
    cout << "1)Recursive\n";
    cout << "2)Iterative\n";
    cin >> opt;
    if (opt == 1) {
        cout << "Please input value:\n";
        cin >> a;

        // Here
        do {
            cout << endl << "From recursive function" << endl;
            for (int i = 1; i <= a; ++i)
                cout << "fib(" << i << ") = " << Fibonacci_R(i) << endl;
            cout << endl;
            break;
        } while (Fibonacci_R(a));
    }
    else
    if (opt == 2)
    {
        cout << "Please input value:\n";
        cin >> a;
        Fibonacci_I(a);
    }
    system("pause");
    return 0;
}

It just takes an awful lot of time to calculate an input of integers greater than 45