Python 中的递归基础

Basics of recursion in Python

提问by Sebastian S

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

“编写一个递归函数，“listSum”，它接受一个整数列表并返回列表中所有整数的总和”。

Example:

例子：

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

I know how to do this another way but not in the recursive way.

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

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

I need the basic way to do this since special built-in functions is not allowed.

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

采纳答案by thefourtheye

Whenever you face a problem like this, try to express the result of the function with the same function.

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

In your case, you can get the result by adding the first number with the result of calling the same function with rest of the elements in the list.

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

For example,

例如，

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([])))))

Now, what should be the result of listSum([])? It should be 0. That is called base conditionof your recursion. When the base condition is met, the recursion will come to an end. Now, lets try to implement it.

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

The main thing here is, splitting the list. You can use slicingto do that.

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

Simple version

简单版

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

---

---

Tail Call Recursion

尾调用递归

Once you understand how the above recursion works, you can try to make it a little bit better. Now, to find the actual result, we are depending on the value of the previous function also. The returnstatement cannot immediately return the value till the recursive call returns a result. We can avoid this by, passing the current to the function parameter, like this

一旦你理解了上面的递归是如何工作的，你就可以试着让它变得更好一点。现在，要找到实际结果，我们还取决于前一个函数的值。该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

Here, we pass what the initial value of the sum to be in the parameters, which is zero in listSum([1, 3, 4, 5, 6], 0). Then, when the base condition is met, we are actually accumulating the sum in the resultparameter, so we return it. Now, the last returnstatement has listSum(ls[1:], result + ls[0]), where we add the first element to the current resultand pass it again to the recursive call.

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

This might be a good time to understand Tail Call. It would not be relevant to Python, as it doesn't do Tail call optimization.

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

---

---

Passing around index version

传递索引版本

Now, you might think that we are creating so many intermediate lists. Can I avoid that?

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

Of course, you can. You just need the index of the item to be processed next. But now, the base condition will be different. Since we are going to be passing index, how will we determine how the entire list has been processed? Well, if the index equals to the length of the list, then we have processed all the elements in it.

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

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

---

---

Inner function version

内部函数版本

If you look at the function definition now, you are passing three parameters to it. Lets say you are going to release this function as an API. Will it be convenient for the users to pass three values, when they actually find the sum of a list?

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

Nope. What can we do about it? We can create another function, which is local to the actual listSumfunction and we can pass all the implementation related parameters to it, like this

不。我们对于它可以做些什么呢？我们可以创建另一个函数，它是实际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

Now, when the listSumis called, it just returns the return value of recursioninner function, which accepts the indexand the resultparameters. Now we are only passing those values, not the users of listSum. They just have to pass the list to be processed.

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

In this case, if you observe the parameters, we are not passing lsto recursionbut we are using it inside it. lsis accessible inside recursionbecause of the closure property.

在这种情况下，如果您观察参数，我们不会传递ls给recursion它，而是在其中使用它。由于关闭属性，ls可以在内部访问recursion。

---

---

Default parameters version

默认参数版本

Now, if you want to keep it simple, without creating an inner function, you can make use of the default parameters, like this

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

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

Now, if the caller doesn't explicitly pass any value, then 0will be assigned to both indexand result.

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

---

---

Recursive Power problem

递归幂问题

Now, lets apply the ideas to a different problem. For example, lets try to implement the power(base, exponent)function. It would return the value of baseraised to the power exponent.

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

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

Now, how can we do this recursively? Let us try to understand how those results are achieved.

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

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

Hmmm, so we get the idea. The basemultiplied to itself, exponenttimes gives the result. Okay, how do we approach it. Lets try to define the solution with the same function.

嗯，所以我们明白了。该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))))

What should be the result if anything raised to power 1? Result will be the same number, right? We got our base condition for our recursion :-)

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

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

Alright, lets implement it.

好的，让我们实现它。

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

Okay, how will be define the Tail call optimized version of it? Lets pass the current result as the parameter to the function itself and return the result when the base condition it met. Let's keep it simple and use the default parameter approach directly.

好的，如何定义 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

Now, we reduce the exponentvalue in every recursive call and multiple resultwith baseand pass it to the recursive powercall. We start with the value 1, because we are approaching the problem in reverse. The recursion will happen like this

现在，我们减少exponent值在每一个递归调用，多result用base，并传递给递归power调用。我们从 value 开始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)

Since exponentbecomes zero, the base condition is met and the resultwill be returned, so we get 32:-)

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

回答by ?ukasz Rogalski

Early exit is typical for recursive functions. seqis falsy when empty (therefore when there are no numbers left to sum).

提前退出是递归函数的典型特征。seq为空时为假（因此当没有数字可求和时）。

Slice syntax allows to pass sequence to recursively called function without integer consumed in current step.

切片语法允许将序列传递给递归调用的函数，而无需在当前步骤中消耗整数。

def listSum(seq):
    if not seq:
        return 0
    return seq[0] + listSum(seq[1:])

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

回答by Eliza

def listSum(L):
    """Returns a sum of integers for a list containing
    integers.
    input: list of integers
    output: listSum returns a sum of all the integers
    in L.
    """
    if L == []:
        return []
    if len(L) == 1:
        return L[0]
    else:
        return L[0] + listSum(L[1:])
print listSum([1, 3, 4, 5, 6])
print listSum([])
print listSum([8])

回答by Belter

Another version:

另一个版本：

def listSum(ls):
    ls_len = len(ls)

    # Base condition
    if ls_len==1:
        return ls[0]
    if ls_len==0:
        return None
    # ls = listSum(ls[0:i]) + listSum(ls[i:])
    elif ls_len%2==0:
            i = int(ls_len/2)
            return listSum(ls[0:i]) + listSum(ls[i:])
    else:
        i = int((ls_len-1)/2)
        return listSum(ls[0:i]) + listSum(ls[i:])

Follow @thefourtheye's example, we can say:

按照@thefourtheye 的例子，我们可以说：

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

Base condition: when lsonly has one element, return this value.

基本条件：当ls只有一个元素时，返回这个值。

回答by Ramazan

def listsum(list):
    if len(list) == 1:
        return list[0]
    else:
        return list[0] + listsum(list[1:])

print(listsum([1,5,9,10,20]))

The basic idea behind this recursive function is that we want to check if we have a base case which is shown as if len(list) == 1:. For the base case we just return the value in the list return list[0], otherwise, we still have multiple elements in the list. In the else:statement we will add the first element from the list which is list[0]to the rest of the elements in the list.This is shown by calling the function recursively with the list shorter by 1 element--the element at index 0-- listsum(list[1:]), this process repeats with the list getting smaller until you arrive at the base case--a list of length 1 and then you will get a final result.

这个递归函数背后的基本思想是我们想要检查我们是否有一个显示为 的基本情况if len(list) == 1:。对于基本情况，我们只返回列表中的值return list[0]，否则，列表中仍然有多个元素。在else:语句中，我们将把列表中的第一个元素添加到列表中list[0]的其余元素中。这通过递归调用函数来显示，列表中的元素短于 1 个元素——索引 0 处的元素—— listsum(list[1:])，这重复该过程，列表变小，直到您到达基本情况——长度为 1 的列表，然后您将获得最终结果。