Создать рекурсивную функцию, а также определение закрытой функции

Question

Цель этого назначения - взять рекуррентное отношение, заданное внизу, а затем создать рекурсивную функцию под recFunc(n), а также определение закрытой функции под nonRecFunc(n).Закрытая функция означает, что наша функция должна зависеть исключительно от n, и что ее выходные данные должны точно соответствовать рекурсивной функции.Затем найдите значение для n = 15 и n = 20 и используйте его, как указано ниже.Вероятно, вам нужно использовать характеристическое уравнение для решения этой проблемы.

Какое значение для nonRecFunc(20) (деленное на) nonRecFunc(15), округленное до ближайшего целого числа.

Проблема:

Решить рекуррентное соотношение a_n = 12a_n-1 - 32a_n-2 с начальными условиями a_0 = 1 и a_1 = 4.

Я не понимаю, как мне следует атаковать эту проблему и как я могу использовать рекурсию для ее решения.

def recFunc(n):
    if n == 0:
        return 1
    elif n == 1:
        return 2
    else:
        return recFunc(n - 1) + 6 * recFunc(n - 2)


def nonRecFunc(n):
    return 4/5 * 3 ** n + 1/5 * (-2) ** n


for i in range(0,10):
    print(recFunc(i))
    print(nonRecFunc(i))
    print()

Answer 1

Как уже упоминалось в моем комментарии выше, я оставляю рекурсивное решение для вас. Для более математического вопроса о нерекурсивном решении рассмотрим это:

у вас есть

x_n = a x_ (n-1) + b x_ (n-2)

Это означает, что изменение x более или менее пропорционально x как x_n и x_ (n-1) будет того же порядка. Другими словами, мы ищем тип функции, дающий

d f (n) / d n ~ f (n)

Это что-то экспоненциальное. Таким образом, приведенное выше предположение

x_n = alpha t ^ n + beta s ^ n

(позже при решении для с и t мотивация для этого становится ясной) из начальных значений мы получаем

альфа + бета = 1

и

альфа т + бета с = 2

Рекурсия обеспечивает

alpha t ^ n + beta s ^ n = a (alpa t ^ (n-1) + beta s ^ (n-1)) + b (alpa t ^ (n-2) + beta s ^ (n-2))

или

t ^ 2 alpha t ^ (n-2) + s ^ 2 beta s ^ (n-2) = a (t alpa t ^ (n-2) + s beta s ^ (n-2) )) + b (alpa t ^ (n-2) + beta s ^ (n-2))

Это уравнение справедливо для всех n , так что вы можете вывести уравнение для t и s .

Включение результатов в приведенные выше уравнения дает вам нерекурсивное решение.

Попробуйте воспроизвести его, а затем перейдите к фактическому заданию.

Приветствие.