Рекурсия без ссылки и назначения - PullRequest
Новая
       7

Рекурсия без ссылки и назначения

6 голосов
/ 09 марта 2020

Задаче является рекурсивная функция в python (или аналогичная), можно ли ее переписать так, чтобы она не ссылалась на себя. Я сделал простой пример, который относится к проблеме. Конечно, сделать его нерекурсивной функцией недопустимо. Он все равно должен выполнять тот же процесс рекурсии. 

def fact(n):
  if n == 0:
    return 1
  return n * fact(n - 1)

Это также эквивалентно сокращенной комбинации. 

fact = lambda n: 1 if n == 0 else n * fact(n - 1)

В этом примере я не должен вызывать fact внутри определение функции.

Редактировать:

Дополнительные ограничения: назначения не должны быть необходимыми для работы решения.

Одно решение (из комментариев) без дополнительного ограничения - создать две функции a и b, которые поочередно вызывают друг друга и эффективно работают факториально. Это недопустимо, потому что для этого необходимо назначить две функции в двух переменных.

Быстрый пример функции, которая не требует назначения: 

f = lambda x: x + 1

Для ее выполнения на arugment 55, я мог бы просто написать 

(lambda x: x + 1)(55)

Так что назначение не было необходимым.

Есть какие-нибудь намеки на это? Или меня обманули до невозможной проблемы?

Ответы [ 2 ]

9 голосов
/ 09 марта 2020

Вы можете использовать что-то вроде лямбда-исчисление , чтобы избежать присваивания и самоссылки, заменив оба на доступ к аргументу анонимной функции. Например: 

fact = (lambda f: f(f))(lambda f: (lambda n: n*f(f)(n-1) if n else 1))

Протестировано в Ideone .

Некоторые подробности ниже для получения дополнительной информации.

Я знаю, что лямбда-исчисление известно как мощный (полный по Тьюрингу), но минималистичный c «язык программирования». Он использует только идентификаторы для переменных, которые могут быть связаны (в значительной степени с аргументами функции) или не связаны (в основном, когда речь идет о частях выражения). Так что это было хорошей отправной точкой.

Канонический путь к express рекурсии в лямбда-исчислении - использование комбинатора с фиксированной точкой . Хотя этот комбинатор может быть наивно выражен в синтаксисе Python, тщательная оценка приводит к бесконечной рекурсии.

Код https://rosettacode.org/wiki/Y_combinator#Python, упомянутый в комментариях, позволяет избежать этой бесконечной рекурсии, задерживая один из рекурсивные вызовы, пока функция не будет вызвана. Но я бы предпочел оставить подробное объяснение этого подхода в отдельном ответе.

Какова основная идея выражения рекурсии в лямбда-исчислении? Передача функции в качестве аргумента самой себе. Итак, я начал с этого: 

lambda f: f(f)  # λ f.f f

Мне нужно передать этой функции другую функцию, которая принимает функцию в качестве значения. Как lambda f: …. И результатом этого вызова должна быть функция, которая должна принимать n в качестве аргумента для вычисления факториала. Мое первое приближение состояло в том, чтобы думать о f как о выражении для рекурсивного вызова, поэтому сначала я произнес: 

(lambda f: f(f))(lambda f: (lambda n: n*f(n-1) if n else 1))

Но потом я понял, что это неправильно: f сам по себе не является рекурсивным вызовом , поскольку f - это функция, которая принимает аргумент f. Таким образом, f(f) является рекурсивным вызовом, приводящим к решению, которое я напечатал в начале.

1 голос
/ 09 марта 2020

Скорее всего, это совсем не то, о чем идет речь, но с некоторыми inspect / types маги c вы можете восстановить вызываемую функцию ... 

import types, inspect


def fact(n):
    frame = inspect.currentframe()
    fn = types.FunctionType(frame.f_code, frame.f_globals)

    if n == 0:
        return 1
    return n * fn(n - 1)


print(fact(10))
...