My lecturer was explaining how the Fibonacci sequence can be displayed for a number
The formula is
Say we had to find the fib for 5 that would be:
fib(5)= fib(5-1) +fib(5-2)
=fib(4) + fib(3)
=fib(2) + fib (-1)?
This is where i get stuck on the sequence, when you hit 1. Do you stop at 1 or keep applying the formula, and if we stop at 1 why?
I am also confused to how we actually reach 5 at the end of the sequence, do we just add up trailing 1s?
Could someone explain the remaining sequence please?
Thanks in advance!
Since i have low reputation, i cant answer my own question so i will post here:
okay so i've worked it out how to do it recursively which gives me a better understanding of how the sequence works! firstly we must use the following recursive algorithm (i have coded in python):
if n==0: return 0 elif n==1 return 1 return (fib(n-1)+fib(n-2))
This is how it goes:
to get to fib (5) you need to work out what fib(4) is:
fib(4) =fib(3) + fib(2)
to find this out you need to work out what fib(3) is:
fib(3) = fib(2) +fib(1)
to find out what fib(3) is you need to find out what fib(2) is:
fib(2) = fib(1)+fib(0)
and we know that fib(1) = 1 because the algorithm states if n=1 return 1.
so now we can work our way back up to find the values:
fib(2) = fib(1)+fib(0) = 1
fib(3) = fib(2) +fib(1) = 1 + 1 = 2
fib(4) =fib(3) + fib(2) = 2 + 1 = 3
now we know what fib (4) and fib(3) is we can work out what fib(5) is:
fib(5) = fib(4) + fib(3) = 3 + 2 = 5
Hope this helped anyone who had the same confusion as me!