递归与助手函数

Question

抱歉如果这个问题有点笼统，但我刚开始学Python，很多时候我看到别人用递归编程时，他们会为主函数创建一个辅助函数，然后调用这个辅助函数，而这个辅助函数本身也是递归的。

这似乎和最简单的递归情况有点不同，比如求列表的和或者阶乘，这些情况下函数只是调用自己。

能不能有人更详细地解释一下这种技巧，最好能举个例子？

非常感谢。

例子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 是否为假值，而我实际上需要的是一个装饰器，或者作为替代：

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

其中 _some_function 是辅助函数。

具体来说，使用 2 允许一些抽象的灵活性。如果出于某种原因你不想使用 bstsearch，你可以直接把它换成其他函数在 __contains__ 中（这样你也能在不同地方重用代码）

Answer 2

其实在其他编程语言中，这种写法用得更频繁，因为在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

Answer 3

通常我这样做是因为递归函数比较复杂或者调用起来不太方便，所以我会写一个更方便的“包装器”。比如，想象一下一个解迷宫的函数。这个递归函数需要一个数据结构来记录迷宫中已经访问过的位置，但为了方便调用者，我只希望调用者传入一个要解决的迷宫。你可以在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)

我对这个例子进行了修改，现在它实际上是一个相当合理的例子。我们把参数强制转换为整数（这叫“鸭子类型”），但我们要求!=操作符不能因为这个转换而改变值；如果把它转换为int后值发生了变化（比如一个小数部分被截断的float值），我们就会拒绝这个参数。同样，我们也会检查负数并拒绝这些参数。然后实际的递归函数就非常信任，根本不进行任何检查。

如果你能提供一个你见过的代码示例，我可以给出更具体的回答。

编辑：好的，讨论一下你的示例。

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

这个很简单：“助手”函数是一个通用的递归函数，可以在任何有链表的节点上工作。然后包装函数是一个方法，知道如何找到self.head，也就是链表的头部。这个“助手”是一个类的成员函数，但它也可以是一个简单的函数，放在通用的数据结构库里。（在Python中这样做更有意义，因为这样的函数可以与任何有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，浪费时间……这并不是一个好主意！不如直接写两个包装器，让它们从正确的位置开始。简单。