Pascal : Rekurens

Fungsi dan prosedur bisa memiliki sifat yang rekursif, artinya prosedur dan fungsi tersebut

memanggil dirinya sendiri dalam bagian implementasinya. Struktur data juga bisa memiliki sifat yang rekursif, yang artinya struktur data tersebut bisa menunjuk ke struktur data yang lain yang sama.

Struktur data rekursif tidak akan dibahas dalam buku ini, karena terlalu komplels. Fungsi rekursif hanya akan dibahas perkenalannya saja. Konsep rekursif bisa sangat rumit, dan akan dibahas di buku lain yang mengajarkan problem solving dan algoritma.

Fungsi yang rekursif

Fungsi faktorial adalah contoh fungsi yang rekursif, fungsi rekursif ini mengandung dirinya sendiri dalam definisinya: faktorial n = faktorial (n – 1) * n

Dan faktorial 0 = 1 Perhatikan bahwa ada dua definisi fungsi ini, yaitu untuk n = 0 (yang hasilnya adalah 1) dan untuk n lebih dari nol (hasilnya adalah faktorial (n – 1) dikalikan dengan n. Bagian yang tidak memanggil dirinya sendiri (dalam kasus n = 0) disebut dengan basis, sedangkan bagian yang memanggil dirinya sendiri disebut sebagai bagian rekurens.

Function faktorial(n: integer):int;

begin

if (n=0) then (*basis*)

begin

faktorial:= 1;

end else (* rekurens *)

begin

faktorial:= n * faktorial ( n – 1);

end;

end;

Tanpa bagian basis, maka rekursi tidak akan berhenti, jadi bagian basis ini harus ada, dan harus dijamin bahwa pada suatu saat kondisi basis akan dipenuhi.

Rekursif dan interatif

Suatu bentuk rekursif bisa diubah menjadi bentuk iteratif (bentuk perulangan/loop), misalnya fungsi faktorial di atas dapat diubah menjadi:

Function faktorial(n: integer):int;

var i, hasil: integer;

begin

i:=0;

hasil:=1;

while (i<n) do

begin

i:=i+1;

hasil:=hasil * i;

end;

faktorial:= i;

end;

Secara umum semua bentuk rekursif bisa diubah menjadi bentuk interatif.