rekrusif fibonacci

function Fibonacci (input n:integer) → integer{fungsi untuk mencari deretan sebuah bilangan fibonacci}algoritma :   
if n = 0 then      Fibonacci ← 0 
  else      if n = 1 then       
  Fibonacci ← 1      else      
   Fibonacci ← Fibonacci(n-1)+Fibonacci(n-2)      
endif  
 endif


Relasi rekurens : 
T(n) = 1 untuk n=1 
T(n) = 2T(n-1) + 1 untuk n>1 
Analisis waktu: 
T(n) = 2T(n - 1) + 1 
T(n) = 2(2T(n - 2) + 1) + 1 = 22T(n - 2) + 2 + 1 
T(n) = 22(2T(n - 3) + 1) + 2 + 1= 23T(n - 3) + 22 + 2 + 1 
… 
T(n) = 2n-1 + … + 22 + 2 + 1 
T(n) = 2n - 1 = 2n - 1 times 

Anggota kelas 2n