Efficient approach for recursive functions

Question

I have given three recursion functions fun1(int ), fun2(int ), fun3(int). All three function depends on each other i.e.

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)

I have to find value for any of these function. How to do it efficiently(in terms of time complexity and non-recursion approach)?

Such function descriptions are incomplete: you need a value for which the functions result is known. — trincot
– trincot, Commented Feb 21, 2017 at 20:39
Actually afun2(m-1) is a* fun2(m-1) and same for other functions. While typing question * got removed automatically. Also Assuming fun1(0)=fun2(0)=fun3(0)=1. — abhi2244
– abhi2244, Commented Feb 21, 2017 at 20:42

Paul Hankin · Accepted Answer · 2017-02-21 20:52:55Z

4

You can express your three equations as a matrix multiply:

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

Then:

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

So assuming you know the values of f1(0), f2(0), f3(0), you can compute the values for f1(m), f2(m) and f3(m) in O(log m) arithmetic operations by computing the matrix power using exponentiation by squaring.

edited Feb 21, 2017 at 20:52

answered Feb 21, 2017 at 20:44

Paul Hankin

58.8k11 gold badges99 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Grzegorz Górkiewicz Over a year ago

This throws a SquareBracketsMissingException.

Leszek · Accepted Answer · 2017-02-21 20:50:53Z

-1

If your coefficients a,b,c,d,e,f don't depend on m, but are absolute constants (or even arbitrary polynomials in variable not depending on m), then the recurrence you describe is called 'linear'. Such case is completely solved by Petkovšek's algorithm.

The algorithm basically lets one compute a so-called closed form of the recurrence. It is described in detail here: https://www.math.upenn.edu/~wilf/AeqB.html

edited Feb 21, 2017 at 20:50

answered Feb 21, 2017 at 20:44

Leszek

1,2431 gold badge12 silver badges25 bronze badges

Collectives™ on Stack Overflow

Efficient approach for recursive functions

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related