Python递归的基础
“编写一个递归函数“ listSum”，该函数接受一个整数列表并返回列表中所有整数的和。”
例：
>>>> 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
我需要执行此操作的基本方法，因为不允许使用特殊的内置函数。
问题答案：
每当遇到这样的问题时，请尝试使用相同的函数表示该函数的结果。
在你的情况下，你可以通过将第一个数字与在列表中其余元素上调用同一函数的结果相加来获得结果。
例如，
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):
... # 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
尾调用递归
了解了上述递归的工作原理后，你可以尝试使其变得更好一点。现在，要找到实际结果，我们还取决于上一个函数的值。该每当遇到这样的问题时，请尝试使用相同的函数表示该函数的结果。
在你的情况下，你可以通过将第一个数字与在列表中其余元素上调用同一函数的结果相加来获得结果。
例如，
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):
... # 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参数来避免这种情况，例如
>>> def listSum(ls, result):
... if not ls:
... return result
... return listSum(ls[1:], result + ls[0])
...
>>> listSum([1, 3, 4, 5, 6], 0)
19
在这里，我们传递参数中和的初始值，即in中的零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)html" target="_blank">功能。它将把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语句无法立即返回值，直到递归调用返回结果为止。我们可以通过将电流传递给function参数来避免这种情况，例如
>>> def listSum(ls, result):
... if not ls:
... return result
... return listSum(ls[1:], result + ls[0])
...
>>> listSum([1, 3, 4, 5, 6], 0)
19
在这里，我们传递参数中和的初始值，即in中的零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
-
某些计算机编程语言允许模块或函数调用自身。 这种技术称为递归。 在递归中，函数α直接调用自身或调用函数β ，而函数β又调用原始函数α 。 函数α称为递归函数。 Example - 调用自身的函数。 int function(int value) { if(value < 1) return; function(value - 1); printf("%d ",valu
-
问题内容： 学习SQL，并有一些问题。我有2张桌子， 现在，我需要的是一个查询，该查询将基于标记要从哪个层次层次结构级别获取参数的参数，从每个层次结构级别返回表中的所有条目。 获取条目非常容易。 条目： 只是有父母的父母，而父母的父母是父母的父母，依此类推。这是我怀疑递归出现的地方。 有谁可以指导思想的吗？ 问题答案： 您对第一级的查询（此处与表格区别）应如下所示： 请注意的正确用法（不要总是与进
-
问题内容： 我在上面直接写了上面的内容，因此可能无法编译，但认为可以。 任何人都可以从存储的角度来简短地解释它的工作原理吗？它通过计算5 （5-1）开始，然后依次下降到4 （4-1）然后是3 *（3-1）.....直到达到1，它将只返回1，对吗？抱歉，我太粗略了，我只想知道这是如何工作的 谢谢 但随着工作的进行，它将获得各个阶段的值 5 （5-1）4 （4-1）… … … 这些如何存储然后取回，或
-
拜托，我需要你的帮助。我花了几个小时试图找出这些函数中的问题。我的老师想让我用一个递归运算给定2个数字。问题是，每次我启动程序并初始化函数时，都会出现这个错误。“RecursionError:调用Python对象时超过了最大递归深度”我没有使用位号，而是使用了StackOverflow中关于同一参数的其他答案中的代码。所以我想我真的没有掌握这个问题的概念: 如果用户在主菜单输入“1”：应该提示用户
-
本文向大家介绍详谈Python基础之内置函数和递归，包括了详谈Python基础之内置函数和递归的使用技巧和注意事项，需要的朋友参考一下 一、内置函数 下面简单介绍几个： 1.abs() 求绝对值 2.all() 如果 iterable 的所有元素都为真（或者如果可迭代为空），则返回 True 3.any() 如果 iterable 的任何元素为真，则返回 True。如果iterable为空，则返回
-
考虑Python中的这个基本递归： 根据斐波那契数列的（n-1）（n-2）函数，这是有道理的。 Python如何执行包含另一个递归的递归，这个递归不在同一代码行内，而是在同一代码行内？“finobacci(number-1)”是否完成所有递归，直到它到达“1”，然后它对“fibonacci(number-2)”做同样的事情，并将它们相加？ 作为比较，下面的递归函数将一个数“x”提升为“y”的幂，我