我是很新，遞推方程的概念，需要下面的算法幫助復發方程算法
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，如果n < = 1，
T（N）= 5 * T（N-1） - 6.T（N-2），如果n> 1
這是正確的，我也必須設置這個算法執行的乘法次數的遞歸。請幫忙。
您在此創建的重現關係是正確的。它基本上是以一些較小的子問題的形式寫一個問題。
現在是乘法的次數。牢記兩件事。
現在爲您的再次發生。
T（N）= N，如果n < = 1
T（N）= 5 * T（N-1） - 6.T（N-2），如果n> 1
你必須在每個步驟，並在每個改變的問題，以兩個子問題被1
T（N）= 5 * T（N-1）步驟n的值減小一個遞歸 - 6 * T（n-2） T（n-1）= 5 * T（n-2）-6 * T（n-3）
所以n步每次分成2個子問題，所以你將有 2 * 2 * ... 2（O（n）time） 所以在你的問題中有大約2^n個步驟因此O（2^n） 每步有2個乘法和一個減法。
一種用於乘法的數目復發會是這樣
T（N）= T（N-1）+ T（N-2）+ 2
所以數量乘法將近似（2^n）* 2。