Reputation: 143
For example, in the fibonacci sequence, given two base cases f(0) = 1 and f(1) = 1, it is quite straight forward to use recursion to obtain f(n). I would like to know if the reverse is possible, given a recurrence relation and f(n), could you back compute f(1)?
For example, given a recurrence relation:
f(n) = (-1)^{n+1} (2*f(n-1) - f(n-2)) (n >= 0)
Since f(n) involves f(n-1) and f(n-2), we know from mathematical induction that we require 2 base cases. However, what if instead of being given the 2 base cases f(1) and f(0), we were instead given:
f(0) = 1
f(15) = -17711
How can we implement a recursive algorithim in python to obtain f(1), that is recursion in reverse?
Upvotes: 1
Views: 125
Reputation: 143
I like to thank John Coleman and Samwise for pointing out that recursion is probably not possible. Here is my iterative solution for the problem. Basically i find f(2) in terms of f(1) and f(0)... f(3) in terms of f(1) and f(0) and so on until i hit f(a), then i can solve for 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
Upvotes: 1
Reputation: 71574
Taking the Fibonacci example, if
f(n) = f(n-1) + f(n-2)
then we can do algebraic manipulation to get:
f(n-2) = f(n) - f(n-1)
and therefore:
f(n) = f(n+2) - f(n+1)
So it's perfectly possible to go either backwards or forwards as long as we know we'll find a base case in whatever direction we're going.
>>> 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]
For your other example, I suspect there is not a solution:
>>> 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)]
since it doesn't look like the value of f(15)
is going to converge on the one you want with either higher or lower f(1)
values.
Upvotes: 1