How do you do recursion in reverse?

Question

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?

Answer 1

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

Answer 2

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.