Kompleksitas waktu untuk algoritma rekursif

Contoh 1. Algoritma rekursif menghitung Faktorial

program faktorial;

kamus

n:integer;

function faktorial(n:integer):integer

 if n = 1 then

  faktorial <-- 1

 else

  faktorial <-- n * faktorial(n-1)

endfunction

algoritma

input (n)

output(faktorial(n))   

Operasi dasar :

Operasi Dasar	Tmax	Tmin
<--	n	1
*	n-1	0
-	n-1	0
=	n	1

Opersi dasar (*)

Tn = n-1

Contoh 2. Algoritma rekursif menghitung pangkat

Program hitung_pangkat;

kamus

bil,p:integer;

function pangkat(bil,p:integer):longint;

 if p=0 then

   pangkat <-- 1

 else

   pangkat <-- bil*pangkat(bil,p-1)

endfunction

Algoritma

   input(bil) {input bilangan}

   input(p) {input nilai pangkat}

  Output('pangkat(bil,p))

end.  

Operasi Dasar	Tmax	Tmin
<--	n	1
*	n-1	0
-	n-1	0
=	n	1

Opersi dasar (*)

Tn = n-1

Contoh 3. Algoritma rekursif menghitung Deret

program Hitung_Deret;

kamus

 n:integer

function deret(n:integer):integer

 if n=1 then

   deret <-- 1

 else

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

endfunction

Algoritma

   Input (n)

   Output (deret(n));

  

end.

Operasi Dasar	Tmax	Tmin
<--	n	1
+	n-1	0
-	n-1	0
=	n	1

Opersi dasar (+)

Tn = n-1