Analisis Algoritma Rekursif

Rekursif adalah fungsi yang memanggil dirinya sendiri.
Contoh Analisis Matematis Algoritma Rekursif :

Menghitung Faktorial

Function  F(input awal,n : integer) à real

KAMUS:

fak : real

ALGORITMA:

If n = 0 then

            fak <-- 1

else

            fak <-- n * F(n-1)

endif

return fak

endFunction

T(n) ---- 0 , n = 0

T(n) ---- T (n-1) +1 , n > 0

 

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

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

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

 = …

 = n + T(0)

 = n + 0

Jadi T(n) = n ϵ Ο(n)

======================================

 

Mencari Nilai S

Algortihm S(n)

{input : A positive integer n}

{Output : the sum of the first n cubes}

if n=1 then

return 1

else

return S(n-1) + n * n* n

endif

T(n) ---- 0 , n = 0

T(n) ---- T (n-1) +2 , n > 0

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

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

 = …

 = n + T(0)

 = n + 0

Jadi T(n) = n ϵ Ο(n)

======================================

Menghitung Deret Aritmatika

Function F(input n : integer) à real

KAMUS

deret : real;

ALGORITMA

if  awal = 0  and n = awal+1 then

deret <-- 1;

else

deret <-- n + F(n-1);

endif

return deret

endFunction

Paling Dalam : +

+ : n

F(n) = n + F(n-1) untuk n > 1

F(n) = 1 untuk n = 1 dan n=0

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)

T(n) = …..

T(n) = n + 0 

T(n) = n

T(n) = n ϵ O(n)