Hands-on: Using C-functions

The code for this exercise is located under cython/c-functions.

Fibonacci numbers are a sequence of integers defined by the recurrence
relation

F_n = F_n-1 + F_n-2

with the initial values F₀=0, F₁=1.

The module fib.py contains a function fibonacci(n) that
calculates recursively F_n. The function can be used e.g. as

from fib import fibonacci

fibonacci(30)

Make a Cython version of the module, and investigate how adding type
information and making fibonacci a C-function affects performance
(hint: function needs to be called both from Python and C). Use
timeit for performance measurements, either from command line

$ python3 -m timeit -s "from fib import fibonacci" "fibonacci(30)"

or within IPython

In []: %timeit fibonacci(30)

Note: this recursive algorithm is very inefficient way of calculating Fibonacci numbers.

How much speedup are you are able to get by using Cython? Are you able to come up with more efficient pure Python algortihm? Please comment!