回答问题

对不起,如果这是一个普遍的问题,但我是 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 

Answers

通常当我这样做时,是因为递归函数调用起来很棘手或烦人,所以我有一个更方便的包装器。例如,想象一个迷宫求解器函数。递归函数需要一个数据结构来跟踪迷宫内的访问点,但为了方便调用者我只希望调用者需要通过迷宫来解决。您可以使用 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:(二叉搜索树)

如果找不到具有指定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都会浪费时间。更复杂,浪费时间......不是胜利!只需编写两个包装器,它们在正确的位置开始。简单的。