Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.

This is a Jupyter notebook. See How to use these notes.

UP TO THE TABLE OF CONTENTS

Fibonnaci

The problem

Still in the theatre waiting for the movie to start, Alice wonders how many ways there are of putting people in the 4 seats. For 0 seats, there is only one way { [] } (the empty sequence). If there is one seat, we have two ways {B, G}. If there are two seats, there are 4 ways {BB, BG, GB, GG}. If there are 3 seats there are 8 ways {BBB, BBG, BGB, BGG, GBB, GBG, GGB, GGG} and so on. Clearly if there are n seats there are $2^n$ ways.

But, the boys never want to sit next to other boys, so she wonders how many ways you can fill 4 seats with boys and girls so that there are never two boys next to each other.

A generalization

In general, the problem is how many ways are there of seating boys and girls in $n$ seats such that two boys never sit next to each other.

Alice makes a table

n arrangements count(n)
0 {[]} 1
1 {B, G} 2
2 {BG, GB, GG} 3
3 {BGB, BGG, GBG, GGB, GGG} 5
4 {BGBG, BGGB, BGGG, GBGB, GBGG, GGBG, GGGB, GGGG} 8

She notices that each number --after the first two-- is the sum of the two previous numbers. (Why is that?) The function from n to count(n) can be completely defined by three equations

  1. $count(0) = 1$
  2. $count(1) = 2$
  3. $count(n) = count(n-1) + count(n-2)$ for all $n$, $n > 1$

Bill points out that the count function related to the famous Fibonnaci function

n fib(n)
0 0
1 1
2 1
3 2
4 3
5 5
6 8
7 13

in that $count(n) = fib(n+2)$ for all natural $n$.

The Fiboannaci function has the same property: After the first two items, each item is the sum of the previous two. It is defined by three equations:

  1. $fib(0) = 0$
  2. $fib(1) = 1$
  3. $fib(n) = fib(n-1) + fib(n-2)$ for all $n$, $n > 1$

The Fibonnaci sequence has a lot of interesting properties and applications. You can read about some of them in this Wikipedia entry.

A contract

We write a contract for the fib function.

def fib( n ):
        """Pre: n is a natural number
           Post: result == the value of the fibonnaci function for n where
           this function is defined by the following three equations
           1. fib(0) = 0
           2. fib(1) = 1
           3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
        """

Problem Analysis

All the problem analysis we need is already done. That's because the definition of the Fibonnaci function is already in a recursive form, so implementing the contract recursively is just a matter of translating the contract into code.

Your solution

Design

Based on the problem analysis, we can write a design in pseudocode. In this case the pseudocode will look a lot like Python, so you can take this step if you want, or skip it if you don't.

[Put your pseudocode here]

Analyze design

Before coding, you should check that your design will work. Here is a checklist

  • Is every case allowed by the precondition covered?
  • Does the code do the right thing (i.e. return a result allowed by the postcondition) in each case?
  • Is every recursive call smaller in some sense than its parent call?

Code

Complete the following function

In [1]:
def fib( n ):
    """
    Pre: n is a natural number
    Post: result == the value of the fibonnaci function for n where
    this function is defined by the following three equations
        1. fib(0) = 0
        2. fib(1) = 1
        3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
    """

Analyze code

If you wrote pseudocode, check that your design is consistant with the pseudocode. If you didn't write pseudocode, use the checklist above to check your code.

Test

Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.

In [2]:
fib(0)  # Expect 0
In [3]:
fib(1)  # Expect 1
In [4]:
fib(2)  # Expect 1
In [5]:
fib(3)  # Expect 2
In [6]:
fib(4)  # Expect 3
In [7]:
fib(5)  # Expect 5
In [8]:
fib(20)   # Expect 6765

Expect the ratio of two successive large Fibonnaci numbers to be roughly the golden ratio 1.618...

In [9]:
fib(31)/fib(30)
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-9-ef4ef34fb191> in <module>()
----> 1 fib(31)/fib(30)

TypeError: unsupported operand type(s) for /: 'NoneType' and 'NoneType'

My Solution

Design

Here is pseudo code

function $fib( n : nat )$

pre true
post result = the value of the fibonnaci function for $n$ where this function is defined by the following three equations

$fib(0) = 0$
$fib(1) = 1$
$fib(n) = fib(n-1) + fib(n-2)$, for all $n$ such that $n > 1$

if $n = 0$ then 1
| $n = 1$ then 1
| $n > 1$ then fib(n-1) + fib(n-2)
end if

Code

In [12]:
def fibMine( n ):
    """
    Pre: n is a natural number
    Post: result == the value of the fibonnaci function for n where
    this function is defined by the following three equations
        1. fib(0) = 0
        2. fib(1) = 1
        3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
    """
    assert isinstance(n, int) and n >= 0
    if n == 0: return 0
    elif n==1 : return 1
    else: return fibMine(n-1) + fibMine(n-2)

Test

In [13]:
fibMine(0)  # Expect 0
Out[13]:
0
In [14]:
fibMine(1)  # Expect 1
Out[14]:
1
In [15]:
fibMine(2)  # Expect 1
Out[15]:
1
In [16]:
fibMine(3)  # Expect 2
Out[16]:
2
In [17]:
fibMine(4)  # Expect 3
Out[17]:
3
In [18]:
fibMine(20)  # Expect 6765
Out[18]:
6765
In [19]:
fibMine(31)/fibMine(30) # Expect roughly the golden ratio 1.618...
Out[19]:
1.6180339887505408
In [20]:
fibMine(-1)  # Expect an assertion error.
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-20-755210da7f13> in <module>()
----> 1 fibMine(-1)  # Expect an assertion error.

<ipython-input-12-f5cc79bf02a2> in fibMine(n)
      8         3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
      9     """
---> 10     assert isinstance(n, int) and n >= 0
     11     if n == 0: return 0
     12     elif n==1 : return 1

AssertionError: 

Going further

My solution above is not very efficient. In fact the number of call is makes is typicall bigger than its result. For example computing fibMine(5) takes 8 calls and computing fibMine(20) takes over 21,000 function calls!

Despite its popularity for illustrating recursion, the straight forward way of using recursion to compute the Fibonnaci function is actually terribly inefficient.

Let's use two accumulators. One carries the value of fib(i) and the other the value of fib(i-1).

In [21]:
def fibWithAccumulator( n ) :
    """
    Pre: n is a natural number
    Post: result == the value of the fibonnaci function for n where
    this function is defined by the following three equations
        1. fib(0) = 0
        2. fib(1) = 1
        3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
    """
    assert isinstance(n, int) and n >= 0
    return fibWithAccumulatorHelper( 0, n, 1, 0 )

def fibWithAccumulatorHelper( i, n, a, b):
    """
    Pre n is a natural number
        i is a natural number in {0,..,n}
        a is fib(i-1)
        b is fib(i)
    Post: result == the value of the fibonnaci function for n where
    this function is defined by the following four equations
        0. fib(-1) = 1
        1. fib(0) = 0
        2. fib(1) = 1
        3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
    """
    if i==n : return b
    else: return fibWithAccumulatorHelper( i+1, n, a+b, a)
    

Testing

In [22]:
fibWithAccumulator(0)  # Expect 0
Out[22]:
0
In [23]:
fibWithAccumulator(1)  # Expect 1
Out[23]:
1
In [24]:
fibWithAccumulator(2)  # Expect 1
Out[24]:
1
In [25]:
fibWithAccumulator(3)  # Expect 2
Out[25]:
2
In [26]:
fibWithAccumulator(4)  # Expect 3
Out[26]:
3
In [27]:
fibWithAccumulator(20)  # Expect 6765
Out[27]:
6765
In [28]:
fibWithAccumulator(31)/fibWithAccumulator(30) # Expect roughly the golden ratio 1.618...
Out[28]:
1.6180339887505408
In [29]:
fibWithAccumulator(-1) # Expect an assertion error
---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
<ipython-input-29-26d0d4563612> in <module>()
----> 1 fibWithAccumulator(-1) # Expect an assertion error

<ipython-input-21-3666865d405a> in fibWithAccumulator(n)
      8         3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
      9     """
---> 10     assert isinstance(n, int) and n >= 0
     11     return fibWithAccumulatorHelper( 0, n, 1, 0 )
     12 

AssertionError: 

We can make this slightly more efficient by using tail recursion optimization and inlining. I won't go into the details, but the result is this function

In [30]:
def iterativeFib( n ) :
    """
    Pre: n is a natural number
    Post: result == the value of the fibonnaci function for n where
    this function is defined by the following three equations
        1. fib(0) = 0
        2. fib(1) = 1
        3. fib(n) = fib(n-1) + fib(n-2) for all n,  n > 1
    """
    assert isinstance(n, int) and n >= 0
    i, a, b = 0, 1, 0
    #invariant: 0 <= i and i <= n and a = fib(i-1) and b = fib(i)
    while i < n:
        i, a, b = i+1, b, a+b
    return b
In [31]:
iterativeFib( 20 )   # Expect 6765
Out[31]:
6765