Как называется такая взаимная "рекурсия"?

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)

Независимо от оптимизаций, таких как неявное запоминание и т. Д., Это создает цепочку вызовов функций, которые не являются строго рекурсивными, создавая и вызывая различные новые функции, никогда не вызывая одну и ту же функцию дважды. Тем не менее все эти функции следуют общему шаблону и представляют собой одну и ту же функцию, созданную снова и снова (возможно, с различными свободными переменными.

И снова, мы можем придумать прямо эквивалентную (в конце концов, классы - это на самом деле просто замыкания, верно;) реализацию с использованием классов. Это особенно важно, поскольку этот стиль [вставьте здесь имя] используется, например, в составном шаблоне. Разница заключается в том, что при использовании шаблона Composite и большинства применений (даже замыканий) экземпляры обычно создаются не на лету. Это по сути то же самое.

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

Как вы указываете, это все еще взаимная рекурсия. Я не думаю, что у "чего-то большего", о котором вы спрашиваете, есть имя; если это произойдет, я никогда не слышал это.

Answer 2

Взаимная рекурсия - это просто частный случай косвенной рекурсии.

Answer 3

Видимо, это называется Mutual Recursion:)

В статье даже приводится тот же пример, что и вы, с odd? а также even? функции.