A simpler recursive code is slower than an iterative version of the same

Question

I wrote this python code to give Harmonic series of a specific value of n, both recursively and iteratively. Here are 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 points:

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 quite large numbers.

I don’t understand why a recursive definition takes longer when the way it is defined requires less computation. Iterative requires the formation of a list and finding its sum, while the recursive one simply sums up 1/n + H(n-1).

What is misleading about this recursion? Why is he slow?

Answer 1

, Python, . Python ( - Python, ) . , .

:

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 ; . S2 , Python . S3 , ; , 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

Answer 2

else: return 1/n + H(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_rec(n-1) #Fix this line