这种相互“递归”称作什么？

Question

我遇到的问题是关于一种代码风格，它看起来很像递归，但又不完全是递归。递归的定义是，函数在自己的定义中调用自己。类似地，互递归是指一个函数调用另一个函数，而这个被调用的函数又直接或间接地调用我们正在定义的函数。

问题在于，我所想到的代码并不是使用同一个函数！它是在另一个函数中使用相同的代码（作为方法或闭包）。

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

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)

这个例子有点直观，而且非常明显是互递归的。然而，如果我把每个函数都包装成一个在每次调用时创建的内部函数，那就不那么清楚了：

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

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

def is_even2(x):
    return make_is_even()(x)

def is_odd2(x):
    return make_is_odd()(x)

不考虑像隐式记忆化等优化，这会产生一连串的函数调用，这并不是严格意义上的递归，因为它创建并调用各种新的函数，而从来没有调用同一个函数两次。尽管如此，所有这些函数遵循一个共同的模板，只是同一个函数被反复创建（可能有不同的自由变量）。

再一次，我们可以用类来实现一个直接等价的版本（毕竟，类实际上就是闭包，对吧；）这尤其重要，因为这种风格的[在这里插入名称]在例如组合模式中被使用。不同之处在于，在组合设计模式及其大多数用法中（即使是闭包），实例通常不是即时创建的。它本质上仍然是相同的。

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在每个对象的基础上定义了一个简单的包装器，每次都调用同一个函数——但这并不是我们需要知道的事情，也不一定适用于其他类和对象的实现。不过，严格来说，它确实是互递归的，还有其他一些特性，而我想知道的就是那其他的东西。)

函数调用设计模式递归闭包方法调用对象创建组合模式互递归

这种相互“递归”称作什么？

3 个回答

撰写回答