Question:
def recur_fibo(n):
"""Recursive function to
print Fibonacci sequence"""
if n <= 1:
return n
else:
return(recur_fibo(n-1) + recur_fibo(n-2))
This code does "simple" recursive fibonacci… Suppose I called:
recur_fibo(33)
recur_fibo(40)
recur_fibo(100)
How to make the calculation be in parallel? I don't want, for example, recur_fibo(100) only be calculated after recur_fibo(40) finishes… I would like an implementation in Python 2 and 3 so I can learn the differences. I still don't understand Threads, so I would like a walkthrough.
Answer:
This implementation is not "true" paralyzable, as well as being a "catastrophe". Yes, you want to know how to calculate different fibonaccis in threads or parallel processes – the answer to that would be a threadpool or processpoll example (hint, look at concurrent.futures) – but I won't touch on that here.
What is not parallelizable is that you cannot have, in the same thread, fibo(10) without having previously calculated fibo(5) – even if your fibo function tells you to calculate fibo(n-1) and fibo(n -2) in separate threads/processes, you will have to wait for both to finish. (and the catastrophe would be even bigger – because threads and processes are MUCH heavier in terms of memory consumption than simple calls)
The implementation works great for didactic purposes, even 10 fibonacci – maybe even 15 – but if you order a 40 fibonacci in it, your computer will crash. From 80 will crash possibly the biggest supercomputer in the world.
That's because you have two function calls inside each fibonacci call. Python, to call a function, creates in memory a new object of type "frame" – (along with an object for each local variable of the function, etc… – in this case it will only be the variable 'n' – but being an integer in Python uses a good 30 bytes – but the frame is about 400 bytes).
Well, if you ask for fibonacci of "3", that's the starting frame, plus the fibo(1) frame, plus the fibo(2) frame – which in turn calls new fibo(1) and fibo(0 ) — there are 5 calls – now realize that if you ask for fibo(5), these 5 calls will be to fibo(3), and 7 more calls to fibo(4) ? That is: the number of function calls you make grows with the SQUARE of the number "n" (what we call O(n²) complexity) – for example, if fibo(5) is going to use 1000 bytes (2*) *10), fibo(10) will already use 2**20 bytes: 1 megabyte and fibo (30) one GB.
The solutions are: Use a cache decorator: functools.lru_cache in your fibonacci – this will make that for any already known value, the function returns immediately, without executing its body (and therefore without two other calls) – that is, to calculate fibo (7), fibo(6) will be called once, but when fibo(5) is called, its value will already be known, and no further calls to the values 4, 3, 2, 1, 0 will be necessary in the branch of (5).
But even better than this is: leave the recursive example to understand recursion on the whiteboard, and write the function interactively – skip away from exponential form.