递归地将列表递减1

Question

非常快速简单的家庭作业问题。我运行正常，但我认为有一个更好的
做这件事的方式。更像Python的方式。
下面是我递归地将列表中的每个元素递减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

你只能用一个论点，在我看来它更简单：

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

但是正如@jamylak指出的，这个算法的复杂性是O（N^2），因为l[1:]创建了一个新的列表，其中引用了列表中其余的项。在

如果你需要效率，我建议你使用列表理解（Haidro's answer），但如果你只想为了学习目的而使用列表理解，我想这不是优先考虑的问题。在

Answer 2

不管怎样，这是学习递归的一种糟糕的方法，因为你用它来做一些本质上不是递归的事情。如果你的老师真的要你写一个程序，让列表中的元素递归地递减，那就让他/她感到羞耻。在

正如Haidro所指出的，解决这个问题的最典型的方法就是使用列表理解来迭代列表

[i - 1 for i in l]

作为一个循环，这是

^{pr2}$

如果您想在任意级别的深度解决相同的问题，递归是很有用的。例如，假设您有一个类似[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微秒。这比最快的递归方法快三个数量级。

• 除非将递归限制设置得更高，否则递归函数在超过1000次调用后不起作用。您可能已经注意到Ashwini Chaudhary的答案中的sys.setrecursionlimit(10**5)调用。这是必要的，因为没有它，每次调用都会导致一个RuntimeError: maximum recursion depth exceeded的大回溯。但即使这样，一个稍微大一点的列表仍然会导致递归限制。根据documentation，每个操作系统都有一个上限，设置得太高会导致崩溃。

• 递归函数更难调试。它们不仅会因来自同一个函数的数百次调用而污染堆栈跟踪，而且在概念上更难理解，因为同一函数的同一部分以不同的方式使用，这取决于您所在的堆栈级别。人类自然的思维方式是反复的。我们一次只做一件事。我们自己大脑的“堆栈”只有几个层次，所以我们很难用递归的方式解决问题，比如“让我开始解决一个问题，但在我完成之前，让我解决另一个问题，然后当我完成时，我会完成原来的问题。在较小的问题中，我也会做同样的事情，这样我在写完之前就可以深入几层。”这就是为什么你走进厨房去拿笔，然后你看到一个糖果棒，开始吃它，当你吃完的时候，你就忘了笔了。你“递归”了一个层次，从笔问题到糖果条问题，你的心理堆栈变得太深了（只有两个层次，但这已经足够了）。如果你不是抓住了糖果棒，但是在你打开它开始吃之前，你还发现了笔（我能想出的最好的迭代分析），你可以做到这两个都不会忘记。你在程序中解决问题的方法应该和你在头脑中解决问题的方式完全相同，因为这是你理解代码在做什么的唯一方法。Python是一种非常好的语言，因为它的高级接口让您可以做到这一点（至少比低级语言更常见）。利用这个事实！

Answer 3

可能是Python，但是：

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