Bentuk Fungsi Rekursif

Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan:

def kali(a, b):

    return a if b == 1 else a + kali(a, b - 1)

Bagaimana cara kerja fungsi rekursif ini? Sederhananya, selama nilai b bukan 1, fungsi akan terus memanggil perintah a + kali(a, b - 1), yang tiap tahapnya memanggil dirinya sendiri sambil mengurangi nilai b. Mari kita coba panggil fungsi kali dan uraikan langkah pemanggilannya:

kali(2, 4)

  -> 2 + kali(2, 3)

  -> 2 + (2 + kali(2, 2))

  -> 2 + (2 + (2 + kali(2, 1)))

  -> 2 + (2 + (2 + 2))

  -> 2 + (2 + 4)

  -> 2 + 6

  -> 8

Perhatikan bahwa sebelum melakukan penambahan program melakukan pemanggilan fungsi rekursif terlebih dahulu sampai fungsi rekursif mengembalikan nilai pasti (2). Setelah menghilangkan semua pemanggilan fungsi, penambahan baru dilakukan, mulai dari nilai kembalian dari fungsi yang paling terakhir. Mari kita lihat contoh fungsi rekursif lainnya, yang digunakan untuk melakukan perhitungan faktorial:

def faktorial(n):

    return n if n == 1 else n * faktorial(n - 1)

Fungsi faktorial memiliki cara kerja yang sama dengan fungsi kali. Mari kita panggil dan lihat langkah pemanggilannya:

faktorial(5)

  -> 5 * faktorial(4)

  -> 5 * (4 * faktorial(3))

  -> 5 * (4 * (3 * faktorial(2)))

  -> 5 * (4 * (3 * (2 * faktorial(1))))

  -> 5 * (4 * (3 * (2 * 1)))

  -> 5 * (4 * (3 * 2))

  -> 5 * (4 * 6)

  -> 5 * 24

  -> 120

Dengan melihat kemiripan cara kerja serta kode dari fungsi faktorial dan kali, kita dapat melihat bagaimana fungsi rekursif memiliki dua ciri khas:

1. Fungsi rekursif selalu memiliki kondisi yang menyatakan kapan fungsi tersebut berhenti. Kondisi ini harus dapat dibuktikan akan tercapai, karena jika tidak tercapai maka kita tidak dapat membuktikan bahwa fungsi akan berhenti, yang berarti algoritma kita tidak benar.
2. Fungsi rekursif selalu memanggil dirinya sendiri sambil mengurangi atau memecahkan data masukan setiap panggilannya. Hal ini penting diingat, karena tujuan utama dari rekursif ialah memecahkan masalah dengan mengurangi masalah tersebut menjadi masalah-masalah kecil.

Setiap fungsi rekursif yang ada harus memenuhi kedua persyaratan di atas untuk memastikan fungsi rekursif dapat berhenti dan memberikan hasil. Kebenaran dari nilai yang dihasilkan tentu saja memerlukan pembuktian dengan cara tersendiri. Tetapi sebelum masuk ke analisa dan pembuktian fungsi rekursif, mari kita lihat kegunaan dan contoh-contoh fungsi rekursif lainnya lagi.

Salah satu konsep paling dasar dalam ilmu komputer dan pemrograman adalah pengunaan fungsi sebagai abstraksi untuk kode-kode yang digunakan berulang kali. Kedekatan ilmu komputer dengan matematika juga menyebabkan konsep-konsep fungsi pada matematika seringkali dijumpai. Salah satu konsep fungsi pada matematika yang ditemui pada ilmu komputer adalah fungsi rekursif: sebuah fungsi yang memanggil dirinya sendiri.

Kode berikut memperlihatkan contoh fungsi rekursif, untuk menghitung hasil kali dari dua bilangan: