CODEWITHSUNDEEP
pythonnumpyrecursion
baymurat
baymurat

Reputation: 81

Similar recursion functions have huge run-time differences. Why is that?

I was studying recursion and I needed to write a recursion function that will compute the greatest integer in the given list.

Firstly I tried this:

def find_max(L):
    if len(L) == 1: return L[0]
    mx = L[0]
    return mx if mx > find_max(L[1:]) else find_max(L[1:])

Then I found another approach which was:

def find_max2(L):
    if len(L) == 1: return L[0]
    rest = find_max(L[1:])
    if rest > L[0]: return rest
    else: return L[0]

I wanted to check the differences so I imported Numpy and created a list comprising of random integers

import numpy as np
np.random.seed()
nums = np.random.randint(10000,size=(25,1))

import time
#FIRST APPROACH
s = time.perf_counter_ns()
print(find_max(nums))
e = time.perf_counter_ns()
print("Elapsed time for the find_max:",e-s,"ns")
#SECOND APPROACH
s = time.perf_counter_ns()
print(find_max2(nums))
e = time.perf_counter_ns()
print("Elapsed time for the find_max2:",e-s,"ns")

I realized that the first one was 2 times slower than the second one.

D:\Codes\Python
λ python recursion.py
[9726]
Elapsed time for the find_max: 735373900 ns
[9726]
Elapsed time for the find_max2: 362327100 ns

D:\Codes\Python
λ python recursion.py
[9939]
Elapsed time for the find_max: 4889083400 ns
[9939]
Elapsed time for the find_max2: 2200926700 ns

D:\Codes\Python
λ python recursion.py
[9913]
Elapsed time for the find_max: 5955406900 ns
[9913]
Elapsed time for the find_max2: 3069119000 ns

I tried to figure it out that why it is like that. Yet I couldn't... If somebody could show me why it is like that, I'd appreciate it!

Upvotes: 1

Views: 52

Answers (3)

devck
devck

Reputation: 341

Two things happening here: first off, you're calling find_max recursively twice in the last line of your first function - this means that for every time you you recurse down a level, you double the number of active calls. The second thing happening is that you call find_max, not find_max2, recursively in the function find_max2. Running find_max2 with this fixed should give you a much faster runtime:

def find_max2(L):
    if len(L) == 1: return L[0]
    rest = find_max2(L[1:])
    if rest > L[0]: return rest
    else: return L[0]

Upvotes: 6

Jörg W Mittag
Jörg W Mittag

Reputation: 369428

The second one only calls find_max recursively one time.

The first one calls find_max twice when you have not found the maximum yet, which is going to be an average half the time, assuming a random distribution of numbers inside the array.

So, the first one is essentially doing twice as much work, therefore it makes sense that it is twice as slow.

Upvotes: 1

Ron Serruya
Ron Serruya

Reputation: 4426

I assume that in find_max2 you are calling find_max2 and not the first function.

It might take twice as long since in the first implementation you are calling find_max twice every time where the current value is not bigger, while in the second one you are only calling it once regardless of the current number being bigger or smaller

Upvotes: 1

Related Questions