How to print Fibonacci Series upto n numbers using Recursion in C++

Question

I am trying to print Fibonacci series using recursion. Unfortunately, it repeatedly prints the last number.

For e.g; if I input 5 it first prints: 1, then 0, then again 1 & 1, and then 2, and then it starts repeating again 0 1 1 2 and after that it prints 3.

#include<iostream>
using namespace std;

int fibonacci(int n)
{
    if (n == 0 || n == 1)
    {
        cout << n << " ";
        return n;
    }
    else
    {
        int sum = fibonacci(n - 1) + fibonacci(n - 2);
        cout << sum << " ";
        return sum;
    }
}

//====================================================================
void main()
{
    int n;
    cout << "Please input the Limit: ";
    cin >> n;
    fibonacci(n);
    system("pause>null");
}

There is nothing .net nor visual-studio related in this question — 463035818_is_not_an_ai
– 463035818_is_not_an_ai, Commented Feb 3, 2016 at 16:25
You could declare it like int fibonacci(int n, bool print = false) and call it in the main with fibonacci(n,true), surround the cout with if(print){}. That said, doing fibonacci this way is extremely inefficient, you will do 2^n calculations when n would suffice. This means that fib(100) will take about 1E30 calculations instead of 100 calculations (and will probably kill your memory doing so). — Aziuth
– Aziuth, Commented Feb 3, 2016 at 16:26
@tobi303 I dunno, void main() is not standard C++, might be a visual studio extension. Hardly merits the tag though. — BoBTFish
– BoBTFish, Commented Feb 3, 2016 at 16:27
It's been 3 decades since I have had to write this function however I believe you have got the algorithm wrong. Shouldn't there be a n-2? — drescherjm
– drescherjm, Commented Feb 3, 2016 at 16:31

uselpa · Accepted Answer · 2016-02-05 19:42:45Z

The recursive definition of the fibonacci function is

fib(n) = fib(n-1) + fib(n-2)

so just change

int sum = fibonacci(n - 1) + fibonacci(n - 1);

to

int sum = fibonacci(n - 1) + fibonacci(n - 2);

Testing:

Please input the Limit: 5
1 0 1 1 2 1 0 1 3 1 0 1 1 2 5

Please input the Limit: 6
1 0 1 1 2 1 0 1 3 1 0 1 1 2 5 1 0 1 1 2 1 0 1 3 8

EDIT 1

You would like to print the fibonacci sequence fib(0), fib(1), ... with this algorithm. If you beef up your output a little you'll see how this works for fib(5):

fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 1 = 1
fib 3 = 2
fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 4 = 3
fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 1 = 1
fib 3 = 2
fib 5 = 5
5

As you see quite a few values are computed several times, which explains the sequence that is printed. One way to compute each result only once is Memoization. If you use memoization and only print the first time a result is determined you'll get:

fib 1 = 1
fib 0 = 0
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5
5

so even then you don't get the order you want. So you'd have to use memoisation and only print the hash map at the end of the process.

5
fib 0 = 0
fib 1 = 1
fib 2 = 1
fib 3 = 2
fib 4 = 3
fib 5 = 5

Of course, you could also just create an additional loop and print all values for fib(i) for i from 1 to n. That would be fairly inefficient though.

EDIT 2

Disclaimer: I have no clue about C++. I wrote my last C program ages ago. But the following works, other people will do it better I'm sure.

So here's a simple example of memoization using a plain array, no hash map. Since you didn't say which concepts you have learnt until now I hope this is simple enough.

#include <iostream>

#define MAX 100
#define UNDEF -1

using namespace std;

int memo[MAX]; // memoization of results

int fibonacci(int n) {
    int res = memo[n];
    if (res != UNDEF) return res; // result has been computed before
    if (n == 0 || n == 1)
        res = n;
    else
        res = fibonacci(n - 1) + fibonacci(n - 2);
    memo[n] = res; // memoize result
    return res;
}

int main() {
    int n, i;
    do {
        cout << "Please input the Limit (max " << MAX << ") : ";
        cin >> n;
    } while (n < 0 || n >= MAX);
    for (i=0; i<=n; i++) memo[i] = UNDEF; // intitialize memo
    fibonacci(n);
    for (i=0; i<=n; i++) cout << memo[i] << " "; // print results
    cout << endl;
}

Testing:

Please input the Limit (max 100) : 40
0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765 10946 17711 28657 46368 75025 121393 196418 317811 514229 832040 1346269 2178309 3524578 5702887 9227465 14930352 24157817 39088169 63245986 102334155

you are right it was a typing mistake but i am still not getting the right answer , it should be 0 1 2 3 5 ..... etc .
usepla you are right i can use a loop but i want to do it by recursion and this method is still not acceptable so can you help me a little bit further?
No i just want you to modify my code and apply a condition so that it will prints specific numbers and do not repeat numbers .
It's not just applying a condition; you need to implement memoization and then loop over the resulting hash map. So basically you have to rewrite your function. I won't have the time to do that right now, but those pointers should get you on the right track.

Ziezi · Accepted Answer · 2016-02-03 19:10:56Z

Here is an example of an implementation, using memoization:

// header needed for the container: map
#include <map> 

int mem_fact (int i, std::map<int, int>& m) {

    // if value with key == i does not exist in m: calculate it
    if (m.find(i) == m.end()) {

        // the recursive calls are made only if the value doesn't already exist
        m[i] = mem_fact (i - 1, m) + mem_fact (i - 2, m); 
    }

    // if value with key == i exists, return the corresponding value
    return m[i];
}

int fast_factorial (int i) {
    // key (Fibonacci index) - value (Fibbonaci number)
    std::map<int, int> memo;

    // initialize the first two Fibonacci numbers
    memo.insert(std::pair<int,int>(0, 0));
    memo.insert(std::pair<int,int>(1, 1));

    return mem_fact(i, memo);
}

I will leave to you where to put the std::cout so that each fibonacci number is displayed once.

Note: in main() you need to call fast_factorial(num_of_fib);

Isaac Clancy · Accepted Answer · 2017-01-05 01:38:17Z

this works

#include <iostream>
#include <chrono>

void _fib(unsigned int current, unsigned int max, unsigned int oneBack, unsigned int twoBack)
{
    if (current == max) return;
    unsigned int sum = oneBack + twoBack;
    std::cout << sum << '\n';
    _fib(current+1, max, sum, oneBack);
}

void fib(unsigned int max)
{
    if (max >= 2)
    {
        std::cout << "0\n1\n";
        _fib(2, max, 1, 0);
    }
    else if (max == 1)
    {
        std::cout << "0\n1\n";
    }
    else if (max == 0)
    {
        std::cout << "0\n";
    }
}

int main()
{
    auto start = std::chrono::system_clock::now();
    fib(1000);
    auto end = std::chrono::system_clock::now();
    std::chrono::duration<double> diff = end - start;
    std::cout << diff.count() << "seconds";
}

Asim Jawad · Accepted Answer · 2017-03-25 16:28:24Z

0

#include<iostream>

using namespace std;

int fibonacci(int n)
{
if((n==1)||(n==0))
{
    return(n);
}
else
{
    return(fibonacci(n-1)+fibonacci(n-2));
}
}

int main()
{
int n,i=0;
cout<<"Input the number of terms for Fibonacci Series:";
cin>>n;
cout<<"\nFibonacci Series is as follows\n";

while(i<n)
{
    cout<<" "<<fibonacci(i);
    i++;
}

return 0;
}
//use this one it is easy

answered Mar 25, 2017 at 16:28

Asim Jawad

1732 silver badges11 bronze badges

Collectives™ on Stack Overflow

How to print Fibonacci Series upto n numbers using Recursion in C++

4 Answers 4

7 Comments

Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

7 Comments

Comments

Comments

Comments

Related