I wrote this python code to give the Harmonic Series of a certain value n both recursively and iteratively. Here is the functions:
def H(n):
if (n <= 0): raise ValueError("n must be bigger than 0.")
if (n == 1): return 1
else: return sum([1/x for x in range(1,n+1)])
def H_rec(n):
if (n <= 0): raise ValueError("n must be bigger than 0.")
if (n == 1): return 1
else: return 1/n + H(n-1)
Then, when I run the code 10 times for each, I get the following times:
RECURSIVE TIMES [22.755768060684204, 17.231882095336914, 14.965636014938354, 14.277509927749634, 14.0553719997406, 13.788002014160156, 13.338942766189575, 13.72638201713562, 14.690818071365356, 14.236813068389893]
RECURSIVE MEAN: 15.30671260356903
ITERATIVE TIMES [15.093524932861328, 12.801156759262085, 13.350629091262817, 13.806081056594849, 13.29387378692627, 13.876484870910645, 12.934008121490479, 13.859009981155396, 13.350301027297974, 13.590226888656616]
ITERATIVE MEAN: 13.595529651641845
The code is supposed to find H_rec(100000000)
and H(100000000)
, which are fairly big numbers.
I don't understand exactly why the recursive definition takes longer when the way it's defined seems to require less computation. The iterative one requires forming a list and finding its sum, while the recursive one just sums 1/n + H(n-1)
.
What is so misleading about this recursion? Why is it slow?
Your recursive function is calling the iterative one in else: return 1/n + H(n-1)
, you need to modify it as the following:
def H_rec(n):
if (n <= 0): raise ValueError("n must be bigger than 0.")
if (n == 1): return 1
else: return 1/n + H_rec(n-1) #Fix this line
Code executed inside the Python interpreter is fastest. Python code (which is compiled to Python byte code that is interpreted by a virtual machine) is slower. User-defined function calls are slowest of all, because the virtual machine has to manage its own call stack to track the execution environments.
Consider the following code:
def S1(n):
return sum(range(1,n))
def S2(n):
rv = 0
for i in range(1,n):
rv += i
return rv
def S3(n):
if n == 0:
return 0
else:
return n + S3(n-1)
S1
is the fastest; as much work as possible is pushed into the interpreter. S2
is slower because now each addition is a separate Python instruction to be interpreted. S3
is slowest because now each addition involves another function call to get its second operand; as noted before, function calls are slow in Python.
>>> print(timeit.timeit('S1(50)', globals=globals()))
1.2118524569996225
>>> print(timeit.timeit('S2(50)', globals=globals()))
3.262354401002085
>>> print(timeit.timeit('S3(50)', globals=globals()))
10.102635376999388
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With