Python 中的递归基础 [英] Basics of recursion in Python
问题描述
"写一个递归函数，"listSum"它接受一个整数列表并返回列表中所有整数的总和".
示例:
<预><代码>>>>listSum([1, 3, 4, 5, 6])19我知道如何以另一种方式做到这一点，但不是以递归方式.
def listSum(ls):我 = 0s = 0当我 <连(ls):s = s + ls[i]我 = 我 + 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.这称为递归的基本条件.当满足基本条件时，递归将结束.现在，让我们尝试实现它.
这里的主要内容是拆分列表.您可以使用切片来做到这一点.
简单版
<预><代码>>>>def listSum(ls):... # 基本条件...如果不是ls:...返回0...... # 第一个元素 + 用其余元素调用 `listsum` 的结果...返回 ls[0] + listSum(ls[1:])>>>>>>listSum([1, 3, 4, 5, 6])19<小时>
尾调用递归
一旦你理解了上面的递归是如何工作的，你就可以试着让它变得更好一点.现在，要找到实际结果，我们还取决于前一个函数的值.return 语句不能立即返回值，直到递归调用返回结果.我们可以通过将当前传递给函数参数来避免这种情况，就像这样
这里，我们在参数中传递和的初始值，在listSum([1, 3, 4, 5, 6], 0)中为零.然后，当满足基本条件时，我们实际上是在累加 result 参数中的总和，因此我们将其返回.现在，最后一个 return 语句有 listSum(ls[1:], result + ls[0])，我们将第一个元素添加到当前 result 并将其再次传递给递归调用.
这可能是了解尾调用的好时机.它与 Python 无关，因为它不进行尾调用优化.
<小时>传递索引版本
现在，您可能认为我们正在创建如此多的中间列表.我可以避免这种情况吗?
当然可以.您只需要接下来要处理的项目的索引.但现在，基础条件将有所不同.既然我们要传递索引，我们将如何确定整个列表是如何处理的?那么，如果索引等于列表的长度，那么我们已经处理了其中的所有元素.
<预><代码>>>>def listSum(ls, index, result):... # 基本条件...如果索引 == len(ls):...返回结果...... # 调用下一个索引并将当前元素添加到结果中... return listSum(ls, index + 1, result + ls[index])...>>>listSum([1, 3, 4, 5, 6], 0, 0)19<小时>
内部函数版本
如果您现在查看函数定义，您将向其传递三个参数.假设您要将此函数作为 API 发布.当用户真正找到一个列表的总和时，是否方便用户传递三个值?
没有.我们对于它可以做些什么呢?我们可以创建另一个函数，它是实际 listSum 函数的本地函数，我们可以将所有与实现相关的参数传递给它，就像这样
现在，当listSum被调用时，它只返回recursion内部函数的返回值，它接受index和<代码>结果参数.现在我们只传递这些值，而不是 listSum 的用户.他们只需要传递要处理的列表.
在这种情况下，如果您观察参数，我们不会将 ls 传递给 recursion，而是在其中使用它.由于闭包属性，ls 可以在 recursion 内部访问.
默认参数版本
现在，如果你想保持简单，不创建内部函数，你可以使用默认参数，就像这样
<预><代码>>>>def listSum(ls, index=0, result=0):... # 基本条件...如果索引 == len(ls):...返回结果...... # 调用下一个索引并将当前元素添加到结果中... 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幂(5, 2) = 25幂(3, 4) = 81现在，我们如何递归地做到这一点?让我们试着了解这些结果是如何实现的.
power(2, 5) = 2 * 2 * 2 * 2 * 2 = 32幂(5, 2) = 5 * 5 = 25幂(3, 4) = 3 * 3 * 3 * 3 = 81嗯，所以我们明白了.base 乘以自身，exponent 乘以结果.好的，我们如何处理它.让我们尝试定义具有相同功能的解决方案.
power(2, 5) = 2 * power(2, 4)= 2 * (2 * 幂(2, 3))= 2 * (2 * (2 * 幂(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好的，让我们实现它.
<预><代码>>>>定义功率(基数，指数):... # 基数条件，如果`exponent` 小于等于1，则返回`base`...如果指数 <= 1:...返回基地......返回基数 * 幂(基数，指数 - 1)...>>>功率(2, 5)32>>>功率(5, 2)25>>>功率(3, 4)81好的，将如何定义它的 Tail 调用优化版本?让我们将当前结果作为参数传递给函数本身，并在满足基本条件时返回结果.让我们保持简单，直接使用默认参数方法.
<预><代码>>>>def power(基数，指数，结果=1):... # 由于我们从 `1` 开始，基本条件将是指数达到 0...如果指数 <= 0:...返回结果......返回幂(基数，指数 - 1，结果 * 基数)...>>>功率(2, 5)32>>>功率(5, 2)25>>>功率(3, 4)81现在，我们使用 base 减少每次递归调用和多个 result 中的 exponent 值，并将其传递给递归 power 调用.我们从值 1 开始，因为我们正在反向处理问题.递归会像这样发生
power(2, 5, 1) = power(2, 4, 1 * 2)= 幂(2, 4, 2)= 幂(2, 3, 2 * 2)= 幂(2、3、4)= 幂(2, 2, 4 * 2)= 幂(2, 2, 8)= 幂(2, 1, 8 * 2)= 幂(2、1、16)= 幂(2, 0, 16 * 2)= 幂(2, 0, 32)由于exponent变为零，满足基本条件并且返回result，所以我们得到32 :-)
"Write a recursive function, "listSum" that takes a list of integers and returns the sum of all integers in the list".
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.
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 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.
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 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
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.
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.
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?
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
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.
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.
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 0 will be assigned to both index and 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 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
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))))
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
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.
>>> 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 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)
Since exponent becomes zero, the base condition is met and the result will be returned, so we get 32 :-)
这篇关于Python 中的递归基础的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
