Python中递归的基础知识

Question

"编写一个递归函数,"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

我需要基本的方法来执行此操作,因为不允许使用特殊的内置函数.

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.这被称为递归的基本条件.当满足基本条件时,递归将结束.现在,让我们尝试实现它.

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

简单版

>>> 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无关,因为它不执行Tail调用优化.

传递索引版本

现在,您可能认为我们正在创建这么多中间列表.我可以避免吗？

当然可以.您只需要接下来要处理的项目的索引.但现在,基本情况将有所不同.由于我们将要传递索引,我们如何确定整个列表的处理方式？好吧,如果索引等于列表的长度,那么我们已经处理了它中的所有元素.

>>> 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每个递归调用和多个resultwith 的值,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:-)