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

Algoritma rekrusif

1.Function faktorial (input n : integer) → integer

{menghasilkan nilai n!, n tidak negatif}

Algoritma 

     If n=0 then

           Return 1 

     Else

           Return ( n*faktorial (n-1) )

     Endif

 Kompleksitas waktu

T(n) = 1+T(n-1)

T(n) = 1+1+T(n-2)=2+T(n-2)

T(n) = 2+1+T(n-3)=3+T(n-3)

         = n+T(0)

         = n+0

Jadi T(n) =n

T(n) Ꞓ 0(n)

2.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