Algoritma dan Pemrogaman : Fungsi Rekursif

Pada artikel sebelumnya kita telah membahas konsep rekursif secara umum. Kita tahu bahwa rekursif dapat diterapkan pada sub program yaitu pada fungsi dan prosedur. Kali ini kita akan membahas rekursif pada fungsi.

Konsep Faktorial

Dalam perhitungannya, faktorial juga menggunakan konsep rekursif loh. Perhatikan konsep faktorial berikut.

Contoh:

Program Faktorial

Program faktorial_bilangan; 
Uses crt; 

Function Faktorial(x:integer):integer; 
Var i, result:integer; 
Begin
  Result:=1; 
  For i:=x downto 1 do 
    result:=result * i;

  Faktorial:=result; 
End; 
Var i: integer; 
Begin
  Clrscr; 
  i := Faktorial(5); 
  Writeln(i); 
  Readln; 
End.

Jalannya program dimulai dari baris pertama di program utama. Berikut adalah proses jalannya program:

1. Clrscr akan membersihkan layar dari kotoran
2. i:=Faktorial(5)
   Baris ini akan meng-assign nilai dari Faktorial(5) ke variabel i. Berapakah nilai Faktorial(5)? Di sini fungsi Faktorial akan dipanggil dari program utama dengan argumen 5 yang akan ditransfer ke parameter x dalam fungsi Faktorial.
   Maka for i:=x downto 1 pada fungsi tersebut akan menjadi for i:=5 downto 1. Perulangan result := result * i akan diulang 5 kali sehingga hasilnya menjadi 54321 = 120.
   Kembali ke program utama dengan mengembalikan nilai 120, i akan berisi 120.
3. Writeln(i) akan menuliskan 120 di layar, kemudian kursor turun 1 baris.
4. Readln akan membuat kursor berkedip sebelum program diakhiri.
   Berikut ini adalah versi rekursi dari fungsi tersebut:

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

Berikut adalah jalannya fungsi ketika dipanggil Faktorial(5):

1. Faktorial(5) menjadi 5 * Faktorial(4)
2. Faktorial(4) menjadi 4 * Faktorial(3)
3. Faktorial(3) menjadi 3 * Faktorial(2)
4. Faktorial(2) menjadi 2 * Faktorial(1)
5. Faktorial(1) hasilnya adalah 1
6. Faktorial(2) hasilnya menjadi 2 * 1 = 2
7. Faktorial(3) hasilnya menjadi 3 * 2 = 6
8. Faktorial(4) hasilnya menjadi 4 * 6 = 24
9. Faktorial(5) hasilnya menjadi 5 * 24 = 120

Maka Faktorial(5) akan bernilai 120. Fungsi Faktorial dipanggil sebanyak 5 kali.

Program Penjumlahan

Contoh lainnya adalah sebuah fungsi dengan parameter x untuk mengembalikan nilai jumlah dari 1 sampai x. Berikut adalah versi iterasinya:

Function Sum(x:integer):integer; 
Var i, result: integer; 
Begin 
  Result:=0; 
  For i:=1 to x do 
    result:=result+i; 
    Sum:=result; 
End;

Ketika misalnya dipanggil sum(5) maka jalannya fungsi adalah sebagai berikut:

1. x akan berisi 5;
2. Result bernilai awal 0;
3. For i:=1 to 5 do result:=result+1 akan menjumlahkan 1+2+3+4+5 = 15.
4. Nilai 15 akan dikembalikan ke pemanggil fungsi tersebut.

Dan berikut ini adalah versi rekursinya

Function Sum(x: integer):integer; 
Begin 
  If x = 1 then 
    Sum := 1 
  Else 
    Sum := x + Sum(x-1); 
End;

Ketika misalnya dipanggil sum(5) maka jalannya fungsi adalah sebagai berikut:

1. Sum(5) menjadi 5 + sum(4)
2. Sum(4) menjadi 4 + sum(3)
3. Sum(3) menjadi 3 + sum(2)
4. Sum(2) menjadi 2 + sum(1)
5. Sum(1) hasilnya adalah 1
6. Sum(2) hasilnya menjadi 2 + 1 = 3
7. Sum(3) hasilnya menjadi 3 + 3 = 6
8. Sum(4) hasilnya menjadi 4 + 6 = 10
9. Sum(5) hasilnya menjadi 5 + 10 = 15

Fungsi Sum(5) akan menghasilkan 15.

Materi Lengkap

Silakan baca juga beberapa artikel menarik kami tentang Rekursif, daftar lengkapnya adalah sebagai berikut.

Tonton juga video pilihan dari kami berikut ini