BAB 4 REKURSIF (REKURSI)

1. Pengertian RekursifRekursif berarti suatu proses yang memanggil dirinya sendiri.

Dalam rekursif sebenarnya terkandung pengertian prosedur atau fungsi. Perbedaannya adalah bahwa rekursif bisa memanggil ke dirinya sendiri, tetapi prosedur atau fungsi harus dipanggil lewat pemanggil prosedur atau fungsi. Rekursif merupakan teknik pemrograman yang penting, dan beberapa bahasa pemrograman modern mendukung keberadaan proses rekursif ini.

Pemanggilan prosedur atau fungsi ke dirinya sendiri bisa berarti proses yang berulang yang tidak bisa diketahui kapan akan berakhir. Dalam pemakaian sehari-hari, rekursif merupakan teknik pemrograman yang berdaya guna untuk digunakan pada pekerjaan pemrograman dengan mengeksperisikannya ke dalam suku-suku dari program lain dengan menambahkan langkahl-angkah sejenis.

2. Proses RekursifProses rekursif untuk beberapa kasus merupakan algoritma yang

baik dan dapat membuat pemecahan masalah lebih mudah. Akan tetapi proses ini banyak menggunakan memori, dikarenakan setiap kali suatu subprogram dipanggil, maka diperlukan sejumlah tambahan memori

Dalam menulis suatu fungsi atau prosedur rekursi, yang perlu diperhatikan adalah fungsi atau prosedur tersebut harus mengandung suatu kondisi akhir dari proses rekursi. Kondisi ini diperlukan untuk mencegah terjadinya proses rekursi yang tidak berujung (indefinite), yaitu proses rekursi akan terus dilakukan tanpa berhenti.

Contoh 1:Proses rekursif yang tidak pernah berakhir (karena tidak mengandung kondisi untuk mengakhirkan rekursi tersebut)

Algoritma REKURSI_TANPA_AKHIR{Rekursi yang tidak berujung akhir}DEKLARASI (* Program Utama *)

{Tidak ada}procedure Rekursi{Menampilkan tulisan “Informatika” secara terus menerus, karena tidak mengandung kondisi pengakhiran rekursi}

DEKLARASI (* Prosedur *){Tidak ada}

DESKRIPSI : (* Prosedur *)write(‘UNINDRA’)Rekursi

DESKRIPSI : (* Program Utama *)

24

Rekursi

Program REKURSI_DENGAN_AKHIR;Var

ulang : integer;procedure Rekursi;

Beginif ulang < 5 thenbegin

write(‘UNINDRA’);ulang := ulang + 1;Rekursi;

end;end;Begin

ulang := 0;Rekursi;

End.

Hasil Output : Bila program dijalankan, maka proses rekursi akan terus dijalankan

tanpa berhenti sebagai berikut:UNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA UNINDRA UNINDRA UNINDRAUNINDRA . . .

Kondisi pengakhiran rekursi dapat dilakukan dengan menggunakan struktur penyeleksian kondisi. Rekursi akan dihentikan bila kondisi telah memenuhi syarat.

Contoh 2:Proses rekursi sebanyak 5 kali, yaitu dengan menyeleksi kondisi dari peubah ulang sampai dengan bernilai 5

Algoritma REKURSI_DENGAN_AKHIR{Rekursi yang tidak berujung akhir}DEKLARASI (* Program Utama *)

ulang : integerprocedure Rekursi{Menampilkan tulisan “UNINDRA” sebanyak 5 kali}DEKLARASI { Tidak ada }DESKRIPSI : (* Prosedur *)if ulang < 5 then

write(‘UNINDRA’)ulang ← ulang + 1Rekursi

endifDESKRIPSI : (* Program Utama *)

25

ulang ← 0Rekursi

Program REKURSI_DENGAN_AKHIR;Var

ulang : integer;procedure Rekursi;Begin

if ulang < 5 thenbegin

write(‘Informatika ’);ulang := ulang + 1;Rekursi;

end;end;

Beginulang := 0;Rekursi;

End.

Contoh 3:Prosedur Deret untuk menampilkan suatu deret bilangan bulat N dari 0 sampai dengan 5

Algoritma DERET{Menampilkan deret bilangan bulat N dari 0 sampai 10}DEKLARASI (* Program Utama *)

N : integerprocedure Deret(output N : word)DEKLARASI (* Prosedur *){Tidak ada}DESKRIPSI : (* Prosedur *)

write(N)if n < 5 then

Deret(N+1)endifDESKRIPSI : (* Program Utama *)N ¬ 0Deret(N)

Program DERET_BILANGAN;var

N : integer;procedure Deret(N : integer);begin

write(N:3);if N < 5 then

Deret(N+1);end;

end;begin

N := 0;Deret(N);

end.

Hasil Output:0 1 2 3 4 5

26

Contoh 4: (Faktorial) Faktorial adalah 1x2x3x4x...N (dengan asumsi N lebih besar

dari 3) dan dapat dirumuskan dengan:N! = N * (N-1) * (N-2) * ... * 1

Perumusan ini dapat didefinisikan secara rekursi sebagai berikut:N! = N * (N-1)!

o Misal, rekursi nilai 4! Dapat dihitung kembali sebesar 4 * 3!, sehingga 5! menjadi:5! = 5 * 4 * 3!

o Secara rekursi nilai 3! adalah 3 * 2!, sehingga nilai 5! menjadi:5! = 5 * 4 * 3 * 2 !

o Secara rekursi nilai dari 2! adalah 2 * 1, sehingga akhirnya nilai 5! adalah: 5! = 5 * 4 * 3 * 2 * 1 = 120

Proses rekursi untuk menghitung N!o N! = 1 untuk N <= 1o N! = N * (N-1)! untuk N > 1

Algoritma HITUNG_FAKTORIAL;{Menghitung faktorial suatu nilangan bulat}DEKLARASI (* Program Utama *)

N : integerfunction FAKTORIAL(input N:integer)® integer{mengembalikan nilai n!}DEKLARASI (* Fungsi *){tidak ada}DESKRIPSI: (* Fungsi *)if N £ 1 then

return 1else

return n*FAKTORIAL(n-1)endif

DESKRIPSI: (* Program Utama *)write(‘Berapa faktorial ?’)read(N)write(‘Faktorial = ‘,FAKTORIAL(N))

PROGRAM HITUNG_FAKTORIAL;var

N : integer;function Faktorial(N: integer):integer;begin

if N <= 1 thenFaktorial := 1

elseFaktorial := N * Faktorial(N-1);

end;begin

write(‘Berapa faktorial ?’);readln(N);write(‘Faktorial= ‘,Faktorial(N));

27

end.

28