E-Learning DAA: Fungsi dan Algoritma Rekursif

Tulisan ini adalah upaya penulis memahami materi yang di-share dosen mata kuliah Desain Analisis Algoritma pada E-Learning

rojauna zalfatthoriq

5 min readFeb 26, 2024

Sudah diketahui secara umum bahwa fungsi dapat memanggil fungsi lainnya.

Sekarang, bisakah sebuah fungsi memanggil dirinya sendiri?

Jawabnya: bisa!

Kondisi ini disebut dengan fungsi rekursif / algoritma rekursif.

Contoh: Bilangan faktorial (!)

Bilangan faktorial, secara sederhana dipahami sebagai berikut.
2! = 2 × 1;
3! = 3 × 2 × 1 (atau 3 × 2!);
4! = 4 × 3 × 2 × 1 (atau 4 × 3!; atau 4 × 3 × 2!);
dst.

Perhatikan sebuah fungsi rekursif dalam bahasa Java berikut,

Lakukan tracing untuk cetak1(3) !

Untuk melakukan tracing cetak1(3), kita akan melacak setiap panggilan rekursif dan hasil cetakan dari metode tersebut. Berikut adalah langkah-langkah tracing-nya:

Panggilan pertama: cetak1(3)

Masuk ke dalam metode cetak1(3).
i saat ini bernilai 3.
Karena i ≥ 1, maka memanggil cetak1(i — 1) yaitu cetak1(2).

Panggilan kedua: cetak1(2)

Masuk ke dalam metode cetak1(2).
i saat ini bernilai 2.
Karena i ≥ 1, maka memanggil cetak1(i — 1) yaitu cetak1(1).

Panggilan ketiga: cetak1(1)

Masuk ke dalam metode cetak1(1).
i saat ini bernilai 1.
Karena i ≥ 1, maka memanggil cetak1(i — 1) yaitu cetak1(0).

Panggilan keempat: cetak1(0)

Masuk ke dalam metode cetak1(0).
Karena i tidak lebih besar atau sama dengan 1, maka tidak ada panggilan rekursif lagi.
Cetak nilai i, yaitu 0.

Kembali ke panggilan sebelumnya: cetak1(1)

Panggilan sebelumnya masih menunggu hasil dari cetak1(0).
Setelah cetak1(0) selesai, lanjut ke perintah berikutnya.
Cetak nilai i, yaitu 1.

Kembali ke panggilan sebelumnya: cetak1(2)

Panggilan sebelumnya masih menunggu hasil dari cetak1(1).
Setelah cetak1(1) selesai, lanjut ke perintah berikutnya.
Cetak nilai 1, yaitu 2.

Kembali ke panggilan pertama: cetak1(3)

Panggilan sebelumnya masih menunggu hasil dari cetak1(2).
Setelah cetak1(2) selesai, lanjut ke perintah berikutnya.
Cetak nilai i, yaitu 3.

IMPLEMENTASI dalam bahasa Java

Java: Output Algoritma Tracing “cetak1(3)”

Fungsi rekursif / algoritma rekursif dalam bahasa Python

Cetak2

Untuk melakukan tracing pada fungsi cetak2(3) dalam Python, kita akan melacak setiap pemanggilan rekursif dan output yang dihasilkan. Berikut adalah langkah-langkah tracing-nya:

Panggilan pertama: cetak2(3)

Cetak nilai x, yaitu 3.
Karena x ≥ 1, maka memanggil cetak2(x — 1) yaitu cetak2(2).

Panggilan kedua: cetak2(2)

Cetak nilai x, yaitu 2.
Karena x ≥ 1, maka memanggil cetak2(x — 1) yaitu cetak2(1).

Panggilan ketiga: cetak2(1)

Cetak nilai x, yaitu 1.
Karena x ≥ 1, maka memanggil cetak2(x — 1) yaitu cetak2(0).

Panggilan keempat: cetak2(0)

Cetak nilai x, yaitu 0.
Karena x tidak lebih besar atau sama dengan 1, maka tidak ada panggilan rekursif lagi.

Cetak3

Sekarang, mari kita lakukan tracing untuk cetak3(3):

Panggilan pertama: cetak3(3)

Karena x (3) lebih besar atau sama dengan 1, maka cetak nilai x, yaitu 3.
Panggil cetak3(x — 1), yang akan menjadi cetak3(2).

Panggilan kedua: cetak3(2)

Karena x (2) lebih besar atau sama dengan 1, maka cetak nilai x, yaitu 2.
Panggil cetak3(x — 1), yang akan menjadi cetak3(1).

Panggilan ketiga: cetak3(1)

Karena x (1) lebih besar atau sama dengan 1, maka cetak nilai x, yaitu 1.
Panggil cetak3(x — 1), yang akan menjadi cetak3(0).

Panggilan keempat: cetak3(0)

Karena x (0) tidak lebih besar atau sama dengan 1, maka tidak ada cetakan lagi dan rekursi berhenti di sini.

Cetak4

Mari kita lakukan tracing untuk fungsi cetak4(3):

Panggilan pertama: cetak4(3)

Karena x (3) lebih besar atau sama dengan 1, maka panggil cetak4(x — 1), yang akan menjadi cetak4(2).

Panggilan kedua: cetak4(2)

Karena x (2) lebih besar atau sama dengan 1, maka panggil cetak4(x — 1), yang akan menjadi cetak4(1).

Panggilan ketiga: cetak4(1)

Karena x (1) lebih besar atau sama dengan 1, maka panggil cetak4(x — 1), yang akan menjadi cetak4(0).

Panggilan keempat: cetak4(0)

Karena x (0) tidak lebih besar atau sama dengan 1, maka tidak ada pemanggilan rekursif lagi.

Kembali ke panggilan sebelumnya: cetak4(1)

Cetak nilai x, yaitu 1.

Kembali ke panggilan sebelumnya: cetak4(2)

Cetak nilai x, yaitu 2.

Kembali ke panggilan awal: cetak4(3)

Cetak nilai x, yaitu 3.

REKURSI: Membuat solusi dengan mereduksi masalah menjadi satu / lebih masalah-masalah serupa yang lebih kecil

CONTOH: Faktorial (!)

Fungsi faktorial: sebuah fungsi yang dapat direpresentasikan dalam bentuk rekursif!

Dapat dipecah menjadi masalah kecil yang serupa;
Dapat dipecah menjadi bentuk faktorial yang yang lebih kecil.

Algoritma faktorial dalam bahasa Python:

Secara umum, Algoritma rekursif mengandung 2 kasus:
Basis (base case)
— Satu/lebih kasus yang pemecahannya tanpa pemanggilan rekursif.
Rekurens / Kasus Induktif (recurrent)
— Pemecahannya dilakukan dengan pemanggilan rekursif.
— Recursive Call: menyelesaikan masalah serupa yang lebih sederhana.