Recursion with ternary operator 'hack' in Python

Question

Playing around in Python, I found that the following code works as I expected:

f = lambda S,b : (S if len(S)==b else f(S[1:],b))

From a list S, it will recursively drop the first element until the length of S equals b. For instance f([1,2,3,4,5,6],3) = [4,5,6].

However, much to my surprise the following solution, that uses the 'ternary hack' [a,b][c] instead of "b if c else a" (aka "c?b:a") does not work:

g = lambda S,b : (g(S[1:],b),S)[len(S)==b]

This will exceed maximum recursion depth.

Why doesn't this work?

(I know neither is an example of great coding style but that is beside the point now.)

Answer 1

Ok, lets look at the ast the lambda function generates:

import ast
tree = ast.parse('lambda S,b : (g(S[1:],b),S)[len(S)==b]')
ast.dump(tree)

After some formatting done in vim this is what I got:

Module(
  [Expr(
    Lambda(
      arguments(
        [Name('S', Param()), Name('b', Param())],
        None,
        None,
        []
      ),
      Subscript(
        Tuple(
          [Call(
              Name('g', Load()),
              [Subscript(Name('S', Load()), Slice(Num(1), None, None), Load()), Name('b', Load())],
              [],
              None,
              None
            ),
            Name('S', Load())
          ],
          Load()
        ),
        Index(
          Compare(
            Call(Name('len', Load()), [Name('S', Load())], [], None, None),
            [Eq()],
            [Name('b', Load())]
          )
        ),
        Load()
      )
    )
  )]
)

As you may see, the first thing this code executes when calls the lambda is the tuple creation and after that, comes directly the recursive call (Call(Name('g'...) to the same lambda.

Calling is the first thing getting done and since the slicing of an empty list is still the empty list:

>>>[1][1:]
[]
>>>[][1:]
[]

This means that g(S[1:]) will reduce your list until the empty list and then continue endlessly calling g with the empty list. This happens because the way the parser execute the statements. The first thing that's executed is the recursive method call, so it won't stop.

My point: base case is not working on the recursion.

Hope this bring more light to the subject.

Answer 2

I think the problem is related to how the ternary operator works. When you use a ternary operator, both expresions gets evaluated before checking the condition.

g = lambda S,b : (g(S[1:],b),S)[len(S)==b]

So in this case g(S[1:],b) gets evaluated before even reaching the if statement.

If you have a function, there's no base case which is the same case with g(S[1:],b)

def func(S, b)
    return func(S[1:],)

func(S,b)
#output: error - exceed maximum recursion depth

S[1:] will reach the point where it's empty and if it's empty, it will return an empty list.

A small example about the empty list:

S = [0, 1]

S = S[1:]
# [1]

S = S[1:]
# [] # empty

S = S[1:]
# [] # also empty

Answer 3

If you do A if C else B, then C is executed first, and then one of A or B is executed (and it's result returned), whereas if you do [B, A][C], both A and B are executed, and then C. You can easily check this by doing p("A") if p("C") else p("B") and [p("B"), p("A")][p("C")] with some function p that prints its input and then returns True or False

So in your first case, S if len(S)==b else f(S[1:],b), the recursive call is executed only if the condition does not apply. In the second case, however, it is executed before the condition is even tested, and the same in the recursively called function, ad infinitum.

(I assume that you do not intend to use this in practice, so this may not be important, but anyhow: note that (1) both functions lack a safeguard for the case len(S) < b, (2) the same can be achieved with S[-b:], and (3) using if/else is, of course, much more readable.)