algoritma pemrograman - ifa's · ditambahkan dengan 1 •bila program dijalankan ... (input j...

S1 Teknik Informatika-Unijoyo 1

Algoritma Pemrograman

Pertemuan Ke-14(Rekursi)

:: Noor Ifada ::


Sub Pokok Bahasan

PendahuluanFaktorialMenara Hanoi


Pendahuluan• Algoritma rekursi adalah algoritma yang merupakan proses

dalam subprogram (dapat berupa fungsi atau prosedur) yang memanggil dirinya sendiri

• Tidak semua bahasa tingkat tinggi menyediakan kemampuan untuk melakukan algoritma rekursi. Salah satu bahasa tingkat tinggi yang dapat melakukan rekursi adalah Bahasa Pascal

• Proses rekursi 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 berikut merupakan proses rekursi yang tidak pernah berakhir, karena tidak mengandung kondisi untuk mengakhirkan rekursi tersebutAlgoritma 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(‘Informatika ’)Rekursi

DESKRIPSI : (* Program Utama *)Rekursi


Program REKURSI_TANPA_AKHIR;procedure Rekursi;Begin Write(‘Informatika ’); Rekursi;End;

Begin Rekursi;End.

• Bila program ini dijalankan, maka proses rekursi akan terus dijalankan tanpa berhenti sebagai berikut:

Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika Informatika . . .

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


• Contoh: Proses rekursi ini akan dilakukan sebanyak 5 kali, yaitu dengan menyeleksi kondisi dari peubah ulang sampai dengan bernilai 5 sebagai berikut:Algoritma REKURSI_DENGAN_AKHIR{ Rekursi yang tidak berujung akhir }DEKLARASI (* Program Utama *)ulang : integer

procedure Rekursi{ Menampilkan tulisan “Informatika” sebanyak 5 kali }DEKLARASI { Tidak ada }DESKRIPSI : (* Prosedur *)if ulang < 5 then write(‘Informatika ’) ulang ← ulang + 1 Rekursiendif

DESKRIPSI : (* Program Utama *)ulang ← 0Rekursi


• Bila program dijalankan:

Informatika Informatika Informatika Informatika Informatika

Program REKURSI_DENGAN_AKHIR;Var ulang : integer;

procedure Rekursi;Begin if ulang < 5 then begin write(‘Informatika ’); ulang := ulang + 1; Rekursi; end;end;

Begin ulang := 0; Rekursi;End.


• Contoh: Prosedur Deret ini digunakan untuk menampilkan suatu deret bilangan bulat N dari 0 sampai dengan 5 sebagai berikut:

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

procedure Deret(output N : word)DEKLARASI (* Prosedur *){ Tidak ada }DESKRIPSI : (* Prosedur *)write(N)if n < 5 then Deret(N+1)endif

DESKRIPSI : (* 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;

begin N := 0; Deret(N);end.

• Pada prosedur tampak terjadi proses rekursi yaitu bila nilai N masih lebih kecil dari 5, maka prosedur kembali dipanggil oleh prosedur itu sendiri dengan mengirimkan parameter nilai N sebelumnya ditambahkan dengan 1

• Bila program dijalankan didapatkan hasil:

0 1 2 3 4 5


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)!

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

5! = 5 * 4 * 3!– Secara rekursi nilai 3! adalah 3 * 2!, sehingga nilai 5!

menjadi:5! = 5 * 4 * 3 * 2 !

– Secara rekursi nilai dari 2! adalah 2 * 1, sehingga akhirnya nilai 5! adalah:

5! = 5 * 4 * 3 * 2 * 1 = 120


• Algoritma rekursif untuk menghitung N! adalah sebagai berikut: Algoritma HITUNG_FAKTORIAL;{ Menghitung faktorial suatu nilangan bulat }DEKLARASI (* Program Utama *)N : integer

function 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 then Faktorial := 1else Faktorial := N * Faktorial(N-1);end;

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

• Bila program ini dijalankan:Berapa Faktorial? 5Faktorial = 120

• Proses rekursi harus mempunyai kondisi terminasi (akhir dari proses rekursi). Kondisi terminasi pada program faktorial ini terletak pada penyeleksian kondisi bila nilai N lebih kecil atau sama dengan 1 sebagai berikut :

If N <= 1 thenHasil := 1

• Nilai dari N ini tidak akan bernilai 0, karena setelah nilai N menjadi 1, proses rekursi akan diakhiri, kecuali bila akan dihitung sebesar 0!. Nilai 0! adalah 1. Dengan demikian proses rekursi ini dapat didefinisikan :

N! = 1 untuk N <= 1N! = N * (N-1)! untuk N > 1


Menara Hanoi • Permasalahan yang merupakan proses rekursi yang

terkenal adalah menara Hanoi. Permasalahan menara Hanoi adalah memindahkan sejumlah piringan dari satu menara ke menara yang lain

• Pemindahan piringan dilakukan satu demi satu dan tidak boleh ada piringan yang lebih kecil yang berada di bawah piringan yang lebih besar. Untuk itu disediakan sebuah menara lagi untuk bantuan pemindahan. Jadi dipergunakan tiga buah menara, yaitu:1. menara sumber yang berisi piringan yang akan dipindahkan

(menara A)2. menara tujuan piringan (menara C)3. menara untuk bantuan (menara B)


Permasalahan Menara Hanoi:– Menara A sebagai sumber– Menara C sebagai tujuan

– Menara B sebagai bantuan

A CB


• Anggaplah jumlah piringan yang akan dipindahkan adalah N piringan. Permasalahan ini dapat dipecahkan dengan langkah sebagai berikut:

• Jika N = 1, maka langsung pindahkan saja piringan dari menara A ke menara C dan selesai

• Pindahkan N-1 piringan dari menara A ke menara B, menggunakan menara C sebagai menara bantuan

• Pindahkan sisa sebuah piringan di A langsung ke C

• Akhirnya pindahkan sisa sejumlah N-1 piringan di menara B ke menara C dengan menggunakan bantuan menara A

• Pemindahan N-1 piringan tersebut dilakukan satu per satu dan tidak sekaligus. Proses pemindahan merupakan proses yang berulang-ulang (rekursi)


Algoritma MENARA_HANOI{ Pemindahan piringan pada permasalahan Menara Hanoi }DEKLARASI (* Program Utama *)J, L : integerA, B, C: charprocedure MenaraHanoi(input J : integer, input A,C,B : char; output L : integer)DEKLARASI (* Prosedur *){ tidak ada }DESKRIPSI: (* Prosedur *)if J = 1 then L ← L + 1 write(‘Langkah : ‘,L,’ ‘) write(‘Pindahkan piringan 1 dari menara ‘,A,’ ke menara ‘,C)else(* Pindahkan N-1 piringan dari menara A ke B menggunakan menara C*) MenaraHanoi(J-1,A,B,C,L) L ← L + 1 write(‘Langkah : ‘,L,’ ‘) write(‘Pindahkan piringan ’,J,’ dari menara ‘,A,’ ke menara ‘,C)(* Pindahkan N-1 piringan dari menara B ke C menggunakan menara A *) MenaraHanoi(J-1,B,C,A,L)endifDESKRIPSI: (* Program Utama *)write(‘Jumlah Piringan ? ’)readln(J)L ← 0A ← ‘A’ {menara sumber}B ← ‘B’ {menara bantuan}C ← ‘C’ {menara tujuan}MenaraHanoi(J,A,C,B,L)

• Solusi Algoritma untuk permasalahan menara Hanoi:


Program MENARA_HANOI;var J, L : integer; A, B, C: char;Procedure MenaraHanoi(J:integer; A,C,B:char; Var L:integer);begin if J = 1 then begin L := L + 1; write(‘Langkah : ‘,L,’ ‚); writeln(‘Pindahkan piringan 1 dari menara ‘,A,’ ke menara ‘,C); end else begin (* Pindahkan N-1 piringan dari menara A ke B menggunakan menara C*) MenaraHanoi(J-1,A,B,C,L); L := L + 1; write(‘Langkah : ‘,L,’ ‘); writeln(‘Pindahkan piringan ’,J,’ dari menara ‘,A,’ ke menara ‘,C); (* Pindahkan N-1 piringan dari menara B ke C menggunakan menara A *) MenaraHanoi(J-1,B,C,A,L); end;end;

begin write(‘Jumlah Piringan ? ’);readln(J); L := 0; A := ‘A’; {menara sumber} B := ‘B’; {menara bantuan} C := ‘C’; {menara tujuan} MenaraHanoi(J,A,C,B,L);end.


• Bila program ini dijalankan untuk memindahkan 4 piringan sebagai berikut:Jumlah piringan ? 4Langkah: 1 Pindahkan piringan 1 dari menara A ke menara BLangkah: 2 Pindahkan piringan 2 dari menara A ke menara CLangkah: 3 Pindahkan piringan 1 dari menara B ke menara CLangkah: 4 Pindahkan piringan 3 dari menara A ke menara BLangkah: 5 Pindahkan piringan 1 dari menara C ke menara ALangkah: 6 Pindahkan piringan 2 dari menara C ke menara BLangkah: 7 Pindahkan piringan 1 dari menara A ke menara BLangkah: 8 Pindahkan piringan 4 dari menara A ke menara CLangkah: 9 Pindahkan piringan 1 dari menara B ke menara CLangkah: 10 Pindahkan piringan 2 dari menara B ke menara ALangkah: 11 Pindahkan piringan 1 dari menara C ke menara ALangkah: 12 Pindahkan piringan 3 dari menara B ke menara CLangkah: 13 Pindahkan piringan 1 dari menara A ke menara BLangkah: 14 Pindahkan piringan 2 dari menara A ke menara CLangkah: 15 Pindahkan piringan 1 dari menara B ke menara C


Summary

• Algoritma rekursi adalah algoritma yang merupakan proses dalam subprogram (dapat berupa fungsi atau prosedur) yang memanggil dirinya sendiri. Yang perlu diperhatikan dalam penulisan fungsi atau prosedur rekursi 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 permasalahan yang dapat diselesaikan dengan lebih baik dan lebih mudah dengan menggunakan algoritma rekursi adalah Permasalahan Faktorial dan Menara Hanoi


Daftar Pustaka

• Jogiyanto HM [1989]. Turbo Pascal, Andi Offset, Yogyakarta.

• Noor Ifada, ST [2005]. Diktat Matakuliah Algoritma Pemrograman, Hibah Kompetisi A1, Jurusan Teknik Informatika, Universitas Trunojoyo.

• Rinaldi Munir [2003]. Algoritma dan Pemrograman dengan Pascal dan C edisi Kedua, Penerbit Informatika, Bandung.

algoritma pemrograman - ifa's · ditambahkan dengan 1 •bila program dijalankan ... (input j...

Documents