Эффективный подход для рекурсивных функций

Question

Я дал три функции рекурсии fun1(int), fun2(int), fun3(int). Все три функции зависят друг от друга, то есть

fun1(m) = a * fun2(m-1) - b * fun3(m-1) 
fun2(m) = c * fun1(m-1) - d * fun3(m-1) 
fun3(m) = e * fun1(m-1) + f * fun2(m-1) 

Я должен найти значение для любой из этих функций. Как это сделать эффективно (с точки зрения временной сложности и нерекурсивного подхода)?

Answer 1

Вы можете выразить свои три уравнения в виде матрицы умножения:

[f1(m)] = [0 a -b] [f1(m-1)] 
[f2(m)] = [c 0 -d] [f2(m-1)] 
[f3(m)] = [e f 0] [f3(m-1)] 

Тогда:

[f1(m)] = [0 a -b]^m [f1(0)] 
[f2(m)] = [c 0 -d] [f2(0)] 
[f3(m)] = [e f 0] [f3(0)] 

Так если вы знаете значения f1 (0) , f2 (0), f3 (0), вы можете вычислить значения для f1 (m), f2 (m) и f3 (m) в O (log m) арифметических операциях, вычислив мощность матрицы с помощью возведения в степень возведения в квадрат.

Answer 2

Если ваши коэффициенты a, b, c, d, e, f не зависят от m, а являются абсолютными константами (или даже произвольными многочленами переменной, не зависящими от m), то повторяемость, которую вы описываете, линейный. Такой случай полностью решается Petkovšek's algorithm.

Алгоритм в основном позволяет вычислить так называемую замкнутую форму повторения. Он подробно описан здесь: https://www.math.upenn.edu/~wilf/AeqB.html