我对递归方程的概念还不太熟悉，需要以下算法的帮助
G(n)
Require: A positive integer n.
if n <= 1 then
return n
else
return 5*g(n - 1) - 6* g(n- 2)
end if
我得出了下面的递推方程：
t（n）=n，如果nT（n）=5*T（n-1）-6.T（n-2），如果n>1
如果这是正确的，我还必须为这个算法执行的乘法数设置一个递归。请帮忙。
最佳答案
你在这里建立的递归关系是正确的。基本上是你用一些更小的子问题的形式写一个问题。
现在是乘法的数目。记住两件事。
在递归关系中，要达到基本情况，需要向下执行的步骤数（在这种情况下，n每种情况下的操作次数。
现在轮到你了。
T（n）=n，如果nT（n）=5*T（n-1）-6.T（n-2），如果n>1
你有一个递归，在每一步把一个问题变成两个子问题，在每一步，n的值减少1
t（n）=5*t（n-1）-6*t（n-2）
t（n-1）=5*t（n-2）-6*t（n-3）
所以每次分成两个子问题就有n个步骤
2*2*2（O（n）时间）
因此，在你的问题中大约有2个n步，因此O（2 ^ n）
每一步有两个乘法和一个减法。
乘法次数的循环如下
t（n）=t（n-1）+t（n-2）+2
所以乘法的数目大约是（2 ^ n）* 2。