Fibonacci problem

[goncrazybbaksoon]

I have an assignment to write a program that uses less than 10 lines of code to print out the Fibonacci numbers....i.e.1,1,2,3,5,8,13,21,34,55,89,etc....but for the life of me, I can't find the logic on this one. The instructor said I can do it using only two variables, but I just can't seem to get this! Can anyone help?

 

[Zyrenthian]

Well, my guess is that you are currently learning recursion. This seqence can be done this way OR itteratively in a for loop etc. Here are a few hints

// recursive call
Fib is equal to Fib(n-1) + Fib(n-2)

// condition to end loop
Fib( some value <= 1) is 1)


Dont look at it as a problem to write a function to output the sequence. Look at it as a problem to tell you the n'th number

i.e.

Fib(5) = 5
Fib(7) = 13
etc...

Now look at it as a loop such as

for(int i = 1;i<=n;i++)
{
if( i != 1)
cout<<&quot;,&quot;;

cout<<fib(i);
}

the above loop can be put into a function called print sequence which calls the recursive funciton fib. Oh, and if your teacher wants you to write code as concice as possible, read up on ? and :. You can do if conditionals with them and nest them which puts all the code on one line and messes with their head. Just takes some getting used to but it makes the code hard to read. The ? : also returns a value... see the example

example

int min(int x,int y)
{
return (x<y ? x:y);
}

without ?:

int min(int x,int y)
{
if( x<y)
return x;
else
return y;
}

which can then be shortend into

int min(int x,int y)
{
if(x<y)
return x;
return y;
}

Just my 2 cents

Matt

 

[lionelhill]

people always and rightly learn recursion, and Fibonacci numbers are a standard example: Zyrenthian is right in everything he says.

But beware of recursion. It is very useful in its place but it has a down-side too. Every time you call a function recursively all the data that function is using, together with return addresses and bits and pieces the processor needs to resume that function after the function call, get stuffed on the stack. And the stack is not endless.
Recursive methods tend to be good provided you don't make a deep tree of recursive calls. Chess search engines work very well recursively because the tree is probably only 3 to 20 calls or so deep at most, but may be 100's of thousands of positions wide. If you calculate x! recursively, though, you are going to get in a terrible pickle by about x=500

Also all that stack creation takes time. &quot;Code recursion&quot; where you call the function from within itself, is time-consuming, and if you can possibly put all the relevant data in some sort of structure maintained within the function, and do all the looping there (&quot;data recursion&quot things will be a lot, lot quicker.

The trouble with recursion is it looks so neat there's a tendancy to use it everywhere, without thinking about what goes on underneath the surface. Use it where you have to, not just because it looks pretty.

As regards your original question, each Fibonacci number is a sum of two previous numbers, so clearly you need to keep track of two numbers (hence your teacher's need for 2 variables). The thing that's not clear to me is how your teacher manages it without a third storage-item of some sort (variable, whatever) to keep track of what n the latest fibonacci number is. (like, is this the third, fourth, or nth). Please can I have 3 variables!

 

[goncrazybbaksoon]

Yes, it's a recursive example, and yes, there are three variables....I thought the nth variable was implied. I tried to follow what Zyrentian had offered, but am lost. Still trying though, any more info you could offer would be helpful!

 

[Zyrenthian]

ok... how bout this. This is an example of recursion to compute factorials

int factorial(unsigned int value)
{
if(value)
return value * factorial(value-1);
return 1;
}

please notice the UNSIGNED part. That means no negative numbers will be coming in. However, as mentioned above, large numbers passed to recursion can be bad. you know the condition stated above in my original post and the basis of the recursion is listed there as well. First, work on computing the n'th fibonacci number. When you can do that, it is all down hill


Matt

 

[lionelhill]

This message has 2 parts:
(1) explanation of using recursion for Fibonacci, and
(2) why in practice this is a hideously bad idea!


(1)
You know the first fibonacci number, that's defined.
You also know the second fibonacci number, that is also part of the definition.
So the problem is to calculate any of the others; the real stuff kicks in with the third fibonacci number.

First you need to make your (soon to be recursive) function deal with the first two numbers, which are special cases: just return the right output if you've been given the right input.

Now deal with number 3.
What is number 3... it's the sum of numbers one and two.
So you are looking to add two other numbers, which are actually results you could get by calling your own routine! Ha! the very thing you are writing at the moment!
So for case number 3, make your routine return the sum of the calls to itself.
But of course it would be nice to be able to deal with case number 4, 5, 6 etc....
so rather than calling a &quot;hard wired&quot; version of fibonacci(3) which sums the values for 1 and 2, we want a general version that sums the relevant 2 fibonacci numbers to make the new one.
This is where the recursion works.

Recursion to generate the answer for func based on calls to func(n-something) is analogous to proving a theorem for case 1 (a nice easy special one), and proving that if theorem(x) is true then theorem (x+1) is true, and therefore every case greater than 1 is true.
i.e. you've made Fibonacci work for 1, 2, and on that basis it works for 3 because it only needs the values 1 and 2 positions to the left on the number line. Therefore it applies to all values from 3 upwards....

(2) But in this case recursion is EVIL, BAD, and shouldn't be done, no way, never!
In addition to the stack thing, because you are using the last 2 Fibonacci numbers to generate a new one (at least if you use what I've described above), each call to fibonacci causes TWO more new calls. This is an exponentially increasing binary tree.
They don't have to be in memory at the same time, so the stack-disaster isn't as bad as it might be, but they do have to be executed. This makes recursion one of the slowest imaginable ways to calculate a simple value in this case.
Just imagine how many calls to fibonacci you are going to make merely to calculate the 10th number! It is depressing....

 

[rossno]

ref:

http://www.deitel.com

&quot;C++ How To Program&quot; ... but don't just copy it and say &quot;I'm done&quot;. L E A R N I T ! ! As noted above, the practical use of recursion is VERY limited, but what you are REALLY learning here, is how to entangle your brain in recursion, then survive (mentally) the unwinding process as the stack unwinds to produce the final result.

// Fig. 3.15: fig03_15.cpp
// Recursive fibonacci function.
#include <iostream>

using std::cout;
using std::cin;
using std::endl;

unsigned long fibonacci( unsigned long ); // function prototype

int main()
{
unsigned long result, number;

// obtain integer from user
cout << &quot;Enter an integer: &quot;;
cin >> number;

// calculate fibonacci value for number input by user
result = fibonacci( number );

// display result
cout << &quot;Fibonacci(&quot; << number << &quot = &quot; << result << endl;

return 0; // indicates successful termination

} // end main

// recursive definition of function fibonacci
unsigned long fibonacci( unsigned long n )
{
// base case
if ( n == 0 || n == 1 )
return n;

// recursive step
else
return fibonacci( n - 1 ) + fibonacci( n - 2 );

} // end function fibonacci


/**************************************************************************
* (C) Copyright 1992-2003 by Deitel & Associates, Inc. and Prentice *
* Hall. All Rights Reserved. *
* *
* DISCLAIMER: The authors and publisher of this book have used their *
* best efforts in preparing the book. These efforts include the *
* development, research, and testing of the theories and programs *
* to determine their effectiveness. The authors and publisher make *
* no warranty of any kind, expressed or implied, with regard to these *
* programs or to the documentation contained in these books. The authors *
* and publisher shall not be liable in any event for incidental or *
* consequential damages in connection with, or arising out of, the *
* furnishing, performance, or use of these programs. *
*************************************************************************/

 

[lionelhill]

Yes, please don't copy it. Rossno is right, the learning content is what's important. And I don't want to live next door to the nuclear power station whose safety system you've worked on if you didn't work out your exercises yourself!

 

[goncrazybbaksoon]

Thank you all for your help! I finally came up with a solution, thought I'd put it on here for you to critique...

int Fib(int firstvalue, int secondvalue, int ival);

void main()
{
int firstnum=1; //first number of fibonacci scale
int secondnum=1; //second number of fibonacci scale
int z = firstnum+secondnum; //sum first+second number

int ival=0; //the value the user wishes the scale to stop at

cout<<&quot;Please enter an ending number: &quot;<<endl;
cin>>ival;
cout<<endl<<endl;

if (z<ival)
{
cout<<firstnum<<endl;
cout<<secondnum<<endl;
Fib(firstnum, secondnum, ival);
}

return;
}

int Fib(int firstvalue, int secondvalue, int ival)
{
int z=firstvalue+secondvalue; //total of last 2 numbers

if (z<ival+1)
{
cout<<z<<endl;
Fib(secondvalue, z, ival);
}
return z;
}

 

[lionelhill]

Just at a glance, one thing I really like is the way you've thought about passing your fibonacci function the last 2 values, so all it needs to do is add them, and call itself ONCE with the values shifted along one.
This has the downside that your central fib function doesn't actually behave how ideally I'd like [ideally I want a function that returns the nth Fibonacci number when I call it as fibonacci] BUT, it means your version will run like greased lightening compared to the published version above. And it's not difficult to add an adaptor-function that starts your function off on its recursive chase after an answer, and dresses it up to look like my ideal fibonacci function.

The next step I suppose would be to scrap code recursion altogether and do something like (pseudocode)

a = 1
b = 1
n is the Fibonacci number we want
while n > 2 do
{ save &quot;b&quot; in a spare variable x (i.e. x=b)
b = a + b
retrieve old &quot;b&quot; and set a = old &quot;b&quot; (i.e. a=x)
n = n - 1
}

This code maintains the last 2 Fibonacci numbers in a and b, and uses them to find the next two each loop.

All that we've done here is keep the two numbers you pass to fib within the function, and do all the adding there, instead of calling a recursive function. OK, we end up needing more than 2 variables (because we need to recalculate b and a and need to keep the old value of one of them for this purpose) - but actually we're using a lot less of the computer's storage than we would doing recursion, because we aren't setting up a whole long string of local variables on the stack....

If I'm writing rubbish, someone let me know.

 

[tokra]

I would point out there is an iterative solution
This is based off of a partial implementation of a solution to swap the values of two variables without the use of a third.

int main()
{
int i=0;
int j=1;
while (true)
{
j+=i; //next number in the series
i=j-i;
//To complete the swap would be j-=i;
cout << i; //use i instead of j so the first two values output correctly
}
return 0;//kinda pointless considering we're in an infinite loop but it's form.
}

I don't have access to a compiler right now so I apologize if it doesn't behave perfectly first time through. WR