Python递归的基础 [英] Basics of recursion in Python
问题描述
编写一个递归函数"listSum"，该函数接受一个整数列表并返回该列表中所有整数的总和".
"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
我知道如何以其他方式执行此操作，但不是以递归的方式进行操作.
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.
推荐答案
每当遇到这样的问题时，请尝试使用相同的函数表示该函数的结果.
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.
例如，
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.这称为递归的基本条件.当满足基本条件时，递归将结束.现在，让我们尝试实现它.
Now, what should be the result of listSum([])? It should be 0. That is called base condition of your recursion. When the base condition is met, the recursion will come to an end. Now, lets try to implement it.
这里最主要的是拆分列表.您可以使用切片来做到这一点.
The main thing here is, splitting the list. You can use slicing to do that.
简单版本
>>> 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语句在递归调用返回结果之前不能立即返回该值.我们可以通过将电流传递给function参数来避免这种情况，例如
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 return statement 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
>>> 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中，然后将其再次传递给递归调用.
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 result parameter, so we return it. Now, the last return statement has listSum(ls[1:], result + ls[0]), where we add the first element to the current result and pass it again to the recursive call.
这可能是了解尾声的好时机.它与Python无关，因为它不执行尾调用优化.
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.
传递索引版本
现在，您可能会认为我们正在创建许多中间列表.我可以避免吗?
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
内部功能版本
如果现在查看函数定义，您将向其传递三个参数.假设您将以API形式发布此函数.当用户实际找到列表的总和时，传递三个值是否方便?
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?
不.我们对于它可以做些什么呢?我们可以创建另一个在实际listSum函数本地的函数，并且可以像这样将所有与实现相关的参数传递给它
Nope. What can we do about it? We can create another function, which is local to the actual listSum function and we can pass all the implementation related parameters to it, like this
>>> 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的用户.他们只需要传递要处理的列表即可.
Now, when the listSum is called, it just returns the return value of recursion inner function, which accepts the index and the result parameters. Now we are only passing those values, not the users of listSum. They just have to pass the list to be processed.
在这种情况下，如果您观察参数，则不会将ls传递给recursion，而是在其内部使用它.由于具有闭包属性，可以在recursion内部访问ls.
In this case, if you observe the parameters, we are not passing ls to recursion but we are using it inside it. ls is accessible inside recursion because of the closure property.
默认参数版本
现在，如果您想保持简单，而无需创建内部函数，则可以使用默认参数，例如
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
现在，如果调用方未显式传递任何值，则0将同时分配给index和result.
Now, if the caller doesn't explicitly pass any value, then 0 will be assigned to both index and result.
递归电源问题
现在，让我们将这些想法应用于另一个问题.例如，让我们尝试实现power(base, exponent)函数.它将把base的值返回到幂exponent.
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 base raised to the power 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
嗯，所以我们明白了. base乘以自身，exponent倍即可得出结果.好的，我们该如何处理.让我们尝试使用相同的功能来定义解决方案.
Hmmm, so we get the idea. The base multiplied to itself, exponent times gives the result. Okay, how do we approach it. Lets try to define the solution with the same function.
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，结果将是什么?结果将是相同的数字，对不对?我们获得了递归的基本条件:-)
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 :-)
= 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
好的，如何定义它的尾调用优化版本?让我们将当前结果作为参数传递给函数本身，并在满足基本条件时返回结果.让我们保持简单，直接使用默认参数方法.
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.
>>> 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值，并使用base减小多个result并将其传递给递归power调用.我们从值1开始，因为我们正相反地解决该问题.递归将像这样发生
Now, we reduce the exponent value in every recursive call and multiple result with base and pass it to the recursive power call. We start with the value 1, because we are approaching the problem in reverse. The recursion will happen like this
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:-)
Since exponent becomes zero, the base condition is met and the result will be returned, so we get 32 :-)
这篇关于Python递归的基础的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
