Before we part from this chapter, I'll show you a simple problem that I submitted to candidates for a Python developer role in a company I used to work for.
The problem is the following: given the sequence 0 1 1 2 3 5 8 13 21 ...
write a function that would return the terms of this sequence up to some limit N
.
If you haven't recognized it, that is the Fibonacci sequence, which is defined as F(0) = 0, F(1) = 1 and, for any n > 1, F(n) = F(n-1) + F(n-2). This sequence is excellent to test knowledge about recursion, memoization techniques and other technical details, but in this case it was a good opportunity to check whether the candidate knew about generators (and too many so called Python coders didn't, when I was interviewing them).
Let's start from a rudimentary version of a function, and then improve on it:
fibonacci.first.py
def fibonacci(N):
"""Return all fibonacci numbers up to N. """
result = [0]
next_n = 1
while next_n <= N:
result.append(next_n)
next_n = sum(result[-2:])
return result
print(fibonacci(0)) # [0]
print(fibonacci(1)) # [0, 1, 1]
print(fibonacci(50)) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
From the top: we set up the result
list to a starting value of [0]
. Then we start the iteration from the next element (next_n
), which is 1
. While the next element is not greater than N
, we keep appending it to the list and calculating the next. We calculate the next element by taking a slice of the last two elements in the result
list and passing it to the sum
function. Add some print
statements here and there if this is not clear to you, but by now I would expect it not to be an issue.
When the condition of the while
loop evaluates to False
, we exit the loop and return result
. You can see the result of those print
statements in the comments next to each of them.
At this point, I would ask the candidate the following question: "What if I just wanted to iterate over those numbers?" A good candidate would then change the code like the next listing (an excellent candidate would have started with it!):
fibonacci.second.py
def fibonacci(N): """Return all fibonacci numbers up to N. """ yield 0 if N == 0: return a = 0 b = 1 while b <= N: yield b a, b = b, a + b print(list(fibonacci(0))) # [0] print(list(fibonacci(1))) # [0, 1, 1] print(list(fibonacci(50))) # [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]
This is actually one of the solutions I was given. I don't know why I kept it, but I'm glad I did so I can show it to you. Now, the fibonacci
function is a generator function. First we yield 0
, then if N
is 0
we return (this will cause a StopIteration
exception to be raised). If that's not the case, we start iterating, yielding b
at every loop cycle, and then updating a
and b
. All we need in order to be able to produce the next element of the sequence is the past two: a
and b
, respectively.
This code is much better, has a lighter memory footprint and all we have to do to get a list of Fibonacci numbers is to wrap the call with list()
, as usual.
But what about elegance? I cannot leave the code like that. It was decent for an interview, where the focus is more on functionality than elegance, but here I'd like to show you a nicer version:
fibonacci.elegant.py
def fibonacci(N): """Return all fibonacci numbers up to N. """ a, b = 0, 1 while a <= N: yield a a, b = b, a + b
Much better. The whole body of the function is four lines, five if you count the docstring. Notice how in this case using tuple assignment (a, b = 0, 1
and a, b = b, a + b
) helps in making the code shorter, and more readable. It's one of the features of Python I like a lot.