Как вы делаете рекурсию в обратном порядке? - PullRequest
Новая
       10

Как вы делаете рекурсию в обратном порядке?

1 голос
/ 21 апреля 2020

Например, в последовательности Фибоначчи, учитывая два базовых случая f (0) = 1 и f (1) = 1, довольно просто использовать рекурсию для получения f (n). Я хотел бы знать, возможно ли обратное, учитывая рекуррентное отношение и f (n), не могли бы вы вычислить обратно f (1)?

Например, учитывая рекуррентное отношение: 

f(n) = (-1)^{n+1} (2*f(n-1) - f(n-2))     (n >= 0)

Поскольку f (n) включает в себя f (n-1) и f (n-2), мы знаем из математической индукции, что нам требуется 2 базовых случая. Однако, что если вместо того, чтобы нам дали 2 базовых случая f (1) и f (0), нам вместо этого дали: 

f(0) = 1
f(15) = -17711

Как мы можем реализовать рекурсивный алгоритм в python, чтобы получить f (1), то есть рекурсия в обратном порядке?

Ответы [ 2 ]

1 голос
/ 22 апреля 2020

Я хотел бы поблагодарить Джона Колемана и Сэмвейса за то, что они указали, что рекурсия, вероятно, невозможна. Вот мое итеративное решение проблемы. По сути, я нахожу f (2) в терминах f (1) и f (0) ... f (3) в терминах f (1) и f (0) и так далее, пока не достигну f (a), затем я могу решить для F (1) 

def my_func(a, b):  # We are given f(a) = b

    memo_dict = {0: [1, 0], 1: [0, 1]} #coefficients in terms of f(0) and f(1)

    def generate_coefficients(n):
        if n == 0:
            return memo_dict[0]
        elif n == 1:
            return memo_dict[1]
        else:

            for i in range(2, n+1):

                prev_element = memo_dict[i-1]
                prev_element_f0_coeff = prev_element[0]
                prev_element_f1_coeff = prev_element[1]

                second_prev_element = memo_dict[i-2]
                second_prev_element_f0_coeff = second_prev_element[0]
                second_prev_element_f1_coeff = second_prev_element[1]

                memo_dict[i] = [((-1)**(i+1)) *
                                (2 * prev_element_f0_coeff
                                                - second_prev_element_f0_coeff),
                                 ((-1)**(i+1)) *
                                (2 * prev_element_f1_coeff
                                 - second_prev_element_f1_coeff)
                                ]

            return memo_dict[n]

    def helper(n):
        a_coeff_list = generate_coefficients(a)
        a_f0_coeff = a_coeff_list[0]
        a_f1_coeff = a_coeff_list[1]

        f1_value = (b - a_f0_coeff * 1) / a_f1_coeff

        return f1_value

    return helper
1 голос
/ 21 апреля 2020

Если взять пример Фибоначчи, если 

f(n) = f(n-1) + f(n-2)

, то мы можем выполнить алгебру c манипуляцию, чтобы получить: 

f(n-2) = f(n) - f(n-1)

и, следовательно: 

f(n) = f(n+2) - f(n+1)

Так что вполне возможно go либо в обратном, либо в прямом направлении, если мы знаем, что найдем базовый случай в любом направлении, в котором движемся. 

>>> def f(n: int) -> int:
...     if n < 14:  # count up to 14
...         return f(n+2) - f(n+1)
...     elif n == 14:
...         return 377
...     elif n == 15:
...         return 610
...     else: # count back to 15
...         return f(n-2) + f(n-1)
...
>>> [f(n) for n in range(20)]
[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181]

Для вашего другого примера, я подозреваю, что не является решением: 

>>> from typing import Callable
>>>
>>> def recurrence_func(f_1: int) -> Callable[[int], int]:
...     """
...     Generates a version of the recurrence relation 
...     function with the given base case value of f(1).
...     """
...     f_0 = 1
...     def f(n: int) -> int:
...         if n == 0:
...             return f_0
...         if n == 1:
...             return f_1
...         return (-1**(n+1)) * (2*f(n-1) - f(n-2))
...     return f
...
>>>
>>> [(f_1, recurrence_func(f_1)(15)) for f_1 in range(-2, 3)]
[(-2, -470832), (-1, -275807), (0, -80782), (1, 114243), (2, 309268)]

, поскольку не похоже, что значение f(15) будет сходиться с тем, которое вам нужно, с более высокими или более низкими значениями f(1).

...