5

我的问题是某种非常类似于递归的代码风格，但并不完全如此。引用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)

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

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)

忽略隐式记忆等优化，这会产生一系列函数调用，这些函数调用不是严格递归的，创建和调用各种新函数而不会调用同一个函数两次。尽管如此，所有这些函数都遵循一个通用模板，并且只是一遍又一遍地创建的同一个函数（可能具有不同的自由变量。

再一次，我们可以提出一个直接等价的（毕竟，类实际上只是闭包，对；）使用类的实现。这一点尤其重要，因为这种风格的[insert name here]用于例如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 在每个对象的基础上定义了一个简单的包装器，它本身每次都调用相同的函数——但这不一定是我们需要知道的，它也不需要对于类和对象的其他实现需要是正确的。但是，是的，严格来说它是相互递归的，以及......更多的东西，这是我想知道的另一件事。）

4

3 回答 3

2

正如您所指出的，这仍然是相互递归。我认为您要询问的“更多”没有名称。如果是的话，我从来没有听说过。

于 2010-04-19T14:05:53.670 回答
2

相互递归只是间接递归的一个特例。

于 2010-04-19T14:07:24.247 回答
1

显然，它被称为相互递归:)

这篇文章甚至给出了和你一样的例子，用odd?和even?函数。

于 2010-04-19T13:58:36.810 回答