 |
| Fibonacci, Leonardo da Pisa (Wikipedia) |
Preamble
The Fibonacci sequence $F_{n} = F_{n-1} + F_{n-2}$ is famous for both artistic and pure mathematical curiosity as an integer sequence. A simple implementation of this sequence appears as a standard programmer's entry-level job question, along with finding factorial and greatest common divisor. In this short post, we will show how to implement $F_{n}$ with recursion in Python one-liner.
Fibonacci Recursion in Python
Here is a one-liner
f = lambda n : n if n < 2 else f(n-1)+f(n-2) ; [f(n) for n in range(0,13)]
Let's dissect the one line. $f$ is our function that computes the $nth$ member of the sequence in a recursive fashion.
For example, a recursion of $f$ at $n=3$ follows the following depth as recursive calls:
- Upper level, n=3 : f(2)+f(1)
- n=2 : f(1) + f(0)
- Returns 1+0 = 1
- n=1 : f(1)
- Returns 1
- Returns 2
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144]Computational efficiency
To compute the sequence for a very large set, this implementation is obviously very slow. One would need to introduce caching within the recursion to avoid repeated computation.
Reading list for novice coders
- List comprehension originating from set builder notation.
- Lambda expressions so-called anonymous functions.
- Recursion, it is a beautiful concept in computer science.
- Range function in Python.
Conclusion
One of the most interesting programming tasks usually comes in implementing integer sequences. Note that Fibonacci day is celebrated on 23rd of November, the day this post is published.
Postscript: Time complexity, memoization version with timings
The complexity of 1 liner code above is $O(2^N)$, with caching it can be $O(N)$. Thanks to Tim Scarfe for pointing out Big-O complexities. The solution is to introduce caching, this is so-called memoization.
The following gives timing for $m=35$ without and with memoization. It is seen that memoization is almost 5 orders of magnitude faster and will actually memory efficient as well. For larger $m$ memoization version may return a value but without memoization, we would quickly overflow on recursive calls.
Postscript: Time complexity, memoization version with timings
The complexity of 1 liner code above is $O(2^N)$, with caching it can be $O(N)$. Thanks to Tim Scarfe for pointing out Big-O complexities. The solution is to introduce caching, this is so-called memoization.
The following gives timing for $m=35$ without and with memoization. It is seen that memoization is almost 5 orders of magnitude faster and will actually memory efficient as well. For larger $m$ memoization version may return a value but without memoization, we would quickly overflow on recursive calls.
import time m = 35 # no memoization t0 = time.process_time() f = lambda n : n if n < 2 else f(n-1)+f(n-2) ; sfib = [f(i) for i in range(1,m)] time.process_time() - t0 # memoization t0 = time.process_time() mem={1:1,2:2} ; f = lambda n : n if n < 2 else mem.get(n) if mem.get(n) else mem.update({n:f(n-1)+f(n-2)}) ; sfib_mem = [f(i) for i in range(1,m)]; sfib_mem = [1]+list(mem.values()) time.process_time() - t0