Fibonacci numbers
Ok, Im stuck on the logic of this program. I need to find the nth Fibonacci number for any positive integer n that the user entered. What does the nth number mean?? the next Fibonacci number? I also don't understand how this program works. If the user entered 5 then I need it to calculate the previous number so that they can be added together to get the next one. Im trying to figure this out in C++ first then write it into assembly code.
|
|
http://en.wikipedia.org/wiki/Fibonacci_number
The Fibonacci sequence is a sequence of numbers where the next number is sum of the previous two numbers in the sequence. The code above has the first two numbers in the sequence as 0 and 1. n would be the number at the nth position in the sequence. so if n is 1, it's the first number which is 0. if n is 5, it'll be the fifth number in the sequence, or 3.
The code you posted makes recursive calls to the fib function to get the values of the previous numbers in the sequence.
Recursive functions have base cases that define when the recursion stops - this is the if statement in the function. The recursive part in the else section calls the fib function again, decrementing n. As n goes down, it will eventually hit the base case.
So if n is 5...
5 doesn't satisfy the base case, so the return statement calls new fib functions - fib(4) and fib(3). neither of those satisfies the base case, so each of those calls new fib functions, fib(3) and fib(2), and fib(2) and fib(1). This starts to hit the base cases (except fib(3), which will call another fib(2) and fib(1)). The separate fib functions after they hit the base case will return values back up the chain of called fib functions. And you'll get an answer.
It can be confusing to understand recursive functions. It might help to draw out the separate calls on paper.
The Fibonacci sequence is a sequence of numbers where the next number is sum of the previous two numbers in the sequence. The code above has the first two numbers in the sequence as 0 and 1. n would be the number at the nth position in the sequence. so if n is 1, it's the first number which is 0. if n is 5, it'll be the fifth number in the sequence, or 3.
The code you posted makes recursive calls to the fib function to get the values of the previous numbers in the sequence.
Recursive functions have base cases that define when the recursion stops - this is the if statement in the function. The recursive part in the else section calls the fib function again, decrementing n. As n goes down, it will eventually hit the base case.
So if n is 5...
5 doesn't satisfy the base case, so the return statement calls new fib functions - fib(4) and fib(3). neither of those satisfies the base case, so each of those calls new fib functions, fib(3) and fib(2), and fib(2) and fib(1). This starts to hit the base cases (except fib(3), which will call another fib(2) and fib(1)). The separate fib functions after they hit the base case will return values back up the chain of called fib functions. And you'll get an answer.
It can be confusing to understand recursive functions. It might help to draw out the separate calls on paper.
Just in the same way you will be asked what is the nth number in the range of positive numbers, you will say n. How did you know that? You simply added n to 0 and you get your answer. In the same way you are being asked what is the nth Fibonacci number, so you need to say (return) something something.
Fibonacci numbers start with 0 and 1. 0 is the zero(th) Fibonacci number and 1 is the 1st Fibonacci number. The rule states that to get the next Fibonacci number after 0 and 1, you simply return the sum of the previous 2.
There are 2 ways to do this (3 actually but will only talk about 2), one way is the recursive method which you seem to have working and the other method is the non recursive method (iterative). Since you already have the recursive method, I will show how the iterative method works.
You are told to find the nth fibonacci number. First thing you do is set 2 variables to 0 and 1 call them:
These will represent the initial Fibonacci numbers
Next set a counter that will start at 0
Then your loop guard is count < n
At each iteration, you swap the values of prev and next and add prev to next (order matters)
And when the loop ends, return next
What this would look like in pseudo-code:
Fibonacci numbers start with 0 and 1. 0 is the zero(th) Fibonacci number and 1 is the 1st Fibonacci number. The rule states that to get the next Fibonacci number after 0 and 1, you simply return the sum of the previous 2.
There are 2 ways to do this (3 actually but will only talk about 2), one way is the recursive method which you seem to have working and the other method is the non recursive method (iterative). Since you already have the recursive method, I will show how the iterative method works.
You are told to find the nth fibonacci number. First thing you do is set 2 variables to 0 and 1 call them:
int prev = 0, next = 1;These will represent the initial Fibonacci numbers
Next set a counter that will start at 0
int count = 0;Then your loop guard is count < n
At each iteration, you swap the values of prev and next and add prev to next (order matters)
And when the loop ends, return next
What this would look like in pseudo-code:
|
|
Ok so I now understand that this program determines the Fn but what about the value of the Fn? If n=8 then F8=21. So am I supposed to create an algorithm that calculates the value of the 8th place?
Hey just a quick update I figured it out finally on what you guys were saying at 9am this morning. I had to pull a late night last night and nothing was clicking. Heres the final project. Thanks!
|
|
FibSum PROC ; ; Calculates the users input until the nth number is found ; ; Receives: input from user ; Returns: result in eax ;----------------------------------------------- cmp ecx, 1 ;Compares the users input to 1 if it is equal to one then jumps to quit jz L2 mov eax, save mov ebx, result add eax, ebx mov result, eax mov save, ebx dec ecx call FibSum ;calls the FibSum function L2: ret FibSum ENDP END main |
Topic archived. No new replies allowed.