After seeing this problem, and being a developer gradually falling in love with Python (or falling in love-hate with it to be precise). It occured to me “well, why not try to see what python could do?”
Of course, I didn’t want to use the straightforward recursive solution, since as my colleague, Ahmed Soliman, rightly concluded that recursion in Python is slow. (An interesting counter-argument can be found here as well).
To cut things short, I wrote a C++ and a Python implementation of the Fibonacci algorithm with memoization, and seemingly I had some interesting observations
Here is the C++ implementation:
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <map>
using namespace std;
unsigned long long fib(unsigned int n) {
static map<unsigned long long, unsigned int> memo;
if (n < memo.size()) {
return memo[n];
} else if (n <= 1) {
memo[0] = 1;
memo[1] = 1;
return memo[n];
} else {
unsigned long long x = fib(n-1) + fib(n-2);
memo[n] = x;
return x;
}
}
int main(int argc, char **argv) {
unsigned int n = 0;
unsigned long long x = 0;
time_t t1, t2;
if (argc != 2) {
cout << "Usage: fib , where is the input in f(n) = f(n-1) + f(n-2)" << endl;
return 1;
}
n = atoi(argv[1]);
t1 = time(NULL);
x = fib(n);
t2 = time(NULL);
cout << "Time taken: " << t2 - t1 << endl;
cout << "fib(n)=" << x << endl;
return 0;
}
Here are the inputs and outputs, note that some values might be incorrect due to overflows, but what matters here is the function call mechanism:
mohd@mohd-laptop:~$ ./fib_memo 40
Time taken: 0
fib(n)=165580141
mohd@mohd-laptop:~$ ./fib_memo 100
Time taken: 0
fib(n)=126979422405
mohd@mohd-laptop:~$ ./fib_memo 1000
Time taken: 0
fib(n)=2071492649197
mohd@mohd-laptop:~$ ./fib_memo 900
Time taken: 0
fib(n)=1862700660921
Now here is the python implementation:
memo = dict() # I don't like this, can't python just have static variables?
def fib(n):
if memo.has_key(n):
return memo[n]
elif n == 0 or n == 1:
memo[n] = 1
else:
memo[n] = fib(n-1) + fib(n-2)
return memo[n]
if __name__ == "__main__":
if len(sys.argv) != 2:
print "Usage: fib , where is the input to f(n) = f(n-1) + f(n-2)"
n = int(sys.argv[1])
t1 = time.time()
x = fib(n)
t2 = time.time()
print "Time Taken: ", t2 - t1
print "fib(n)=", x
And here are my tests:
mohd@mohd-laptop:~$ python fib_memo.py 40
Time Taken: 0.000197887420654
fib(n)= 165580141
mohd@mohd-laptop:~$ python fib_memo.py 100
Time Taken: 0.00048303604126
fib(n)= 573147844013817084101
mohd@mohd-laptop:~$ python fib_memo.py 900
Time Taken: 0.00656604766846
fib(n)= 88793027306605937532517516910637647045239090036365766884466525589158360259770006891772711976920559280382807770394537471560061517120086971996377683290300054868066659454250625417891167369401
mohd@mohd-laptop:~$ python fib_memo.py 1000
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
....
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
memo[n] = fib(n-1) + fib(n-2)
File "fib_memo.py", line 11, in fib
RuntimeError: maximum recursion depth exceeded
So WTF? The recursion depth limit is somewhere near a 1000 function calls? To confirm my doubts I cracked open iPython with this scenario:
mohd@mohd-laptop:~$ ipython
/var/lib/python-support/python2.6/IPython/Magic.py:38: DeprecationWarning: the sets module is deprecated
from sets import Set
Python 2.6.2 (release26-maint, Apr 19 2009, 01:58:18)
Type "copyright", "credits" or "license" for more information.
IPython 0.9.1 -- An enhanced Interactive Python.
? -> Introduction and overview of IPython's features.
%quickref -> Quick reference.
help -> Python's own help system.
object? -> Details about 'object'. ?object also works, ?? prints more.
In [1]: from fib_memo import *
In [2]: fib(1000)
RuntimeError: maximum recursion depth exceeded
In [3]: fib(900)
Out[3]: 88793027306605937532517516910637647045239090036365766884466525589158360259770006891772711976920559280382807770394537471560061517120086971996377683290300054868066659454250625417891167369401L
In [4]: fib(1000)
Out[4]: 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501L
Now python is happy because it has to do only 100 recursive calls to get fib(1000), which clearly shows that the recursion limit is much smaller than what’s offered by the C++ implementation, and even worse, it means that the function behaviour can change according to the order it receives arguments.
On the other hand, the C++ implementation suffers from the fact that lead to wrong return if they exceed the “long long” limit (how many bits is that on x86_64?), but at least the function behaviour is deterministic, and probably the only limiting factor to calling the function is when the size of the map grows too large to be held in the process’s address space hence causing a segfault.
Bottomline, yes, you can theoretically use recursion in Python, but neverthless you should worry A LOT about performance, and even if you find optimizations, be aware of how your functions can get called and that inputs don’t cause the function to exceed the recursion limits. In other words, just spare yourself the time and don’t use recursion in Python unless ABSOLUTELY necessary, othereise Python offers a lot of tricks to get your things done.
.
