递归和辅助函数

Question

抱歉，如果这是一个普通的问题，但我是Python的初学者，很多时候当我看到其他人使用递归编写代码时，他们会为主函数创建一个helper函数，然后调用这个helper函数，它本身就是递归的。

这似乎有点不同于最简单的递归情况，例如（列表和，阶乘），其中函数只调用自身。

有人能更仔细地解释这个技巧吗？也许可以举个例子？

非常感谢。

示例1:（使用递归反转链表）

def revert_list(self):
    self.head = self._revert_helper(self.head)


def _revert_helper(self, node):
    temp = None
    if node.forward == None: 
        return node
    else:
        temp = self._revert_helper(node.forward)
        node.forward.forward = node
        node.forward = None
    return temp

示例2:（二进制搜索树）

def __contains__(self, key):
    return self._bstSearch(self._root, key)

# Returns the value associated with the key.
def valueOf(self, key):
    node = self._bstSearch(self._root, key)
    assert node is not None, "Invalid may key."
    return node.value

# Helper method that recursively searches the tree for a target key:
# returns a reference to the Node. This allows 
# us to use the same helper method to implement
# both the contains and valueOf() methods of the Map class.

def _bstSearch(self, subtree, target):
    if subtree is None:  # base case
        return None
    elif target < subtree.key: # target is left of the subtree root
        return self._bstSearch(subtree.left) 
    elif target > subtree.key: # target is right of the subtree root
        return self.bstSearch(subtree.right) 
    else:                      # base case
        return subtree 

Answer 1

根据我的经验（仅限于我的经验），当

1. 递归只在较大的函数中有用（不是很推荐，但我有一些坏习惯）

2. 需要为该功能做准备，但仅需一次（而不是标记或其他开关）

我使用它的一种方法是为了记录日志，同时避免重新记录级别

def _factorial(x):
    return 1 if x == 0 else x*_factorial(x)

@log #assuming some logging decorator "log"
def factorial(x):
    return _factorial(x)

否则，将为阶乘函数的每个递归级别调用log，这可能是我不需要的。

另一个用法是解析默认参数。

def some_function(x = None):
    x = x or set() #or whatever else
    #some stuff
    return some_function()

会检查每次迭代的x是否是错误的，而我实际上需要的是一个decorator，或者作为一个替代：

def some_function(x = None):
   return _some_function(x if x else set())

其中_some_function是helper函数。

特别是对于2，它允许一些抽象的自由。如果出于某种原因您不想使用bstsearch，您可以将其替换为__contains__中的其他函数（您还可以在不同的地方重用代码）

Answer 2

通常当我这样做的时候，是因为递归函数很难调用或者很烦人，所以我有一个更方便的包装器。例如，想象一个迷宫解算器函数。递归函数需要一个数据结构来跟踪迷宫中的访问点，但为了方便调用方，我只希望调用方需要在迷宫中传递来解决问题。您可以使用Python中的默认变量来处理这个问题。

我这样做的另一个主要原因是为了速度。递归函数非常可靠，并且假设它的参数都是有效的；它只是全速进行递归。然后包装器函数在第一次调用递归函数之前仔细检查所有参数。作为一个简单的例子，阶乘：

def _fact(n):
    if n == 0:   # still need to handle the basis case
        return 1
    return n*_fact(n-1)

def fact(n):
    n0 = int(n)
    if n0 != n:
        raise ValueError("argument must make sense as an int")
    if n < 0:
        raise ValueError("negative numbers not allowed")
    return _fact(n)

我从原稿中编辑了这个，现在它是一个非常合理的例子。我们将参数强制为整数（“duck typing”），但我们要求!=运算符不指示它通过此强制更改了值；如果将其转换为int更改了值（例如，截断了小数部分的float值），则拒绝该参数。同样地，我们检查是否有否定，并拒绝这个论点。那么实际的递归函数非常可信，根本不包含检查。

如果你发布了一个你看到的激发这个问题的代码示例，我可以给出不那么含糊的答案。

编辑：好的，讨论你的例子。

• 示例1:（使用递归反转链表）

非常简单：“helper”函数是一个通用的递归函数，它可以在类中任何具有链表的节点上工作。包装器是一个方法函数，它知道如何找到列表的头self.head。这个“helper”是一个类成员函数，但它也可以是通用数据结构素材库中的一个简单函数。（这在Python中比在C等语言中更有意义，因为这样的函数可以处理任何链表，链表是一个名为forward的成员作为其“下一个指针”值的类。因此，您可以编写一次，然后将其与实现链接列表的多个类一起使用。）

• 示例2:（二进制搜索树）

如果找不到具有指定key的节点，则实际递归函数返回None。然后有两个包装器：一个实现__contains__()，如果返回None，则工作正常；另一个实现valueOf()，如果找不到密钥，则引发异常。如注释所述，两个包装器允许我们用一个递归函数解决两个不同的问题。

同样，就像第一个例子一样，这两个包装器在一个特定的位置开始搜索：self._root，树的根。实际的递归函数可以在树中的任何位置启动。

如果__contains__()是用要搜索的节点的默认参数实现的，并且默认值被设置为某个唯一值，那么它可以检查特殊值并在这种情况下从根开始。然后，当正常调用__contains__()时，将传入唯一值，递归函数可以知道它需要查看特殊位置self._root。（不能仅仅将self._root作为默认值传入，因为默认值是在编译时设置的，并且类实例可以在这之后更改，因此它不会正常工作。）

class UniqueValue:
    pass

def __contains__(self, key, subtree=UniqueValue):
    if subtree is UniqueValue:
        subtree = self._root

    if subtree is None:  # base case
        return None
    elif key < subtree.key: # target is left of the subtree root
        return self.__contains__(key, subtree.left) 
    elif key > subtree.key: # target is right of the subtree root
        return self.__contains__(key, subtree.right) 
    else:                      # base case
        return subtree

注意，虽然我说过可以像我在这里展示的那样实现，但我并没有说我更喜欢它。实际上我更喜欢两个包装版。这有点棘手，而且每次递归调用检查是否subtree is UniqueValue都会浪费时间。更复杂，浪费时间。。。不是胜利！只需写两个包装纸，在正确的地方开始。很简单。

Answer 3

这实际上在其他语言中使用得更频繁，因为python通常可以使用可选参数来模拟这种行为。其思想是递归得到许多用户不需要提供的初始参数，这有助于跟踪问题。

def sum(lst):
    return sumhelper(lst, 0)

def sumhelper(lst, acc):
    if lst:
        acc += lst[0]
        return sumhelper(lst[1:], acc)
    return acc

这里，它用于将起始参数设置为0，因此用户不必提供它。但是，在python中，可以通过将acc设为可选来模拟它：

def sum(lst, acc=0):
    if lst:
        acc += lst[0]
        return sum(lst[1:], acc)
    return acc