这种相互的“递归”叫什么？

Question

我的问题是一种非常类似递归的代码样式，但这不是很好。用Wikipedia的话来说，递归是“一种定义函数的方法，其中被定义的函数应用于它自己的定义中”。类似地，相互递归应用另一个函数，它直接或间接地应用我们定义的函数。在

问题是我正在考虑和处理的代码没有使用相同的函数！它在另一个函数（作为方法或闭包）中使用相同的代码。在

这里的问题是，虽然我的代码是相同的，但函数不是。请看以下基本的相互递归示例：

def is_even(x):
    if x == 0:
        return True
    else:
        return is_odd(x - 1)

def is_odd(x):
    if x == 0:
        return False
    else:
        return is_even(x - 1)

这有点直观，而且非常清楚地相互递归。但是，如果我将每个函数包装为每次调用都创建一次的内部函数，就不那么清楚了：

^{pr2}$

忽略诸如隐式记忆等优化，这会产生一系列严格意义上不递归的函数调用，创建和调用各种新函数，而不必调用同一个函数两次。尽管如此，所有这些函数都遵循一个共同的模板，并且只是反复创建的同一个函数（可能使用不同的自由变量）。在

同样，我们可以使用类来实现一个直接等价的实现（毕竟，类实际上只是闭包，对吧；）。这一点尤其重要，因为这种样式的[在此处插入名称]用于Composite Pattern。不同之处在于，对于复合设计模式，以及大多数用途（甚至闭包），实例通常不是动态创建的。基本上还是一样的。在

class EvenChecker(object):
    def check(self, x):
        if x == 0:
            return True
        else:
            return OddChecker().check(x - 1)

class OddChecker(object):
    def check(self, x):
        if x == 0:
            return False
        else:
            return EvenChecker().check(x - 1)

def is_even3(x):
    return EvenChecker().check(x)

def is_odd3(x):
    return OddChecker().check(x)

这一次的链是对象创建和方法调用，但原理是一样的。（实际上，我要指出的是，它稍有不同，因为Python在每个对象的基础上定义了一个简单的包装器，它本身每次都调用同一个函数——但这不一定是我们需要知道的，对于其他类和对象的实现也不需要是真的。但是的，严格地说，它是相互递归的，而且。。。更重要的是，这是我想知道的另一件事。）

Answer 1

相互递归只是indirect recursion的一个特例。在

Answer 2

正如您所指出的，这仍然是相互递归。我不认为你所问的“更多的东西”有名字；如果有，我从未听说过。在

Answer 3

显然，它被称为Mutual Recursion：）

本文甚至给出了与您相同的示例，包括odd?和{}函数。在