python - 递归和辅助函数

Question

抱歉，如果这是一个普遍的问题，但我是 Python 的初学者，很多时候当我看到其他人使用递归进行编码时，他们为 main 函数创建了一个辅助函数，然后调用该辅助函数，它本身就是递归的。

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

有人可以通过示例更仔细地解释这种技术吗？

非常感激。

示例 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

score 7 · Accepted Answer

这实际上在其他语言中更常用，因为 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

score 4 · Accepted Answer

通常当我这样做时，是因为递归函数调用起来很棘手或烦人，所以我有一个更方便的包装器。例如，想象一个迷宫求解器函数。递归函数需要一个数据结构来跟踪迷宫内的访问点，但为了方便调用者我只希望调用者需要通过迷宫来解决。您可以使用 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列表的头部。这个“助手”是一个类成员函数，但它也可以是通用数据结构库中的一个简单函数。（这在 Python 中比在 C 之类的语言中更有意义，因为这样的函数可以与任何链表一起使用，该链表是一个类，其成员称为forward“下一个指针”值。所以你真的可以写一次然后使用它具有多个实现链表的类。）

示例 2：（二叉搜索树）

None如果在指定的 . 中找不到节点，则实际的递归函数返回key。然后有两个包装器：一个实现了__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. 更复杂，浪费时间......不是胜利！只需编写两个包装器，它们在正确的位置开始。简单的。

score 3 · Accepted Answer

根据我的经验（仅我的经验），我在以下情况下使用这种编码风格

递归只在较大的函数中有用（不是很推荐，但我有一些不好的习惯）
需要为函数做准备，但只需要一次（而不是标志或其他开关）

我使用它的一种方法是用于记录目的，同时避免重新记录级别

def _factorial(x):
    如果 x == 0 则返回 1 否则 x*_factorial(x)

@log #假设一些日志装饰器“日志”
默认阶乘（x）：
    返回 _factorial(x)

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

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

def some_function(x = None):
    x = x 或 set() #或其他
    #一些东西
    返回一些函数（）

会检查x每次迭代是否为假，而我真正需要的是装饰器，或者作为替代方案：

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

_some_function辅助函数在哪里。

具体来说2，它允许一些抽象的自由。如果由于某种原因你不想使用 bstsearch，你可以将它换成其他函数__contains__（你也可以在不同的地方重用代码）

python - 递归和辅助函数

3 回答 3

Related

Reference