?
Solved

Help With Recursion

Posted on 2000-03-12
11
Medium Priority
?
269 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 85

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
Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
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 85

Accepted Solution

by:
ozo earned 800 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 85

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 85

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

Industry Leaders: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

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

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…
This is a short and sweet, but (hopefully) to the point article. There seems to be some fundamental misunderstanding about the function prototype for the "main" function in C and C++, more specifically what type this function should return. I see so…
The goal of this video is to provide viewers with basic examples to understand and use structures in the C programming language.
The goal of this video is to provide viewers with basic examples to understand opening and writing to files in the C programming language.

840 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