Python 递归和辅助函数

Recursion and Helper Function

提问by Mat.S

Sorry if this is a general question but I am a beginner in Python and many times when I see other people code using recursion, they create a helper function for the main function and then call that helper function which itself is recursive.

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

This seems a bit different from the simplest cases of recursion for example (sum of lists, factorial) where the function only calls itself.

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

Can someone explain this technique more carefully perhaps with examples?

有人可以用例子更仔细地解释这种技术吗？

Much appreciated.

非常感激。

Example 1: (Reversing linked list using recursion)

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

Example 2: (Binary Search Tree)

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

采纳答案by steveha

Usually when I do this, it is because the recursive function is tricky or annoying to call, so I have a wrapper that is more convenient. For example, imagine a maze solver function. The recursive function needs a data structure to keep track of visited spots inside the maze, but for convenience to the caller I just want the caller to need to pass in a maze to solve. You can maybe handle this with a default variable in Python.

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

The other major reason I have done this is for speed. The recursive function is very trusting, and assumes its arguments are all valid; it just goes full speed ahead with the recursion. Then the wrapper function carefully checks all the arguments before making the first call to the recursive function. As a trivial example, factorial:

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

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)

I have edited this from the original, and now it's actually a pretty reasonable example. We coerce the argument to an integer ("duck typing") but we require that the !=operator not indicate it to have changed in value by this coercion; if converting it to intchanges the value (for example, a floatvalue that had a fractional part truncated) we reject the argument. Likewise, we check for negative and reject the argument. Then the actual recursive function is very trusting and contains no checks at all.

我已经从原文中编辑了这个，现在它实际上是一个非常合理的例子。我们将参数强制转换为整数（“鸭子类型”），但我们要求!=操作员不要通过这种强制方式指示它的值发生了变化；如果将其转换为int更改值（例如，float截断小数部分的值），我们将拒绝该参数。同样，我们检查否定并拒绝该论点。那么实际的递归函数是非常可信的，根本不包含任何检查。

I could give less vague answers if you posted an example you have seen of code that inspired this question.

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

EDIT: Okay, discussion of your examples.

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

• Example 1: (Reversing linked list using recursion)

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

Pretty simple: the "helper" function is a general recursive function that will work on any node in the class that has a linked list. Then the wrapper is a method function that knows how to find self.head, the head of the list. This "helper" is a class member function, but it could also be a simple function in a general data-structures stuff library. (This makes more sense in Python than in languages like C, because a function like this could work with any linked list that is a class with a member called forwardas its "next pointer" value. So you really could write this once and then use it with multiple classes that implement linked lists.)

很简单：“helper”函数是一个通用的递归函数，它可以在类中具有链表的任何节点上工作。然后包装器是一个方法函数，它知道如何找到self.head列表的头部。这个“助手”是一个类成员函数，但它也可以是通用数据结构材料库中的一个简单函数。（这在 Python 中比在 C 之类的语言中更有意义，因为这样的函数可以与任何链表一起使用，该链表是一个具有称为forward“下一个指针”值的成员的类。所以你真的可以写一次，然后使用它具有多个实现链表的类。）

• Example 2: (Binary Search Tree)

• 示例 2：（二叉搜索树）

The actual recursive function returns Noneif no node can be found with the specified key. Then there are twowrappers: one that implements __contains__(), which works just fine if it returns None; and valueOf(), which raises an exception if the key is not found. As the comment notes, two wrappers lets us solve two different problems with a single recursive function.

None如果找不到具有指定 的节点，则实际递归函数返回key。然后有两个包装器：一个实现了__contains__()，如果它返回就可以正常工作None；和valueOf()，如果未找到密钥，则会引发异常。正如评论所指出的，两个包装器让我们可以用一个递归函数解决两个不同的问题。

Also, just as with the first example, the two wrappers kick off the search in a specific location: self._root, the root of the tree. The actual recursive function can be started anywhere inside a tree.

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

If __contains__()were implemented with a default argument of a node to search, and the default was set to some unique value, it could check for the special value and start at the root in that case. Then when __contains__()is called normally, the unique value would be passed in, and the recursive function could know that it needs to look at the special location self._root. (You can't just pass in self._rootas the default value, because the default value is set at compile time, and the class instance can change after that, so it wouldn't work right.)

如果__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

Note that while I said it couldbe implemented as I show here, I didn't say I prefer it. Actually I prefer the two wrappers version. This is a little bit tricky, and it wastes time on every recursive call checking to see if subtree is UniqueValue. More complex and wastes time... not a win! Just write the two wrappers, which start it off in the right place. Simple.

请注意，虽然我说它可以像我在这里展示的那样实施，但我并没有说我更喜欢它。其实我更喜欢两个包装版本。这有点棘手，它浪费时间在每次递归调用检查以查看subtree is UniqueValue. 更复杂，浪费时间......不是胜利！只需编写两个包装器，在正确的位置开始它。简单的。

回答by Snakes and Coffee

From my experience (and my experience only), I use this style of coding when

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

1. The recursion is only useful in the larger function (not very recommended, but I have some bad habits)

2. There needs to be preparation done for the function, but only once (instead of a flag or other switch)

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

2. 需要为函数做准备，但只需要一次（而不是标志或其他开关）

One way I use it is for logging purposes, while avoiding re-logging levels

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

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

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

Otherwise, logwould be called for each recursive level of the factorial function, something I may not desire.

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

Another usage would be to resolve default arguments.

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

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

Would check if xis falsey for every iteration, while what I actually need is a decorator, or as an alternative:

会检查x每次迭代是否为假，而我实际需要的是一个装饰器，或者作为替代：

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

where _some_functionis the helper function.

_some_function辅助函数在哪里。

Specifically with 2, it allows for some freedom of abstraction. If for some reason you didn't want to use a bstsearch, you could just swap it for some other function in __contains__(and you'd also be able to reuse code in different places)

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

回答by Stjepan Bakrac

This is actually used more often in other languages, because python can usually emulate that behavior with optional arguments. The idea is that the recursion gets a number of initial arguments, that the user doesn't need to provide, which help keep track of the problem.

这实际上在其他语言中更常用，因为 python 通常可以使用可选参数模拟该行为。这个想法是递归获得一些用户不需要提供的初始参数，这有助于跟踪问题。

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

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

Here it's used to set a starting parameter to 0, so the user doesn't have to provide it. However, in python you can emulate it by making accoptional:

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

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