Fibonacci series

Question

I am trying to do an exercise with the Fibonacci series. I have to implement with a recursive function, a succession of the prime n number of Fibonacci and print them in the same function. The problem is that my function print also the intermediate number. The results, for example, for n = 6, should be : 1 1 2 3 5 8. Any solutions?

Thanks

#include<iostream>
using namespace std;
int rec(int n)
{
    int a, b;
    if (n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        cout << a + b << endl;
        return a + b;
    }

}
int main()
{ 
    int n = 6;
    rec(n);
    return 0;
}

I love the Fibonacci. How are you applying it that is not academic / homework? — SQLMason, Mar 31 '15 at 16:13
Have you searched? http://stackoverflow.com/questions/1518726/recursive-fibonacci — SQLMason, Mar 31 '15 at 16:16
you need to tag your language, and you need to show what's your current output for 6. — Jason Hu, Mar 31 '15 at 16:18
Sorry. My output for 6 is : 1 2 1 3 1 2 5 1 2 1 3 8. I saw stackoverflow.com/questions/1518726/recursive-Fibonacci but my problem is printing the numbers with the recursive function, not the Fibonacci function itself. — gerton, Mar 31 '15 at 16:36

user2736738 · Answer 1 · 2015-03-31T18:01:42.133

2

I have taken help of static int. That worked the way you wanted.

void rec(int n)
{
    static int a=0,b=1,sum;
    if(n>0)
    {
         sum = a+b;
         a=b;
         b= sum;
         cout<<sum<<" ";
         rec(n-1);
    }
}

Though you have to print the first Fibonacci number yourself in main().

cout<<"0 ";
rec(n);

edited Mar 31 '15 at 18:01

answered Mar 31 '15 at 16:42

user2736738

30,591
5
42
56

This example is only using recursion to replace a loop, effectively it's for( ; n > 0 ; n -= 1){ ... }, using the static variables to calculate the Fibonacci numbers. Also the first Fibonacci number is usually 0 (0 1 1 2 3 5 ...) . – rcgldr Mar 31 '15 at 17:50
@rcgldr.: Yes you are right, the recursion is used only to avoid the for loop. And the fibonacci numbers are usually 0 1 1 2 etc. But I will modify my answer(a mistake). – user2736738 Mar 31 '15 at 18:01
1

Very elegant solution! – Damian Mar 29 '16 at 08:32

score 1 · Accepted Answer · answered Mar 31 '15 at 18:22

1

You can use this:

#include<iostream>
using namespace std;
#define MAXN 100
int visited[MAXN];
int rec(int n)
{
    if(visited[n])
    {
        return visited[n];
    }
    int a, b;
    if (n == 0|| n==1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        cout << " " <<a + b;
        return visited[n] = a + b;
    }

}
int main()
{
    int n = 6;
    cout<< "1";
    rec(n);
    cout<<endl;
    return 0;
}

This implementation uses dynamic programming. So it reduces the computation time :)

answered Mar 31 '15 at 18:22

Ali Akber

3,670
3
26
40

You might wanna add `if(n >= MAXN){ return -1; }` at the beginning of `rec()` – Alex Díaz Mar 31 '15 at 18:43
Actually n will not be equal to MAXN. maximum n can be 46. if n>46, then it will overflow integer range – Ali Akber Mar 31 '15 at 18:55

sam · Answer 3 · 2015-03-31T17:12:32.350

Because you are printing in rec, its printing multiple times because of recursion. No need to print in the recursive function. Instead print the result in main

#include<iostream>
using namespace std;
int rec(int n)
{
    int a, b;
    if (n == 0 || n == 1)
    {
        return n;
    }
    else
    {
        a = rec(n - 1);
        b = rec(n - 2);
        //cout << a + b << endl;
        return a + b;
    }
}

int main()
{
    int n = 6;

    for (int i = 1; i <= n; i++)
    {
        cout << rec(i) << endl;
    }

    system("pause");
    return 0;
}

Eric Gitangu · Answer 4 · 2015-07-31T04:53:56.880

0

I'm pretty sure you have gotten working solutions but I have a slightly different approach that doesn't require you to use data structures:

/* Author: Eric Gitangu Date: 07/29/2015 This program spits out the fibionacci sequence for the range of 32-bit numbers Assumption: all values are +ve ; thus unsigned int works here */

#include <iostream>
#include <math.h>
#define N pow(2.0,31.0)

using namespace std;

void fibionacci(unsigned int &fib, unsigned int &prevfib){
    unsigned int temp = prevfib;
    prevfib = fib;
    fib += temp;
}
void main(){
    int count = 0;
    unsigned int fib = 0u, prev = 1u;

    while(fib < N){
        if( fib ==0 ){
            fib = 0;
            cout<<" "<< fib++ <<" \n ";
            continue;
        }
        if( fib == 1 && count++ < 2 ){
            fib = 1;
            cout<< fib <<" \n ";
            continue;
        }
        fibionacci(fib, prev);
        cout<< fib <<" \n ";
    }
}

edited Jul 31 '15 at 04:53

answered Jul 30 '15 at 09:17

Eric Gitangu

1
1

Output: 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 , 922 7465 , 14930352 , 24157817 , 39088169 , 63245986 , 102334155 , 165580141 , 267914296 , 433494437 , 701408733 , 113490317 0 , 1836311903 , 2971215073 – Eric Gitangu Jul 30 '15 at 11:01
I think OP wanted a recursive implementation though. – Mewa Jul 31 '15 at 00:16
Thank you Mewa for pointing that out, I did realize that after I had already posted but I figured I offer a different approach but thank u :) – Eric Gitangu Jul 31 '15 at 04:52

score 0 · Answer 5 · answered Apr 05 '16 at 06:28

0

Try this recursive function.

int fib(int n)
   return n<=2 ? n : fib(n-1) + fib(n-2);

It is the most elegant solution I know.

answered Apr 05 '16 at 06:28

Damian

4,395
4
39
67

Fibonacci series

5 Answers5