在Python中使用三元运算符'hack'进行递归

Question

在Python中玩,我发现以下代码按预期工作:

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

从列表S中,它将递归地删除第一个元素,直到S的长度等于b.例如f([1,2,3,4,5,6],3)= [4,5,6].

然而,令我惊讶的是,以下解决方案使用'三元黑客'[a,b] [c]而不是"b if c else a"(又名"c？b:a")不起作用:

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

这将超过最大递归深度.

为什么这不起作用？

(我知道两者都不是一个很好的编码风格的例子,但现在不是重点.)

Answer 1

好的,让我们看一下astlambda函数生成:

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

在vim中完成一些格式化后,这就是我得到的:

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()
      )
    )
  )]
)

正如您所看到的,此代码在调用lambda时执行的第一件事是元组创建,之后直接将递归调用(Call(Name('g'...)传递给相同的lambda.

调用是第一件事,因为切换空列表仍然是空列表:

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

这意味着g(S[1:])将减少列表直到空列表,然后继续无休止地调用g空列表.这是因为解析器执行语句的方式.执行的第一件事是递归方法调用,所以它不会停止.

我的观点:基本情况不适用于递归.

希望这为这个主题带来更多的光明.