Solved

Help With Recursion

Posted on 2000-03-12
11
263 Views
Last Modified: 2010-04-02
Hello,
  How can I modify my program below to print out the Fibanocci numbers in the Function "CalcFib" as it goes along, rather than just print the last number in the sequence. Right now my program will print out "2" because it is the 3rd Fib number. However, in this case I would want the "CalcFib" function to print out 0,1,1,2; rather than print out the last Fib number from the main function.

Thanks,
  P

#include "stdafx.h"


#include <iostream.h>

int CalcFib( int n ){

      if (n < 2){
            return n;
      }
      else{
        return CalcFib(n-1) + CalcFib(n-2);
      }

}


int main(int argc, char* argv[]){

    cout << CalcFib( 3 ) << endl;

      return 0;
}
0
Comment
Question by:pipe
  • 4
  • 4
  • 2
  • +1
11 Comments
 
LVL 3

Expert Comment

by:arnond
ID: 2609783
OK, this should work:
--------------------------------------------
#include "stdafx.h"

#include <iostream.h>

int CalcFib( int n ){
   int ret;
   if (n < 2){
   cout << n << endl;
   return n;
   }
   else{
   ret = CalcFib(n-1) + CalcFib(n-2);
   cout << ret << endl;
   return (ret);
  }
}


int main(int argc, char* argv[]){

  CalcFib( 3 );

  return 0;
}

--------------------------------------------------

Hope this helps,
Arnon David.
0
 

Author Comment

by:pipe
ID: 2609888

Yea, I had something simliar to this, however, for example if I call CalcFib( 4 ) this will produce

1
0 *
1 *
1 *
2 *
1
0
1
3 *

instead of 0, 1, 1, 2, 3. The stars represent the Fib number and everything else is the build up of these numbers. I need a way to weed out the numbers that are not Fib. I have found serveral other ways to do this, but not with recursion.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2609973
int PrintFib( int n ){
  if( n >= 2 ){
    n = PrintFib(n-1) + CalcFib(n-2);
  }
  cout << n << endl;
  return n;
}
0
Best Practices: Disaster Recovery Testing

Besides backup, any IT division should have a disaster recovery plan. You will find a few tips below relating to the development of such a plan and to what issues one should pay special attention in the course of backup planning.

 
LVL 3

Expert Comment

by:arnond
ID: 2610023
Second go:
-----------------------------------------------
#include "stdafx.h"

#include <iostream.h>

int CalcFab(int n)
{
  if (n<2)
    return (n);
  else
    return CalcFab(n-1)+CalcFab(n-2);
}

int main (int argc, cahr* argv[])
{
  int i;
  for (i=0;i<20;i++)
  {
    cout<<CalcFab(i)<<endl;
  }
  return (0);
}

-----------------------------------------------

OK, so it's a bit off, but it gets the job done with little work.

Arnon David.

BTW, It still uses recursion.....
0
 

Author Comment

by:pipe
ID: 2610038
Thanks arnod. I can see it still uses the recursion in the CalcFib function, however, I am trying to do all of the work in this function and not use a for loop in main. Ozo's solution was the same as yours and mine and still produces all the unwanted numbers. There has got to be some way to do this, but I am completely stumped.
0
 
LVL 84

Accepted Solution

by:
ozo earned 200 total points
ID: 2610060
int CalcFib( int n ){

if (n < 2){
return n;
}
else{
  return CalcFib(n-1) + CalcFib(n-2);
}

}
int PrintFib( int n ){
  if( n >= 2 ){
    n = PrintFib(n-1) + CalcFib(n-2);
  }
  cout << n << endl;
  return n;
}
0
 
LVL 12

Expert Comment

by:pjknibbs
ID: 2610062
Why don't you want to use a FOR loop in main? It would be far more efficient if you want to print the entire sequence of Fibonacci numbers. Doing it recursively like this means CalcFib() has to recalculate all the lower-order numbers before it can print the higher ones.
0
 

Author Comment

by:pipe
ID: 2610072
Ah..I see what you were thinking now.  Maybe it is not possible to do it in one function. I am not concerned with the effiency of it. I just found this exercise in an old book, but they didn't print a solution. I thought it would be trival when I started doing it, but I guees not. Thanks.
0
 
LVL 84

Expert Comment

by:ozo
ID: 2610528
int CalcFib( int n ){
  if( n <= -2 ){
    n = CalcFib(n+1) + CalcFib(n+2);
  }else if( n >= 2 ){
    n = CalcFib(n-1) - CalcFib(2-n);
  }
  if( n > 0 ){ cout << n << endl; }
  return n;
}
0
 
LVL 84

Expert Comment

by:ozo
ID: 2610581
// Or more efficiently
int PrintFib( int n, int a, int b ){
   cout << a << endl;
   if( n == 0 ){
       return a;
   }else{
       return PrintFib(n-1,b,a+b);
   }
}
int main(int argc, char* argv[]){

  PrintFib(3,0,1);

  return 0;
}
0
 

Author Comment

by:pipe
ID: 2610788
Thanks much!
0

Featured Post

How our DevOps Teams Maximize Uptime

Our Dev teams are like yours. They’re continually cranking out code for new features/bugs fixes, testing, deploying, responding to production monitoring events and more. It’s complex. So, we thought you’d like to see what’s working for us. Read the use case whitepaper.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

An Outlet in Cocoa is a persistent reference to a GUI control; it connects a property (a variable) to a control.  For example, it is common to create an Outlet for the text field GUI control and change the text that appears in this field via that Ou…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use nested-loops in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

792 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question