如何計算以下模塊的θ值作爲n的函數？

Question

function rec (n:integer); 
    begin 
     if n<=1 then 
      return (1) 
     else 
      return(rec(n-1)+rec(n-1)+rec(n-1)) 
    end 

我的復發如下，我很困惑表達這種復發作爲n的函數。 我認爲方程式是一些什麼樣的; T（n）= 3T（n-1）+2。

Answer 1

考慮此功能的一個稍微更一般的版本：

重新替代這個入本身多次以發現一個圖案新興：

重複的處理之後爲m次。

我們什麼時候停止？此復發停止條件是n <= 1，所以：

因此對於T表達式變爲：

替代中的數字，a = 3, b = 1, c = 2：

請注意，我們忽略了最大值爲m的任何舍入，因爲整數舍入誤差的最大值爲0.5，因此只給出常數因子差異。