9

在 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]

这将超过最大递归深度。

为什么这不起作用？

（我知道这两者都不是优秀编码风格的例子，但现在这无关紧要。）

4

3 回答 3

6

好的，让我们看看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使用空列表调用。发生这种情况是因为解析器执行语句的方式。执行的第一件事是递归方法调用，因此它不会停止。

我的观点：基本情况不适用于递归。

希望这能为主题带来更多亮点。

于 2013-11-08T13:16:17.183 回答
4

我认为问题与三元运算符的工作方式有关。当您使用三元运算符时，两个表达式都会在检查条件之前进行评估。

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

所以在这种情况下g(S[1:],b)，甚至在到达 if 语句之前就被评估了。

如果您有一个功能，则没有与以下情况相同的基本情况g(S[1:],b)

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

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

S[1:] 将到达它为空的点，如果它为空，它将返回一个空列表。

关于空列表的一个小例子：

S = [0, 1]

S = S[1:]
# [1]

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

S = S[1:]
# [] # also empty
于 2013-11-08T13:13:51.493 回答
2

如果您这样做A if C else B，则C首先执行then ，然后执行or之一 （并返回结果），而如果您这样做，则同时执行and ，然后执行. 您可以通过执行并使用一些打印其输入然后返回或AB[B, A][C]AB Cp("A") if p("C") else p("B")[p("B"), p("A")][p("C")]pTrueFalse

因此，在您的第一种情况下，S if len(S)==b else f(S[1:],b)仅当条件不适用时才会执行递归调用。然而，在第二种情况下，它甚至在条件被测试之前执行，并且在递归调用的函数中也是如此，ad infinitum。

（我假设您不打算在实践中使用它，因此这可能并不重要，但无论如何：请注意（1）这两个功能都缺乏对 case 的保护len(S) < b，（2）同样可以通过S[-b:]，和（ 3）使用if/else当然更具可读性。）

于 2013-11-08T13:17:47.357 回答