CODEWITHSUNDEEP
c++recursion
user3499387
user3499387

Reputation: 1

Recursion help in C++

The assignment is Design and Develop a C++ program to list the first N terms of the Fibonacci series.

The output should look like this:

My problem is that I have written the recursive function below but I'm not sure how to format it so it outputs to screen in the manner above.

#include <iostream>
using namespace std;

//Function Prototype
int fib(int);


int main()
{
for (int x = 0; x < 15; x++)
    cout << fib(x) << " ";




    cin.get();
    cin.get();

    return 0;
}

//Definition of fib 
int fib(int n)
{ 
//Return 1 when n is 0
 if ( n <= 0 ) 
     return 0;
 else if (n == 1)
     return 1;
 else
     return fib(n-1) + fib(n-2);

}

Could someone shed some light on how to get this accomplished?

Thank you.

Upvotes: 0

Views: 191

Answers (5)

agbinfo
agbinfo

Reputation: 803

Here's an example that doesn't recompute values when calling fib for a single value. You can combine Marius's idea to compute the values once even on multiple runs.

The trick is that fib(unsigned&, unsigned) will return the previous fibonacci it has already computed.

#include <iostream>
using namespace std;

unsigned fib(unsigned& m, unsigned n)
{ 
  if (n==0) {
    return 0;
  }

  if (n==1) {
    m = 0;
    // cout << "0,"; // uncomment if sequence should start with a 0
    return 1;
  }

  unsigned prev;
  m = fib(prev, n-1);
  cout << m << ",";
  return m+prev;
}

unsigned fib(unsigned n) {
  unsigned prev;
  unsigned f = fib(prev, n);
  cout << f;
  return f;
}

int main() {
  for (unsigned i=2; i<13; i++) {
    cout << "N=" << i << " ";
    fib(i);
    cout << endl;
  }
  return 0;
}

Will printout:

N=2 1,1
N=3 1,1,2
N=4 1,1,2,3
N=5 1,1,2,3,5
N=6 1,1,2,3,5,8
N=7 1,1,2,3,5,8,13
N=8 1,1,2,3,5,8,13,21

Upvotes: 0

Noctis
Noctis

Reputation: 11763

Since it all does is print the fibonacci number, and the ones before, you just need to add them to your output ... You can either have an aggregating string that you pass along, that will hold all the temp values, or just call another method that will have temp outputs. (mind you, it's not very efficient though :)

int fib_verbose(int n)
{ 
  //Return 1 when n is 0
   if ( n <= 0 ) 
      return 0;
  else if (n == 1) {         
      return 1;
  }
  else {
      int smaller = fib(n-2);
      int larger = fib(n-1);

      cout << smaller << " " << larger  << endl;
      return smaller + larger;
  }
}

You'll have to sort out the spaces, and formatting, but that's the gist.

Edit: As per agbinfo comment: removed the 1 printing, and also storing the variables so we don't need to call them twice. (Still, for efficiency, look at Marius's answer :) ).

Upvotes: 1

Marius Bancila
Marius Bancila

Reputation: 16318

I would take a different approach. I'd save the already computed Fibonacci values so they are not computed them over and over again, like in a map, and than using that map to print the values.

std::map<int, int> fibs;

int fib(int const n)
{
   auto p = fibs.find(n);
   if(p != fibs.end())
      return p->second;

   int f = 1;
   if (n > 1)
   {
      f = fib(n-1) + fib(n-2);
   }

   fibs[n] = f;

   return f;
}

You can then loop through the computed values like this:

for(int n = 0; n < 10; ++n)
{
   fib(n);

   std::cout << "N=" << n << " ";
   for(int i = 0; i <= n; ++i)
      std::cout << fibs[i] << ",";

   std::cout << std::endl;
}

Upvotes: 1

2785528
2785528

Reputation: 5566

How to format?

You have a good start. Try this as a next step...

for (int x = 0; x < 15; x++)
   cout << x << "=" << fib(x) << " " << std::endl;

cin.get();

In my system, I can add to the cout line, compile, and review the output in < 10 seconds. Fast turn around and practice (for you) are your friends.

Upvotes: 1

CapelliC
CapelliC

Reputation: 60004

if you don't care too much about efficiency, a double loop will do

for (int x = 2; x < 15; x++) {
  cout << "N = " << x << " ";
  for (int y = 2; y <= x; y++)
    cout << fib(y) << " ";
  cout << endl;
}

Upvotes: 1

Related Questions