Curious about the Fibonacci sequence...

Alrighty, so: I've been asked to create a world where a character calculates the nth Fibonacci number.

Now, I'm fairly proficient with Alice at this point, having only been introduced to it three months ago, and I understand the Fibonacci sequence, how each new number is the sum of the last two, ad infinitum.

Clearly recursion is going to play into making this world work, but I am unsure at this point if "calculating the nth Fibonacci number" requires input from the user. That is, should the character continue calculating each new term until either a) the user tells it to stop, or b) Alice's mathematical limits have been reached, or should the user be asked to give two numbers, and go from there? I am a bit perplexed.

Any additional hints on how to go about programming the calculation sequence properly and efficiently would be greatly appreciated!

Thanks in advance!

I would ask the user for any integer >= 0, Let's call it "N".

Then Print the "NTH" Fibonacci term so like this:


Print Fibonacci (N)
***************************

Fibonacci(N){
If N= 0
return 0
If N=1
return 1
else
return Fibonacci(N-1) + Fibonacci(N-2)

}

Hmm, I see. Now, I'm still using the object-oriented version of Alice, where everything is essentially drag-and-drop; so are you suggesting that I creat a function wherein the user is asked for a single integer, higher than 0, and if that integer is 1, to return 1, but if it is higher, to return a value that is the sum of the given integer -1 and the given integer -2?

No return the sum of Fibonacci(N-1) and Fibonacci(n-2)

Fibonacci is a function which returns an integer value. That looks like this:

Fibonacci(N){
If N= 0
return 0
If N=1
return 1
else
return Fibonacci(N-1) + Fibonacci(N-2)

}

I guess I'm still a little confused here. Maybe my understanding of Fibonacci is not what I thought it was. Perhaps some clarification? The Fibonacci numbers are a set number of values, correct? That is, it begins with 1, or even 0, and continues on with 1, 2, 3, 5, 8, 13, 21, 34, and so on? If so, is the first 1 the first "nth" value, with the second 1 being the second "nth", the 2 the third, etc.? And if this is the case, if I were to ask the user to input a value, would that value then have to be 0, or 1, in order to calculate properly?

The code that you suggested, scarlet, I guess I am still unsure a) how it works, and b) how to implement it into the drag-and-drop environment of Alice.

Anyone who can offer any kind of help, it would be greatly appreciated, I'm not sure why I'm having such a hard time here.

I think I am in your class and I am having the same problems. I can get it to calculate the Nth number and add the previous 2 before it. Basically if i enter 9, i will get 8+7=15 but I believe he's asking us to calculate that position in the sequence. Now, if this was another language I could just code that, but I don't see how we can set the sequence in the program. It just makes no sense to me. I am also using the object oriented version of Alice so if anyone can help that would be great!

Hahaha, yes I am having the exact same issue! I feel as though there must have been a class that I missed wherein he talked more specifically about Fibonacci, because as I recall, he mentioned it once briefly in class, but never elaborated. Regardless, I've done a lot of researching about the sequence, and how to go about calculating it; it's just like you said, in almost any other language, it would be quite simple to program, but I just CAN'T seem to get it in Alice. Heh, it's good to know that someone else is having the same problem. I've basically at this point decided to just take a loss on some of my mark for the assignment. It's stressing me out too much, ha.

As a starting disclaimer, I personally dislike the Fibonacci example - for exactly the reasons leading to this discussion - so this bias will probably show through. As LanceA has pointed out, however, the issues are covered in the AP exam and so have to be learned if you are taking that exam. (Also a better mathematician may take exception to the level of rigor of this discussion - please if you do, post a better one.)

The true Fibonacci sequence has to use the generating formula Fn = Fn-1 + Fn-2 and start with 1,1, … Thus the third number in the sequence is 2, the fourth 3, the fifth 5, etc. You can use same approach with any two starting numbers to generate a similar sequence, but it will give a different sequence of actual numbers.

In a recursive calculation, the starting pair is a bit hidden (lines 2-5 in Scarlet's code, for example) since what that pair does there is stop the sequence of recursive calls. This leads to the oddball (IMO) call to needed to calculate Fibonacci(0) when the idea of a "0th" number of a sequence is really undefined.

Notes:

The best reference I have found is http://en.wikipedia.org/wiki/Fibonnaci_numbers , though it is not at all "watered down" and is a bit difficult to follow. It does give (non-recursive) methods for calculating just a single number in the sequence.

For Alice recursive code to calculate the sequence, see http://www.alice.org/community/showt...ight=Fibonacci .

Dr. Jim:

I've spent quite a bit of time on that Wikipedia article, re-reading it over and over in attempt to absorb some relevancy from it that I could actually apply to Alice, but of course being the programming noob that I am, I was unsuccessful. :P

Now, I took a look at LanceA's post, and your reply. I downloaded the Fibonacci world and studied it, but I'm curious - that particular code does not calculate the "nth" number, does it? It simply generates the Fibonacci number that includes the value the user enters, correct? Or is that what is considered as the "nth" number?

Thank you so much for your response, I was hoping I would hear from you in time.

That question actually came from a textbook by Joel Adams, ALICE IN ACTION. It was meant to demonstrate Recursive methods in ALICE.

Personally, I disagree with recursion as it leads to stack overflows, etc. but the Computer Science AP folks love it! Allthough I'm not sure most of them understand it's inefficiency.

It does make for good questions on an exam!

Good luck,