Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Why I'm getting "maximum recursion depth exceeded"

I just saw an alternative construction for python's if-else statements like (0, 1)[ x > 5] and wanted to try it with recursion but for some reason it's not working. Just forget for a moment that it's unpythonic.

Here is an original code which I'm trying to replace with alternative:

def f(n):
    return 1 if n == 1 else n * f(n - 1)

Alternative, which give recursion problem:

def f(n):
    return (n * f(n - 1), 1)[n == 1]

What is the problem with alternative code?

like image 873
Viacheslav Kondratiuk Avatar asked Mar 13 '23 17:03

Viacheslav Kondratiuk


2 Answers

The problem is that Python will always try to compute n * f(n - 1) before indexing the tuple with [n == 1].

The result is that the function keeps calling itself until the process runs out of memory on the stack.

The first code avoids this by doing the n==1 check before the recursive call, and then not making the call if the check succeeds

Source:

https://docs.python.org/2/reference/expressions.html has a section on 'Evaluation order' stating that it is performed left to right.

like image 53
Tom Rees Avatar answered Mar 15 '23 05:03

Tom Rees


Your first function short circuits. n * f(n - 1) is only computed if n != 1.

In the second function, Python must evaluate both elements to create the list, so n * f(n - 1) is always computed, even when the elements are never accessed. This results in infinite recursion.

like image 26
jpmc26 Avatar answered Mar 15 '23 05:03

jpmc26