python - Python 中的递归基础

Question

"Write a recursive function, "listSum" that takes a list of integers and returns the sum of all integers in the list".

例子:

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

我知道如何以另一种方式做到这一点，但不是以递归方式。

def listSum(ls):
    i = 0
    s = 0
    while i < len(ls):
        s = s + ls[i]
        i = i + 1
    print s

我需要基本的方法来做到这一点，因为不允许使用特殊的内置函数。

Answer 1

每当你遇到这样的问题时，试着用相同的函数来表达函数的结果。

在您的情况下，您可以通过将第一个数字与对列表中的其余元素调用相同函数的结果相加来获得结果。

例如，

listSum([1, 3, 4, 5, 6]) = 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([])))))

现在，listSum([]) 的结果应该是什么？ ?它应该是 0。这称为递归的基本条件。当满足基本条件时，递归将结束。现在，让我们尝试实现它。

这里的主要内容是拆分列表。您可以使用 slicing要做到这一点。

简易版

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

尾调用递归

一旦你理解了上面的递归是如何工作的，你就可以试着让它变得更好一点。现在，要找到实际结果，我们还取决于前一个函数的值。 return在递归调用返回结果之前，语句不能立即返回值。我们可以通过将电流传递给函数参数来避免这种情况，就像这样

>>> def listSum(ls, result):
...     if not ls:
...         return result
...     return listSum(ls[1:], result + ls[0])
... 
>>> listSum([1, 3, 4, 5, 6], 0)
19

在这里，我们在参数中传递和的初始值，在 listSum([1, 3, 4, 5, 6], 0) 中为零。 .然后，当满足基本条件时，我们实际上是在 result 中累加总和。参数，所以我们返回它。现在，最后一个 return声明有listSum(ls[1:], result + ls[0]) ，我们将第一个元素添加到当前 result并将其再次传递给递归调用。

这可能是了解 Tail Call 的好时机.它与 Python 无关，因为它不进行尾调用优化。

传递索引版本

现在，您可能认为我们正在创建如此多的中间列表。我可以避免吗？

当然可以。您只需要接下来要处理的项目的索引。但现在，基础条件将有所不同。既然我们要传递索引，我们将如何确定整个列表是如何处理的？好吧，如果索引等于列表的长度，那么我们已经处理了其中的所有元素。

>>> def listSum(ls, index, result):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
... 
>>> listSum([1, 3, 4, 5, 6], 0, 0)
19

内函数版本

如果您现在查看函数定义，您将向其传递三个参数。假设您要将此函数作为 API 发布。当用户实际找到列表的总和时，用户传递三个值是否方便？

不。我们对于它可以做些什么呢？我们可以创建另一个函数，它是实际 listSum 的局部函数。函数，我们可以将所有与实现相关的参数传递给它，就像这样

>>> def listSum(ls):
...
...     def recursion(index, result):
...         if index == len(ls):
...             return result
...         return recursion(index + 1, result + ls[index])
...
...     return recursion(0, 0)
... 
>>> listSum([1, 3, 4, 5, 6])
19

现在，当 listSum被调用，它只是返回 recursion 的返回值内部函数，它接受 index和 result参数。现在我们只传递这些值，而不是 listSum 的用户.他们只需要传递要处理的列表。

在这种情况下，如果您观察参数，我们不会传递 ls至 recursion但我们在里面使用它。 ls可在内部访问 recursion因为闭包属性。

默认参数版本

现在，如果你想保持简单，不创建内部函数，你可以使用默认参数，像这样

>>> def listSum(ls, index=0, result=0):
...     # Base condition
...     if index == len(ls):
...         return result
...
...     # Call with next index and add the current element to result
...     return listSum(ls, index + 1, result + ls[index])
... 
>>> listSum([1, 3, 4, 5, 6])
19

现在，如果调用者没有明确传递任何值，那么 0将分配给 index和 result .

递归幂问题

现在，让我们将这些想法应用于不同的问题。例如，让我们尝试实现 power(base, exponent)功能。它将返回值 base提升到权力 exponent .

power(2, 5) = 32
power(5, 2) = 25
power(3, 4) = 81

现在，我们如何递归地做到这一点？让我们尝试了解这些结果是如何实现的。

power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32
power(5, 2) = 5 * 5             = 25
power(3, 4) = 3 * 3 * 3 * 3     = 81

嗯，所以我们明白了。 base乘以自身，exponent时间给出了结果。好的，我们如何处理它。让我们尝试定义具有相同功能的解决方案。

power(2, 5) = 2 * power(2, 4)
            = 2 * (2 * power(2, 3))
            = 2 * (2 * (2 * power(2, 2)))
            = 2 * (2 * (2 * (2 * power(2, 1))))

如果任何东西的幂为 1，结果应该是什么？结果将是相同的数字，对吗？我们得到了递归的基本条件:-)

            = 2 * (2 * (2 * (2 * 2)))
            = 2 * (2 * (2 * 4))
            = 2 * (2 * 8)
            = 2 * 16
            = 32

好的，让我们实现它。

>>> def power(base, exponent):
...     # Base condition, if `exponent` is lesser than or equal to 1, return `base`
...     if exponent <= 1:
...         return base
...
...     return base * power(base, exponent - 1)
... 
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81

好的，如何定义 Tail 调用优化版本呢？让我们将当前结果作为参数传递给函数本身，并在满足基本条件时返回结果。让我们保持简单，直接使用默认参数方法。

>>> def power(base, exponent, result=1):
...     # Since we start with `1`, base condition would be exponent reaching 0
...     if exponent <= 0:
...         return result
...
...     return power(base, exponent - 1, result * base)
... 
>>> power(2, 5)
32
>>> power(5, 2)
25
>>> power(3, 4)
81

现在，我们减少 exponent每个递归调用和多个 result 中的值与 base并将其传递给递归 power称呼。我们从值 1 开始，因为我们正在反向处理这个问题。递归会像这样发生

power(2, 5, 1) = power(2, 4, 1 * 2)
               = power(2, 4, 2)
               = power(2, 3, 2 * 2)
               = power(2, 3, 4)
               = power(2, 2, 4 * 2)
               = power(2, 2, 8)
               = power(2, 1, 8 * 2)
               = power(2, 1, 16)
               = power(2, 0, 16 * 2)
               = power(2, 0, 32)

自 exponent变为零，满足基本条件并且 result将被返回，所以我们得到 32 :-)