递归递减列表1

Question

非常快速简单的家庭作业问题.我运行正常,但我认为有更好的
方法.一种更加Pythonic的方式.
这是我的代码递归递减列表的每个元素1.

l = range(30)  
def recurseDecrMap(l, x = []):  
    if len(l) == 0:  
        return []  
    else:  
        x.append(l[0] -1)  
    recurseDecrMap(l[1:], x)  
    return x  

所以感谢任何输入.我正在努力学习做更好的递归.无法
掌握它的诀窍.

Answer 1

可能不那么 pythonic,但有:

def recurseDecrMap(l):
    return [l[0]-1] + recurseDecrMap(l[1:]) if l else []

Answer 2

你只能使用一个参数,在我看来它更简单:

def recurseDecrMap(l):  
    if not l:  
        return []  
    else:
        return [l[0]-1] + recurseDecrMap(l[1:])

但正如@jamylak指出的那样,该算法的复杂性为O(N ^ 2),因为l[1:]创建了一个新列表,其中包含对列表中其余项的引用.

如果你需要效率,我建议你使用列表理解(Haidro的答案),但我想如果你只是为了学习目的,它不是一个优先事项.

Answer 3

对于它的价值,这是一种了解递归的可怕方法,因为你正在使用它来做一些本身不具有递归性的东西.如果你的老师真的要求你写一个程序,[1, 2, 3, 4] 递归递减列表的元素,那么他/她就会感到羞耻.

正如Haidro所说,解决这个问题的最Pythonic方法是使用列表理解迭代列表

[i - 1 for i in l]

作为一个循环,这是

def decr(l):
    a = []
    for i in l:
        a.append(i - 1)
    return a

如果要在任意深度级别解决相同问题,则递归很有用.例如,假设您有类似的东西,[1, [2, 3], [[4], 5]]并且您希望将每个数字减1,同时保持列表结构.在这种情况下,递归解决方案将使用基本情况的迭代解决方案,并为递归情况调用自身.

def decr_recursive(l):
    a = []
    for i in l:
        if isinstance(i, list):
            a.append(decr_recursive(i))
        else:
            a.append(i - 1)
    return a

如果您想要支持的不仅仅是列表或整数,这可以很容易地修改.

>>> decr([1, [2, 3], [[4], 5]])
[0, [1, 2], [[3], 4]]

这是一种在不使用递归的情况下很难解决的问题,但很容易用它来解决.你要问的是在没有递归的情况下很容易解决的问题(这只是为了上帝而在列表上进行的简单迭代),但有些难以用它来解决.

你应该避免在Python中递归的一些原因

• 它更难阅读.比较[i - 1 for i in l],甚至是显式循环,比如

  def decr(l):
      if not l:
          return []
      return [l[0] - 1] + decr(l[:1])
  

• 在Python中调用函数可能很昂贵.我在电脑上和Ashwini Chaudhary大致相同.但是[i - 1 for i in range(10**4)]我的电脑需要559μs.这比最快的递归方法快三个数量级.

• 除非您将递归限制设置得更高,否则递归函数不会超过1000次调用.你可能已经注意到了sys.setrecursionlimit(10**5)Ashwini Chaudhary的回答.这是必要的,因为没有它,每次调用都会导致RuntimeError: maximum recursion depth exceeded跟随一个巨大的追溯.但即便如此,更大的列表仍然会导致递归限制.根据文档,每个操作系统都有一个上限,将其设置得太高可能会导致崩溃.

• 递归函数更难调试.它们不仅会使用来自同一函数的数百个调用来污染堆栈跟踪,但它们在概念上更难以遵循,因为同一函数的相同部分以不同的方式使用,具体取决于您在堆栈中的哪个级别人类自然的思维方式是迭代的.我们一次做一件事.我们自己的大脑"堆栈"只有几层深,所以我们很难以递归方式解决问题,比如"让我开始解决问题,但在我完成之前,让我解决另一个问题,然后当我完成后,我将完成原来的问题.在较小的问题中,我可能会做同样的事情,所以在我完成之前我会得到几个等级." 这就是为什么你走进厨房拿笔,然后你看到一个糖果棒开始吃它,当你完成后,你忘记了笔.你"递归"了一个级别,从笔问题到直板问题,​​你的心理堆栈太深了(只有两个级别,但这就足够了).如果你反而抓住了糖果棒,但是在你打开它并开始吃它之前,还找到了笔(我能想出的最佳迭代方法),你可以做到这两点而不会忘记.解决程序问题的方式应该与解决问题的方式完全相同,因为这是了解代码执行情况的唯一方法.Python是一种非常好的语言,因为它的高级接口让你可以做到这一点(至少比在低级语言中更常见).用这个事实!

Answer 4

这是最糟糕的方式 - 使用Fixed Point Combinator:

Y = lambda g: (lambda f: g(lambda arg: f(f)(arg))) (lambda f: g(lambda arg: f(f)(arg)))
recurseDecrMap = Y(lambda f: lambda l: [l[0]-1] + f(l[1:]) if l else [])