CODEWITHSUNDEEP
pythonalgorithmrecursion
ts10
ts10

Reputation: 87

Is using recursive function inefficient in python?

I tried to solve the question that calculates the number in the array of kth row, nth column. As you can see in the figure below, the value of the first row, nth column is n. Then, array[k][n] is the sum of values across from array[k-1][1] to array[k-1][n]. (I can use only basic python tools, cannot use Numpy or other packages in this problem)

enter image description here

At first, I tried to solve the problem by using the recursive function as follows.

def n_family(k, n):
    if k == 0:
        return n
    elif n == 1:
        return 1
    else:
        return n_family(k-1,n) + n_family(k,n-1)
k = int(input())
n = int(input())
print(n_family(k, n))

However, I failed because the code spent too much when k > 12 and n > 12. Then, I used the code below

k = int(input())
n = int(input())
apt = [[j+1 if i == 0 else 0 for j in range(14) ] for i in range(k+1)] #max(n) is 14
for floor in range(1,k+1):
    apt[floor][0] = 1
    for room in range(1,14):
        apt[floor][room] += (apt[floor][room-1] + apt[floor-1][room])
print(apt[k][n-1])

I wonder why the second code spent less time. And I want to ask if using recursive function inefficient in python always? Or This situation is just a specific case?

Upvotes: 1

Views: 162

Answers (2)

qouify
qouify

Reputation: 3900

The performance of your recursive function is not due to the implementation of recursivity in python but rather to the way your recursive algorithm proceeds.

That's a part of the execution tree of your function for k=n=4.

n_family(4, 4)
   n_family(4, 3)
      n_family(3, 3)
      ...
      n_family(4, 2)
      ...
    n_family(3, 4)
      n_family(2, 4)
      ...
      n_family(3, 3)    <- duplicate call
      ...

You see that your recursive function is called twice for k=n=3 and many such redundant computations will be performed. Whereas your iterative function is optimal: the value of each "cell" is computed only once.

Therefore if you want to use a recursive algorithm for this problem you must use some memorisation mechanism like, e.g., functools.cache as suggested by @blhsing.

Upvotes: 3

James
James

Reputation: 3411

Python (CPython at least) doesn't have tail call optimisation:

What is tail call optimization?

So in general you can expect recursive implementations of an algorithm to be slower than an equivalent iterative implementation.

This is a deliberate design choice by Guido to trade off some performance in exchange for a more intuitive debugging experience. The impact might be reduced in a future version of Python though if frame handling is improved. (https://github.com/markshannon/faster-cpython/blob/master/plan.md)

However, as pointed out in the comments, in the specific example above the performance difference is likely not due to the language features, as you are doing a different set of calculations in each version.

Upvotes: 2

Related Questions