Optimization of recursive processing based on linear homogenized quadratic recurrence relation equation solution
Overview
As you write code, you write recursive functions quite frequently. Recursion sometimes allows for very beautiful and elegant code that solves problems, but due to the mathematical nature of the ignition equation and the nature of how the recursive processing method on a computer, it may show such poor performance that it is difficult to use unless it is optimized with sufficient consideration
There will be many ways to optimize the recursive code. The most typical method is to convert simple recursive iterations to linear iterations, or to perform the recursive code itself at the compiler level through inline and paste the results. However, both methods have limitations, and no matter how well optimized they are, time complexity of O(n) or higher will be required
In the case of optimizing recursive processing by solving linear homogeneous quadratic recurrence relocation, it provides a method of obtaining each term in O(1) through an equation derived by calculating the solution of quadratic recurrence relocation that satisfies a specific condition. In other words, when it comes to ordinary quadratic recurrence relation, the values of two previous terms are required to obtain the value of the nth term, so all terms up to n terms must be obtained sequentially, but in the case of a newly obtained equation by solving the recurrence relocation expression, the value of the nth term can be obtained immediately, so the larger the nth term, the smaller the amount of computation is
The word ‘Linear homogeneous quadratic recurrence relocation’ in the title can be difficult to come by. Examples of the corresponding equation may include the following
Exp 1 is the linear homogeneous quadratic recurrence relocation expression of the very famous Fibonacci sequence, and Exp 2 satisfies the linear homogeneous quadratic relocation
Interpretation of the meaning of each part of the ‘Linear homogeneous quadratic recurrence relocation’
The term ‘recurrence relation’ refers to a sequence in which the nth value is determined as a preceding term. To define this more strictly, it is as follows
Simply put, ‘degree’ refers to the number of previous terms required to determine the value of the nth term. For example
is a quadratic recurrence relocation because it requires two terms (n-1, n-2) to obtain the value of the nth term. As another example
is a linear recurrence relocation because it requires one term (n-1) to obtain the value of the nth term
To find out ‘linearity’ not strictly but conveniently, you can check if it is not in the following form
The above equation is non-linear quadratic recurrence relocation. The reason for nonlinearity is that, as you can see from the equation, the two previous terms for obtaining the nth term are connected through multiplication operations. To be linear, it must be a detachment operation instead of a multiplication operation. That is, the following equation is a linear recurrence relation equation
In the general recurrence relational equation, when all terms other than the constant term on the right side are turned over to the left side, the constant term on the right side is zero
Assuming that there is a recurrence relocation equation as above, if all terms other than the constant terms on the right side are passed to the left side, it will be as follows
At this time, since the right side of the developed equation is not 0, but 2, the existing equation is not a homogeneous equation. On the other hand, the following recurrence relocation equation is a homogeneous equation
How to solve linear homogeneous quadratic recurrence relation equation
Strictly defines the process of solving linear homogeneous quadratic recurrence relocation as follows
It may be difficult to understand the above theorem, so I’ll show you the process of actually solving it with an equation
First, the above equation corresponds to the linear homogeneous quadratic recurrence relation equation. Now, if we convert it into a quadratic equation for t, we can transform it as follows. This equation is called the characteristic equation of recurrence relation
Now we need to find the solution to the equation
If the equation is constructed to obtain the general solution of recurrence relocation based on the obtained solution of the characteristic equation, it will be as follows
The general solution can be obtained in relation to the initial conditions of the recurrence relocation equation
Based on this, the final development of the equation will be as follows
Now, if you want to find the nth term, you can calculate it by just filling in the appropriate value in the above equation
As another example, I will solve the recurrence relocation equation of the Fibonacci sequence, Exp1
First, the above equation corresponds to the linear homogeneous quadratic recurrence relation equation. Now, if we convert it into a quadratic equation for t, we can transform it as follows
Now we need to find the solution to the equation
If the equation is constructed to obtain the general solution of recurrence relocation based on the obtained solution of the characteristic equation, it will be as follows
The general solution can be obtained in relation to the initial conditions of the recurrence relocation equation
Based on this, the final plot of the equation will be as follows
Now, if you want to find the nth term, you can calculate it by just filling in the appropriate value in the above equation
Code writing and performance analysis
Based on the Fibonacci sequence, which is Exp 1, I will write the actual code and analyze the performance of the code writing method using the general recursive function method and the code writing method using the recurrence relation equation
Testing took place in Github Codespace’s 4-core • 16GB RAM • 32GB instance environment
First, let’s look at the function definition
import math
def GetFibonacciWithGeneralWay(n : int):
if n == 1 or n == 2:
return 1;
return GetFibonacciWithGeneralWay(n - 1) + GetFibonacciWithGeneralWay(n - 2);
def GetFibonacciWithSolutionWay(n : int):
left : float = (1.0 / math.sqrt(5)) * math.pow(((1.0 + math.sqrt(5)) / 2.0), n)
right : float = (1.0 / math.sqrt(5)) * math.pow(((1.0 - math.sqrt(5)) / 2.0), n)
return left - right;
for n in range(1, 10):
print(f'{n} - {GetFibonacciWithGeneralWay(n)}')
print('------------------')
for n in range(1, 10):
print(f'{n} - {GetFibonacciWithSolutionWay(n)}')1 - 1
2 - 1
3 - 2
4 - 3
5 - 5
6 - 8
7 - 13
8 - 21
9 - 34
------------------
1 - 1.0
2 - 0.9999999999999999
3 - 2.0
4 - 3.0000000000000004
5 - 5.000000000000001
6 - 8.000000000000002
7 - 13.000000000000004
8 - 21.000000000000004
9 - 34.000000000000014If you look at the results themselves, the results come out well in both methods
Now let’s represent the time it takes to average the two methods by repeating them sufficiently from small to large. The test code is as follows, and n is calculated from 1 to 30 and repeated 100 times for each n to obtain the average
import matplotlib.pyplot as plt
import math
import time
def GetFibonacciWithGeneralWay(n : int):
if n == 1 or n == 2:
return 1;
return GetFibonacciWithGeneralWay(n - 1) + GetFibonacciWithGeneralWay(n - 2);
def GetFibonacciWithSolutionWay(n : int):
left : float = (1.0 / math.sqrt(5)) * math.pow(((1.0 + math.sqrt(5)) / 2.0), n)
right : float = (1.0 / math.sqrt(5)) * math.pow(((1.0 - math.sqrt(5)) / 2.0), n)
return left - right;
nMax : int = 30
tryCountMax : int = 100
generalWayConsumeTimes : list = [0] * nMax
for n in range(1, nMax + 1):
for tryCount in range(tryCountMax):
generalWayStartTime = time.time()
GetFibonacciWithGeneralWay(n)
generalWayEndTime = time.time()
generalWayConsumeTimes[n - 1] += generalWayEndTime - generalWayStartTime
generalWayConsumeTimes[n - 1] /= float(tryCountMax)
solutionWayConsumeTimes : list = [0] * nMax
for n in range(1, nMax + 1):
for tryCount in range(tryCountMax):
solutionWayStartTime = time.time()
GetFibonacciWithSolutionWay(n)
solutionWayEndTime = time.time()
solutionWayConsumeTimes[n - 1] += solutionWayEndTime - solutionWayStartTime
solutionWayConsumeTimes[n - 1] /= float(tryCountMax)
plt.plot(generalWayConsumeTimes, color='r', label='General Way')
plt.plot(solutionWayConsumeTimes, color='g', label='Solution Way')
plt.legend()
plt.show()The results clearly show the performance difference between the two methods
conclusion
Recursion is clearly a very useful tool for writing code for solving more elegant forms of problems. However, performance can also be a significant obstacle to making recursive choices. I’m sure that if the method covered in this post is properly utilized, it will help optimize performance while adopting a method using recursive methods at the same time
