Solved

Help With Recursion

Posted on 2000-03-12
11
257 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
Comment Utility
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
Comment Utility

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
Comment Utility
int PrintFib( int n ){
  if( n >= 2 ){
    n = PrintFib(n-1) + CalcFib(n-2);
  }
  cout << n << endl;
  return n;
}
0
 
LVL 3

Expert Comment

by:arnond
Comment Utility
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
Comment Utility
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
Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

 
LVL 84

Accepted Solution

by:
ozo earned 200 total points
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
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
Comment Utility
// 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
Comment Utility
Thanks much!
0

Featured Post

Why You Should Analyze Threat Actor TTPs

After years of analyzing threat actor behavior, it’s become clear that at any given time there are specific tactics, techniques, and procedures (TTPs) that are particularly prevalent. By analyzing and understanding these TTPs, you can dramatically enhance your security program.

Join & Write a Comment

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…
Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
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 opening and reading files in the C programming language.

744 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

Need Help in Real-Time?

Connect with top rated Experts

11 Experts available now in Live!

Get 1:1 Help Now