Copyright (c) Theodore Norvell 2017. Licence: Creative Commons Noncommercial Attribution International 4.0.
This is a Jupyter notebook. See How to use these notes.
Still in the theatre waiting for the movie to start, Alice wonders how many ways there are of putting boys and girls in the 4 seats. (Here we ignore every aspect of a person except whether they are a boy or a girl.) 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.
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
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:
The Fibonnaci sequence has a lot of interesting properties and applications. You can read about some of them in this Wikipedia entry.
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
"""
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.
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]
Before coding, you should check that your design will work. Here is a checklist
Complete the following 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
"""
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.
Below are some tests. After you define the function, you can run these tests and compare the answers with expected answers above.
fib(0) # Expect 0
fib(1) # Expect 1
fib(2) # Expect 1
fib(3) # Expect 2
fib(4) # Expect 3
fib(5) # Expect 5
fib(20) # Expect 6765
Expect the ratio of two successive large Fibonnaci numbers to be roughly the golden ratio 1.618...
fib(31)/fib(30)
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
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)
fibMine(0) # Expect 0
fibMine(1) # Expect 1
fibMine(2) # Expect 1
fibMine(3) # Expect 2
fibMine(4) # Expect 3
fibMine(20) # Expect 6765
fibMine(31)/fibMine(30) # Expect roughly the golden ratio 1.618...
fibMine(-1) # Expect an assertion error.
My solution above is not very efficient. In fact the number of call is makes is typically 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. However, we can use it as the basis for a more efficient solution.
Let's use two accumulators. One carries the value of fib(i) and the other the value of fib(i-1). In order to handle fib(0), it's helpful to define that fib(-1)=1.
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)
fibWithAccumulator(0) # Expect 0
fibWithAccumulator(1) # Expect 1
fibWithAccumulator(2) # Expect 1
fibWithAccumulator(3) # Expect 2
fibWithAccumulator(4) # Expect 3
fibWithAccumulator(20) # Expect 6765
fibWithAccumulator(31)/fibWithAccumulator(30) # Expect roughly the golden ratio 1.618...
fibWithAccumulator(-1) # Expect an assertion error
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
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
iterativeFib( 20 ) # Expect 6765