Solved

# Help With Recursion

Posted on 2000-03-12
257 Views
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
Question by:pipe
• 4
• 4
• 2
• +1

LVL 3

Expert Comment

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

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

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

LVL 3

Expert Comment

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

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

ozo earned 200 total points
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

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

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

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

// 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

Thanks much!
0

## Featured Post

### 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â€¦
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â€¦
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.