Is using recursive function inefficient in python?

Question

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?

It's not related to python. It's just that the recursive function is ineffective as it perform many redundant computations which are not done by your iterative version. — sevan
– sevan, Commented Aug 12, 2021 at 7:59
As the comment above says, this is not a problem related to the language but rather the time complexity of your algorithm. You're recalculating lots of values you already had. If for whatever reason you really need to use recursive functions in this problem, you might want to learn about dynamic programming, since it would optimise it to be basically as fast as the second solution. To answer the actual question you made, yes calling functions is actually slower than not calling them, but the time a function call takes is negligible unless your code performs an enormous amount of operations. — Shinra tensei
– Shinra tensei, Commented Aug 12, 2021 at 8:03
Thank you so much! Your comments helped me a lot. I need to study algorithms and functools.cache. — ts10
– ts10, Commented Aug 12, 2021 at 8:10
Your two functions use different algorithms. You can implement your second solution in a tail recursive manner that would perform similar. (Yes, I know CPython does not have TCO but my statement about preformance is still true and it works as long as the depth isn't blowing the stack) — Sylwester
– Sylwester, Commented Aug 12, 2021 at 13:33

sevan · Accepted Answer · 2021-08-12 08:14:16Z

3

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.

edited Aug 12, 2021 at 8:14

answered Aug 12, 2021 at 8:05

sevan

3,9743 gold badges19 silver badges30 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

James · Accepted Answer · 2021-08-12 08:07:21Z

2

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.

answered Aug 12, 2021 at 8:07

James

3,4711 gold badge22 silver badges34 bronze badges

1 Comment

Sylwester Over a year ago

OPs recursive function is not tail recursive since it branches like a tree. TCO requires the recursive function to do recursion in tail position for it to be an iterative process.

Collectives™ on Stack Overflow

Is using recursive function inefficient in python?

2 Answers 2

Comments

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related