Understanding the Fibonacci Sequence

In the Fibonacci sequence, is fib(0) 0 or 1 ?

You're correct. The Fibonacci sequence is formally defined with seed values fib(0) = 0 and fib(1) = 1. This is a requirement for the rest of the sequence to be right (and not offset by one or anything).

In mathematics, the Fibonacci numbers, commonly denoted F_n, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

In mathematics, the Fibonacci numbers, commonly denoted Fn, form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1.

Edit: I have to concede that there is another (much less common, and usually informal) way to define the sequence by seeding it with values 1 and 1, but this is not the conventional one by any means. It is certainly not preferred in all the formal mathematical definitions I’ve seen, like The On-Line Encyclopaedia of Integer Sequences.

Understanding recursion with the Fibonacci Series

When in doubt, just break it down.

The tree flow is actually counter-intuitive to the actual control flow, but once you understand the sequence of calls, it becomes clearer. The thing to understand here is that you keep breaking down a larger computation to a sum of smaller computations, and you stop when you hit the base case (the if statements). Now you can carry out all the small computations, and combining the results of those small computations to form a bigger, larger result, until you have your final answer.

Every time a recursive call hits the base case, it will return either 1, or 0, depending on what case was hit. This value will be returned to the previous caller. To understand, consider:

f(1)3 + f(0)3

Note here that the subscript represents the depth of the recursion call tree. The call is made by f(2)2. f(1)3 is computed first, and 1 is returned to f(2)2. f(0)3 is then computed, and 0 is returned to f(2)2. The two return values are summed, and the result is 1.

f(2)2 then returns 1 to whoever called it, which in this case happens to be f(3)1. f(3)1 called f(2)2 + f(1)2, meanwhile this other f(1)2 also returns 1 to f(3)1, who now adds that with the result of f(2)2, to form 2.

f(3)1 now passes 2 to f(4)0, its caller, which happened to call f(3)1 + f(2)1 ... and so it goes.

---

An alternative way of looking at this is to start from the first function call that is actually made: f(4)0.

f(4)0 computes f(3)1 + f(2)1. But to compute f(3)1, it needs to know f(2)2 + f(1)2, and similarly, to compute f(2)1, it needs to know f(1)2 + f(0)2, and so on.

fibonacci numbers, why does this recurring function work?

A Fibonacci number is defined as the sum of the two preceding Fibonacci numbers. That gives the following:

1 1 2 3 5 8 13 ...

So for the 3rd number (1 1 2) you would take the result of finding the previous - i.e. 2nd (1 1 2) number and add it to the number before the previous - i.e. 1st (1 1 2) number.

You also have to understand that the program needs to calculate the value of the two preceding numbers before it can calculate the number you want to know. Therefore it keeps calling itself - using the same method - until it has calculated everything.

How to write the Fibonacci Sequence?

There is lots of information about the Fibonacci Sequence on wikipedia and on wolfram. A lot more than you may need. Anyway it is a good thing to learn how to use these resources to find (quickly if possible) what you need.

Write Fib sequence formula to infinite

In math, it's given in a recursive form:

In programming, infinite doesn't exist. You can use a recursive form translating the math form directly in your language, for example in Python it becomes:

def F(n):
    if n == 0: return 0
    elif n == 1: return 1
    else: return F(n-1)+F(n-2)

Try it in your favourite language and see that this form requires a lot of time as n gets bigger. In fact, this is O(2ⁿ) in time.

Go on on the sites I linked to you and will see this (on wolfram):

This one is pretty easy to implement and very, very fast to compute, in Python:

from math import sqrt
def F(n):
    return ((1+sqrt(5))**n-(1-sqrt(5))**n)/(2**n*sqrt(5))

An other way to do it is following the definition (from wikipedia):

The first number of the sequence is 0,
the second number is 1, and each
subsequent number is equal to the sum
of the previous two numbers of the
sequence itself, yielding the sequence
0, 1, 1, 2, 3, 5, 8, etc.

If your language supports iterators you may do something like:

def F():
    a,b = 0,1
    while True:
        yield a
        a, b = b, a + b

Display startNumber to endNumber only from Fib sequence.

Once you know how to generate Fibonacci Numbers you just have to cycle trough the numbers and check if they verify the given conditions.

Suppose now you wrote a f(n) that returns the n-th term of the Fibonacci Sequence (like the one with sqrt(5) )

In most languages you can do something like:

def SubFib(startNumber, endNumber):
    n = 0
    cur = f(n)
    while cur <= endNumber:
        if startNumber <= cur:
            print cur
        n += 1
        cur = f(n)

In python I'd use the iterator form and go for:

def SubFib(startNumber, endNumber):
    for cur in F():
        if cur > endNumber: return
        if cur >= startNumber:
            yield cur

for i in SubFib(10, 200):
    print i

My hint is to learn to read what you need. Project Euler (google for it) will train you to do so :P
Good luck and have fun!

Why does the fibonacci recursive sequence work?

In the Fibonacci sequence the first two numbers are zero and one. Every number after these is the sum of the previous 2 numbers. So the first few numbers are

F(0) ≡ 0
F(1) ≡ 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
...
F(n) = F(n - 1) + F(n - 2) ∀ n > 1

Therefore when we calculate a Fibonacci number recursively we have to practice the following logical procedure (in pseudo-code out of respect to StackOverflow).

Integer NthFibonacci(Integer n) {
    if (n < 0) {
        return undefined;
    } else if (n < 2) {
        return n;
    } else {
        return NthFibonacci(n - 1) + NthFibonacci(n - 2);
    }
}

I'm sure you know all this but I think it will help my explanation to have this part as a reference.

Where the Ones and Zeros Come In

The best way to explain this is probably with an example.

Imagine that, as above, we are trying to recursively calculate F(6). Try following the procedure given above. Remember that we will perform recursion only if n > 1.

First we start with F(6) = F(5) + F(4).

Then we find F(5) = F(4) + F(3).

Then we find F(4) = F(3) + F(2).

Then we find F(3) = F(2) + F(1).

Then we find F(2) = F(1) + F(0).

This is where things start to work out!

We have now gotten F(2) in terms of F(1) ≡ 1 and F(0) ≡ 0 (both of which are known), and so we are able to calculate an actual value instead of performing more recursion.

We can now find F(2) = F(1) + F(0) = 1 + 0 = 1.

NOTICE THE 1 AND 0 Those are what people are talking about when they say the whole thing comes down to ones and zeros. Every time we recurse down to find a base value we will end up finding F(2) = 1 + 0. This leads to more ones and zeros as we move back up our recursion tree being able to calculate higher and higher values, as follows.

F(3) = F(2) + F(1) = (1 + 0) + 1
F(4) = F(3) + F(2) = ((1 + 0) + 1) + (1 + 0)
F(5) = F(4) + F(3) = (((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)
F(6) = F(5) + F(4) = ((((1 + 0) + 1) + (1 + 0)) + ((1 + 0) + 1)) + (((1 + 0) + 1) + (1 + 0))

Now if you add up all the 1's you get a sum of 8, and so F(6) = 8, which is correct!

This is how it works, and this is how it breaks down to ones and zeros.

---

Related Topics