如何反向执行递归

Question

例如，在斐波那契序列中，给定两种基本情况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(，即反向递归？

Answer 1

以Fibonacci为例，如果

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

然后我们可以进行代数运算得到：

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

因此：

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

因此，只要我们知道我们会在任何方向上找到一个基本情况，就完全有可能倒退或前进。

>>> 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)]

因为看起来CCD_ 1的值不会收敛于具有更高或更低CCD_。

Answer 2

我要感谢John Coleman和Samwise指出递归可能是不可能的。这是我对这个问题的迭代解决方案。基本上，我根据f(1(和f(0(找到f(2(。。。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