4

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?

Viacheslav Kondratiuk
  • 8,493
  • 9
  • 49
  • 81
  • You might try to debug the problem yourself by inserting `print n` inside the body of the alternative function. – Paul Hankin Apr 01 '16 at 11:53
  • ask yourself "what happens when n==1?" Does the function stop calling itself, or does it continue? What will cause it to stop? – Bryan Oakley Apr 01 '16 at 11:54
  • @BryanOakley I assume that expression will evaluate to True, which will cast to 1 and return second element of tuple, what will stop recursion. – Viacheslav Kondratiuk Apr 01 '16 at 11:55
  • Because your condition is after your tuple which is contain the function itself and there for calling it recursively for until it encounter the `RuntimeError`. – Mazdak Apr 01 '16 at 11:56
  • First syntax uses short-circuiting, second does not. Related: http://stackoverflow.com/questions/394809/does-python-have-a-ternary-conditional-operator – Łukasz Rogalski Apr 01 '16 at 11:56
  • re: _"I assume that expression will evaluate to True"_: don't _assume_. You need to know for certain. – Bryan Oakley Apr 01 '16 at 12:28

2 Answers2

5

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.

Tom Rees
  • 455
  • 2
  • 10
2

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.

jpmc26
  • 28,463
  • 14
  • 94
  • 146