» » » Materi Kuliah Teknik Informatika Dasar Pemrograman Fungsi Rekursif
8/30/2016T8/30/2016
, Edit

Materi Kuliah Teknik Informatika Dasar Pemrograman Fungsi Rekursif

// kode iklan */
// kode iklan
Materi Kuliah Teknik Informatika Dasar Pemrograman Fungsi Rekursif

11.1 Pengertian Rekursi

Rekursi adalah suatu proses dari fungsi yang memanggil dirinya sendiri. Fungsi yang seperti ini disebut fungsi rekursif (recursive function). Dalam sebuah fungsi rekursif pemanggilan dapat terjadi berulang kali. Karena ada proses yang berulang-ulang maka harus ada suatu kondisi yang mengakhiri prosesnya. Jika tidak, maka proses tidak akan pernah berhenti sampai memori yang digunakan tidak dapat menampung lagi.
Pemecahan masalah dengan pendekatan rekursif dapat dilakukan jika masalah tersebut dapat didefinisikan secara rekursif, yaitu masalah dapat diuraikan menjadi masalah sejenis yang lebih sederhana.


Listing Program 11.1 Contoh Fungsi Rekursi

procedure rekursi(n: integer);
begin
    if n > 0 then
    begin
      writeln('rekursi ',n);
rekursi(n-1);
    end;
end;

var p: integer;

begin
  p:=3;
  rekursi(p);
end.

Hasil Running:

Rekursi 3
Rekursi 2
Rekursi 1

Dalam membuat fungsi rekursi harus ditentukan kondisi perhentian. Pada contoh listing program 11.1 di atas kondisi perhentiannya adalah jika nilai n sudah lebih kecil atau sama dengan 0. Setiap kali fungsi memanggil dirinya sendiri, nilai dari n dikurangi dengan nilai 1, sehingga nilai n akhirnya akan menjadi nol dan proses rekursi akan diakhiri, sehingga fungsi ini akan memanggil dirinya sendiri sebanyak n kali.
Contoh untuk menggambarkan fungsi rekursif yang sering digunakan adalah fungsi untuk mendapatkan nilai faktorial dari suatu bilangan bulat.


Listing Program 11.2 Program Faktorial

Function faktorial(x: integer): longint;
Begin
   If x<= 1 then
Faktorial := 1
   Else
Faktorial := x * faktorial(x-1);
 End;

Var n:integer;

Begin
  Writeln(‘Menghitung N Faktorial (N!)’);    
  Write(‘Masukkan N : ’);  readln(n);
  Writeln(n,’ ! = ‘, faktorial(n));
End.

Hasil Running:

Menghitung N Faktorial (N!)
Masukkan N : 5
5 ! = 120


Program 11.2 di atas dapat dijelaskan sebagai berikut:
1. Fungsi utama memanggil fungsi faktorial() dengan mengirimkan nilai n = 5 untuk parameter formal x, yang maksudnya akan dilakukan perhitungan sebanyak 5 faktorial.
2. Jika nilai dari x  pertama kali yang diberikan oleh fungsi utama bernilai kurang dari atau sama dengan satu, maka hasil faktorial yang akan diberikan adalah bernilai 1.
3. Jika nilai x pertama kali yang diberikan oleh fungsi utama lebih besar dari 1, maka proses rekursi akan dilakukan misalnya nilai x = 5 , maka proses rekursi yang pertama adalah:
Faktorial=  5 * faktorial(4);

Proses ini akan memanggil kembali fungsi dirinya sendiri dengan mengirimkan nilai 4 sebagai nilai x yang baru. Karena nilai x masih lebih besar dari 1 maka proses rekursi kedua akan dilakukan dengan hasilnya adalah 4 * faktorial(3). Untuk x adalah 3, hasil yang diperoleh oleh rekursi adalah 3 * faktorial(2) dan seterusnya sampai nilai x adalah 1. Untuk nilai x sama dengan 1 ini, perintah faktorial:=1 akan mengembalikan proses ke bagian yang memanggilnya.
Hasil akhir dari nilai yang akan dikembalikan oleh fungsi faktorial dari penjelasan di atas untuk 5 faktorial dapat dituliskan sebagai berikut:


11.2 Perbandingan Rekursif dengan Iteratif

Kekurangan fungsi rekursif:
1. Memerlukan memory yang lebih banyak untuk menyimpan activation record dan variabel lokal.  Activation record  diperlukan waktu proses kembali kepada pemanggil.
2. Memerlukan waktu yang lebih banyak untuk menangani activation record.

Secara umum gunakan penyelesaian rekursif hanya jika:
1. Penyelesaian sulit dilaksanakan secara iteratif.
2. Efisiensi dengan cara rekursif sudah memadai.
3. Efisiensi bukan masalah dibandingkan dengan kejelasan logika program.

Jika sebuah masalah dapat diselesaikan dengan cara iteratif maka gunakan iteratif. Jika penyelesaian dengan menggunakan iteratif memerlukan algoritma yang relatif rumit maka dapat dicoba dengan pendekatan rekursif karena rekursif memerlukan sumber daya yang lebih banyak.
Contoh program untuk membandingkan penggunaan itertif dan rekursif dapat dilihat dalam program menampilkan deret fibonacci pada listing program 11.3 dan listing program 11.4 bawah ini.

Baca juga:
  1. Materi Kuliah Semester 1 Teknik Informatika Dasar Pemrograman Percabangan
  2. Materi Kuliah Semester 1 Subprogram 2 ( Function )
  3. Materi Kuliah Semester 1 Teknik Informatika Dasar Pemrograman Fungsi Standar & Input Output
  4. Materi Kuliah Semester 1 Teknik Informatika Dasar Pemrograman Perulangan
  5. Materi Kuliah Semester 1 Teknik Informatika Dasar Pemrograman Runtunan
  6. Materi Kuliah Semester 1 Teknik Informatika Dasar Pemrograman Sub Program (Prosedur)

Listing Program 11.3 Program Fibonacci dengan Rekursif

Function Fibo(N:word): word;
Begin
  If n< 2 then
Fibo := N;
  Else
Fibo := Fibo(N-2) + Fibo(N-1);
End;

Var
  N,i : Word;

Begin
  Writeln(‘Menampilkan deret Fibonacci’);
  Write(‘Batas suku bilangan ke : ‘); readln(N);
  Writeln(‘Deret ke ‘,N,‘ = ‘, Fibo(N));
  Write(‘Deret fibonacci : ‘);
  For i:= 1 to N do
write(fibo(i),’ ‘);
end.

Hasil Running:

Menampilkan deret Fibonacci
Batas suku bilangan ke : 5
Deret ke 5 = 5
Deret Fibinacci : 1 1 2 3 5

Penjelasan program:

Deret fibonacci mempunyai nilai suku-suku bilangan berikut: 
0, 1, 1, 2, 3, 5, 8, 13, 21, ............

Ciri khusus deret ini adalah tiap-tiap suku adalah hasil penjumlahan dari nilai dua suku sebelumnya. Misalnya adalah nilai suku ke dua adalah penjumlahan nilai suku ke 0 (bernilai 0) dengan suku ke 1 (bernilai 1) jadi nilai suku ke 2 adalah sama dengan 1 (0 + 1). Nilai suku ke tiga adalah nilai suku ke dua ditambah nilai suku ke satu. Misalnya untuk mencari bilangan fibonacci ke- 5, maka urutan pengerjaannya adalah sebagai berikut:




Dari diagram terlihat bahwa untuk mendapatkan deret ke 5 dari deret fibonacci maka fungsi fibo(4) dihitung satu kali, fungsi fibo(3) dihitung dua kali, fungsi fibo(2) dihitung tiga kali dan fungsi fibo(1) dihitung dua kali. Hal ini menyebabkan proses lebih lama dan juga sumber daya yang dibutuhkan untuk menangani proses ini lebih banyak.
 


Listing Program 11.4 Program Fibonacci dengan Iteratif


uses wincrt;

Function fibo(n : word): word;
Var
 fb1, fb2, fn, i : word;
begin
  if n< 2 then fibo:=n
  else
  begin
    fb1:= 0;
    fb2:= 1;
    for i:= 2 to n do begin
       fn: = fb1;
fb1:= fb2;
fb2:= fn + fb2;
    end;
    fibo:= fb2;
  end;
end;

var
   x, i: word;
begin
  writeln('Menampilkan deret Fibonacci'); writeln;
  write('Batas suku bilangan ke : '); readln(x);
  write('Deret ke ', x, ' = ',fibo(x)); writeln;
  write('Deret fibonacci : ');
  for i:= 1 to x do
write(fibo(i),' '); 
end.


Hasil Running:

Menampilkan deret Fibonacci
Batas suku bilangan ke : 5
Deret ke 5 = 5
Deret fibonacci : 1 1 2 3 5


Penjelasan Program:
Dari listing program 11.4, terlihat bahwa setiap kali akan menghitung suku ke-n, maka nilai-nilai suku sebelumnya akan digunakan kembali, yaitu nilai dari n-1(variabel fb1) dan nilai dari n-2(variabel fb2). Pertama dihitung nilai dari deret ke-n, kemudian nilai dari deret n-1 diberikan kepada deret n-2, dan nilai dari deret n diberikan kepada deret n-1.

Dengan cara iterasi ini, untuk menghitung nilai fibonacci(5) dapat dilakukan dengan cara:

Fb1(nilai variabel n-1) = 0
Fb2(nilai variabel n-2)=1

Untuk i = 2 (suku ke-2):
  Fn = 0
  Fb1 = 1
  Fb2 = 0+1= 1
Untuk i = 3 (suku ke-3):
  Fn = 1
  Fb1 = 1
  Fb2 = 1+1= 2
Untuk i = 4 (suku ke-4):
  Fn = 1
  Fb1 = 2
  Fb2 = 1+2= 3
Untuk i = 5 (suku ke-5):
  Fn = 2
  Fb1 = 3
  Fb2 = 2+3= 5

Hasil akhirnya adalah Fibo(5) adalah 5


Terima kasih telah membaca Materi Kuliah Teknik Informatika Dasar Pemrograman Fungsi Rekursif

// kode iklan

jangan lupa iklannya diklik ya, to "Materi Kuliah Teknik Informatika Dasar Pemrograman Fungsi Rekursif"

Post a Comment

Subscribe to: Post Comments (Atom)