将切片传递给 Python 中的递归函数

Question

我想我了解递归函数和切片的基本原理（分别），但我无法将它们组合在一起。我不明白将切片或列表传递给以下函数时会发生什么。

def listSum(ls):
    # Base condition
    if not ls:
        return 0

    # First element + result of calling `listsum` with rest of the elements
    return ls[0] + listSum(ls[1:])

listSum([1, 3, 4, 5, 6])
19

这是包含这段代码的线程： Understanding recursion in Python

我想我真的会从调用函数时发生的事情的演练中受益。

该线程有很多不同递归函数的示例，具有预期的输出。后面的例子我理解的比我上面复制的还要少

Answer 1

递归的基本概念是每次调用消耗部分输入，减少它直到匹配基本情况。

这里的基本情况是 if not ls，当 ls 是一个空列表时也是如此。

消耗是通过切片完成的：每次调用传递一个比上一个元素短一个元素的列表。这是通过 listSum(ls1:]) 完成的，它在由 ls 的所有元素组成的列表上调用 listSum，除了第一个 .

然后将第一个元素添加到递归调用的结果中并返回。由于将对 ls 的元素进行一次递归调用，因此 ls 中的每个数字轮流成为弹出并求和的数字，即 consumed .

逐步完成，我们将添加

1 + listSum( [3, 4, 5, 6] )

也就是

1 + 3 + listSum( [4, 5, 6])

也就是

1 + 3 + 4 + listSum( [5, 6] )

即

1 + 3 + 4 + 5 + listSum( [6] )

即

1 + 3 + 4 + 5 + 6 + listSum([])

由于基本情况，

1 + 3 + 4 + 5 + 6 + 0

也就是 19。

Answer 2

列出遍历婴儿步骤

对于使用递归遍历列表，只有 3 件事很重要

空列表 - 在任何事情之前总是检查你的列表是否为空！
列表的头部 – 第一项
列表的尾部 – 整个列表除了第一项

好的，这是我们将用来编写程序的函数

def is_empty (ls):
  return ls == []

def head (ls):
  return ls[0]

def tail (ls):
  return ls[1:]

函数的使用很简单

is_empty ([])           # => True
is_empty ([ 1, 2, 3 ])  # => False

head ([ 1, 2, 3 ])      # => 1

tail ([ 1, 2, 3 ])      # => [2,3]

好的，让我们来编写我们的 list_sum 函数——我想你会同意我们最终得到了一个非常可读的程序，这要归功于我们定义的列表助手

def list_sum (ls):
  if is_empty (ls):
    return 0
  else:
    return head (ls) + list_sum (tail (ls))

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

但是你用尾递归标记了它，所以在可选参数和默认值的帮助下，我们可以将递归调用移到尾位置。粗体

的变化

def list_sum (ls<b>, acc = 0</b>):
  if is_empty (ls):
    return <b>acc</b>
  else:
    return list_sum (tail (ls)<b>,</b> head (ls) + <b>acc</b>)

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

但是Python并没有真正的尾调用消除，所以你仍然需要来确保堆栈安全。

每天抽高阶函数

使用 head 和 tail 将我们从 [0] 和 [1:] 的单调（和丑陋）中解脱出来，但是这种列表遍历模式非常普遍，以至于我们甚至可以完全摆脱这个层次的思考！

让我们回顾一下我们的函数，list_sum。此函数遍历列表并使用内置的 + 函数执行加法。如果我们想用 * 乘以所有元素而不是 + 怎么办？

def list_sum (ls):
  if is_empty (ls):
    return 0
  else:
    return head (ls) + list_sum (tail (ls))

def list_product (ls):
  if is_empty (ls):
    return <b>1</b>
  else:              
    return head (ls) <b>* list_product</b> (tail (ls))

print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040

唯一不同的是0改为1，+改为*。我们不想每次想对列表做某事时都重写所有内容。如果我们使用函数参数抽象这些值，我们就可以在这个漂亮的小程序中捕捉到列表遍历的本质

from operator import add, mul

def list_reduce (f, acc, ls):
  if is_empty (ls):
    return acc
  else:
    return list_reduce (f, f (acc, head (ls)), tail (ls))

def list_sum (ls):
  return list_reduce (add, 0, ls)

def list_product (ls):
  return list_reduce (mul, 1, ls)

print (list_sum ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 28

print (list_product ([ 1, 2, 3, 4, 5, 6, 7 ]))
# => 5040

并且可以使用其他高阶函数构建高阶函数。然后在不知不觉中，您正在进行各种高级转换和遍历！

请注意，此时我们没有考虑 head 或 tail。诸如 not []、ls[0] 和 ls[1:] 之类的脑洞大开的东西是看不见的，因此是心不在焉的。

def map (f, ls):
  return list_reduce (lambda acc, x: acc + [ f (x) ], [], ls)

def square (x):
  return x * x

print (map (square, [ 1, 2, 3, 4, 5, 6, 7 ]))
# => [1, 4, 9, 16, 25, 36, 49]

将切片传递给 Python 中的递归函数

Passing a slice to recursive function in Python

python

list

recursion

slice

tail-recursion