Fungsi rekursif

This entry is part 2 of 2 in the series Pengantar Pemrograman Python 2

Secara praktis, fungsi rekursif dapat dimaknai sebagai fungsi yang memanggil dirinya sendiri. Fungsi rekursif dapat kita gunakan saat solusi sebuah persoalan bergantung pada solusi persoalan yang sama dari ruang persoalan yang lebih kecil. Dengan kata lain, fungsi rekursif sendiri adalah teknik pemecahan persoalan tertentu, dengan memecah persoalan tersebut ke dalam persoalan dengan ukuran yang semakin mengecil sampai ia cukup kecil untuk dipecahkan langsung.

Karakteristik

Teknik rekursif sendiri adalah bentuk implementasi dari algoritma dengan tipe divide and conquer. Sebuah algoritma dengan tipe ini memiliki 3 tahapan umum yakni:

  1. Divide, membagi/memecah persoalan secara terus menerus ke dalam bentuk yang lebih kecil.
  2. Conquer, memecahkan persoalan yang sudah diperkecil hingga mencapai ukuran dimana ia dapat dapat dipecahkan sendiri (base scenario)
  3. Combine, menggabungkan pemecahan/solusi dari seluruh persoalan kecil hingga menjadi solusi untuk persoalan awal.

Contoh

Contoh fungsi rekursif 1: faktorial

Rumus matematis bilangan faktorial :

  • 1 ! = 1
  • 2! = 2 x 1
  • 3! = 3 x 2 x 1
  • n! = n x (n-1) x (n-2) …. x 3 x 2 x 1
  • n! = n x (n-1)!

Mari kita petakan rumus bilangan faktorial dengan tahapan teknik rekursif.

  1. Divide, n! = n x (n-1)!, artinya bahwa n! dapat dipecahkan bila kita mengetahui nilai (n-1)!, dan seterusnya hingga bentuk terkecil yang bisa dipecahkan langsung yakni 1!.
  2. Conquer, jika persoalan sudah mencapai 1!, kita sudah mencapai base scenario, dan nilainya dapat langsung kita berikan yakni 1!=1.
  3. Combine, menggabungkan seluruh hasil pada tahap conquer dari 1! hingga n!

Berdasarkan hasil tersebut kita dapat membuat fungsi faktorial seperti pada sebagai berikut.

def faktorial(x):
  if x<=1: # base scenario
    return 1
  else:
    f = x * faktorial(x-1)
  return f

Jalankan cuplikan kode berikut untuk melihat cara penggunannya.

Contoh fungsi rekursif 2: fibonacci

Rumus matematis bilangan fibonacci

  • f(1) = 1
  • f(2) = 1
  • f(3) = 1 + 1 = 2
  • f(4) = 2 + 1 = 3
  • f(5) = 3 + 2 = 5
  • f(n) = f(n-1) + f(n-2)

Deret fibonacci: 1,1,2,3,5,8,13, ……

Fungsi untuk mencari bilangan fibonacci ke-n secara rekursif

Contoh lain

Beberapa contoh algoritma lain yang menggunakan teknik rekursif antara lain:

  1. Teknik pengurutan merge sort
  2. Teknik pengurutan quick sort

Sekian, semoga bermanfaat.

Salam.

Series Navigation<< Menggunakan modul

You may also like...

Berikan komentar