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. — qouify, Aug 12 '21 at 07:59
Use [functools.cache](https://docs.python.org/3/library/functools.html#functools.cache). — blhsing, Aug 12 '21 at 08:01
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, Aug 12 '21 at 08:03
Thank you so much! Your comments helped me a lot. I need to study algorithms and functools.cache. — ts10, Aug 12 '21 at 08: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, Aug 12 '21 at 13:33

qouify · Accepted Answer · 2021-08-12T08:14:16.813

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.

score 2 · Answer 2 · answered Aug 12 '21 at 08:07

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.

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. — Sylwester, Aug 12 '21 at 13:30

Is using recursive function inefficient in python?

2 Answers2