Rekursi dalam Python

Rekursi merupakan teknik pemrograman ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan suatu permasalahan.

Sebelum mempelajari materi tentang Rekursi dalam Python, terlebih dahulu pelajari tentang: Argumen Fungsi dalam Python, Variabel Global, Lokal, dan Nonlocal dalam Python, dan Kata Kunci global dalam Python.

Pada awalnya, konsep ini mungkin terlihat membingungkan. Sebuah fungsi yang sedang dijalankan dapat memanggil fungsi yang sama kembali. Proses tersebut kemudian berulang sampai mencapai kondisi tertentu yang menyebabkan pemanggilan berhenti.

Contoh sederhana:
def hitung(n):
if n > 0:
print(n)
hitung(n - 1)
hitung(5)

Hasil:
5
4
3
2
1

Pada program tersebut, fungsi `hitung()` memanggil dirinya sendiri menggunakan:
hitung(n - 1)

Nilai `n` terus berkurang sampai kondisi `n > 0` tidak terpenuhi.

Cara Kerja Rekursi

Rekursi bekerja dengan cara memecah suatu masalah menjadi masalah yang lebih kecil dengan bentuk yang serupa. Secara umum, sebuah fungsi rekursif mempunyai dua bagian penting:

• Kondisi dasar.
• Pemanggilan rekursif.

Keduanya sangat penting agar fungsi dapat berhenti.

Contoh:
def hitung(n):
if n == 0:
return
print(n)
hitung(n - 1)

Pada program tersebut:
if n == 0:
return

merupakan kondisi dasar.

Sedangkan:
hitung(n - 1)

merupakan pemanggilan rekursif.

Kondisi Dasar

Kondisi dasar atau kondisi penghentian merupakan bagian yang menentukan kapan rekursi berhenti.

Contoh:
def hitung(n):
if n == 0:
return
print(n)
hitung(n - 1)

Ketika `n` mencapai `0`, perintah `return` dijalankan sehingga fungsi berhenti. Tanpa kondisi dasar, fungsi dapat terus memanggil dirinya sendiri.

Pentingnya Kondisi Dasar

Kondisi dasar berfungsi sebagai batas akhir dari proses rekursi.

Contoh:
def hitung(n):
if n == 0:
return
print(n)
hitung(n - 1)

Jika fungsi dipanggil:
hitung(3)

prosesnya:
hitung(3)
↓
hitung(2)
↓
hitung(1)
↓
hitung(0)
↓
berhenti

Hasil yang ditampilkan:
3
2
1

Rekursi Tanpa Kondisi Dasar

Kesalahan yang sering terjadi adalah membuat fungsi yang terus memanggil dirinya sendiri tanpa kondisi penghentian.

Contoh:
def hitung(n):
print(n)
hitung(n - 1)
hitung(5)

Fungsi tersebut tidak mempunyai kondisi untuk berhenti. Akibatnya, Python akan terus melakukan pemanggilan fungsi sampai batas rekursi tercapai dan menghasilkan kesalahan. Karena itu, setiap fungsi rekursif harus mempunyai kondisi dasar yang jelas.

Rekursi Menghitung Mundur

Salah satu contoh paling sederhana adalah menghitung mundur.
def hitung_mundur(n):
if n == 0:
print("Selesai")
return
print(n)
hitung_mundur(n - 1)
hitung_mundur(5)

Hasil:
5
4
3
2
1
Selesai

Setiap pemanggilan mengurangi nilai `n` sebesar satu.

Rekursi Menghitung Naik

Rekursi juga dapat digunakan untuk menghitung dari angka kecil menuju angka yang lebih besar.

Contoh:
def hitung_naik(n):
if n == 0:
return
hitung_naik(n - 1)
print(n)
hitung_naik(5)

Hasil:
1
2
3
4
5

Perhatikan bahwa `print()` ditempatkan setelah pemanggilan rekursif. Posisi perintah tersebut memengaruhi urutan hasil.

Rekursi untuk Menghitung Faktorial

Salah satu contoh terkenal penggunaan rekursi adalah menghitung faktorial. Faktorial suatu bilangan adalah hasil perkalian bilangan tersebut dengan semua bilangan positif yang lebih kecil darinya.

Contoh:
5! = 5 × 4 × 3 × 2 × 1

Hasilnya:
120

Fungsi rekursif untuk menghitung faktorial:
def faktorial(n):
if n == 0 or n == 1:
return 1
return n * faktorial(n - 1)
print(faktorial(5))

Hasil:
120

Cara Kerja Faktorial secara Rekursif

Ketika menjalankan:
faktorial(5)

Python melakukan proses:
5 × faktorial(4)
↓
4 × faktorial(3)
↓
3 × faktorial(2)
↓
2 × faktorial(1)
↓
1

Kemudian hasil dikembalikan:
1
2 × 1 = 2
3 × 2 = 6
4 × 6 = 24
5 × 24 = 120

Hasil akhirnya adalah `120`.

Rekursi untuk Menjumlahkan Bilangan

Rekursi juga dapat digunakan untuk menghitung jumlah bilangan dari satu nilai tertentu sampai batas tertentu.

Contoh:
def jumlah(n):
if n == 0:
return 0
return n + jumlah(n - 1)
print(jumlah(5))

Hasil:
15

Prosesnya:
5 + jumlah(4)
4 + jumlah(3)
3 + jumlah(2)
2 + jumlah(1)
1 + jumlah(0)

Ketika mencapai `jumlah(0)`, fungsi mengembalikan `0`. 

Kemudian hasil dihitung kembali:
1
1 + 2 = 3
3 + 3 = 6
6 + 4 = 10
10 + 5 = 15

Rekursi pada Deret Fibonacci

Rekursi juga sering digunakan untuk mempelajari deret Fibonacci.

Deret Fibonacci memiliki pola:
0, 1, 1, 2, 3, 5, 8, 13, ...

Setiap nilai diperoleh dari penjumlahan dua nilai sebelumnya.

Fungsi sederhana:
def fibonacci(n):
if n <= 1:
return n
return fibonacci(n - 1) + fibonacci(n - 2)
print(fibonacci(6))

Hasil:
8

Cara kerja fungsi tersebut menggunakan dua pemanggilan rekursif:
fibonacci(n - 1)

dan:
fibonacci(n - 2)

Keduanya kemudian dijumlahkan.

Rekursi pada Struktur Data

Rekursi sangat berguna untuk menangani struktur data yang mempunyai bentuk bertingkat.

Contohnya:

• Struktur folder.
• Struktur pohon.
• Data bertingkat.
• Direktori komputer.
• Struktur organisasi.
• Dokumen yang memiliki bagian dan subbagian.

Misalnya terdapat struktur folder:
Folder Utama
├── Dokumen
│ ├── Tugas
│ └── Laporan
├── Gambar
│ ├── Foto
│ └── Desain
└── Video

Setiap folder dapat memiliki folder lain di dalamnya.

Rekursi dapat digunakan untuk mengunjungi setiap bagian tersebut tanpa harus mengetahui terlebih dahulu berapa banyak tingkat folder yang tersedia.

Rekursi untuk Menampilkan Elemen Daftar

Rekursi juga dapat digunakan untuk memproses daftar.

Contoh:
def tampilkan(data, indeks=0):
if indeks == len(data):
return

print(data[indeks])
tampilkan(data, indeks + 1)

buah = ["Apel", "Jeruk", "Mangga"]
tampilkan(buah)

Hasil:
Apel
Jeruk
Mangga

Parameter `indeks` digunakan untuk mengetahui posisi data yang sedang diproses. Ketika `indeks` sudah sama dengan panjang daftar, fungsi berhenti.

Rekursi dan Perulangan

Rekursi dan perulangan dapat digunakan untuk menyelesaikan beberapa masalah yang sama. Contoh menggunakan perulangan:
for i in range(1, 6):
print(i)

Hasil:
1
2
3
4
5

Contoh menggunakan rekursi:
def tampilkan(n):
if n > 5:
return
print(n)
tampilkan(n + 1)
tampilkan(1)

Hasilnya sama:
1
2
3
4
5

Karena itu, rekursi bukan berarti selalu lebih baik daripada perulangan.vPemilihan teknik bergantung pada jenis masalah yang ingin diselesaikan.

Perbedaan Rekursi dan Perulangan

Berikut dijelaskan perbedaan antara rekursi dan perulangan pada Python.

Rekursi:

• Fungsi memanggil dirinya sendiri.
• Membutuhkan kondisi dasar.
• Cocok untuk masalah yang mempunyai struktur bertingkat.
• Dapat membuat solusi tertentu menjadi lebih sederhana.
• Menggunakan ruang penyimpanan untuk setiap pemanggilan fungsi.

Perulangan:

• Menggunakan struktur seperti `for` atau `while`.
• Tidak membutuhkan pemanggilan fungsi berulang.
• Cocok untuk proses pengulangan sederhana.
• Biasanya lebih mudah dipahami untuk proses berulang yang sederhana.

Ringkasnya:

• Rekursi → fungsi memanggil dirinya sendiri
• Perulangan → perintah dijalankan berulang

Tumpukan Pemanggilan Fungsi

Setiap kali sebuah fungsi memanggil dirinya sendiri, Python perlu menyimpan informasi mengenai pemanggilan tersebut. Informasi tersebut disimpan dalam tumpukan pemanggilan fungsi.

Contoh:
def hitung(n):
if n == 0:
return
print(n)
hitung(n - 1)
hitung(3)

Urutan pemanggilannya:
hitung(3)
hitung(2)
hitung(1)
hitung(0)

Setelah mencapai kondisi dasar, pemanggilan mulai selesai satu per satu. Konsep ini penting untuk memahami bagaimana rekursi bekerja di dalam komputer.

Batas Rekursi

Python memiliki batas jumlah pemanggilan rekursif yang dapat dilakukan secara bertingkat. Hal ini dilakukan untuk mencegah penggunaan sumber daya yang tidak terkendali. Contoh fungsi yang tidak pernah berhenti:
def terus():
terus()
terus()

Fungsi tersebut terus memanggil dirinya sendiri. Akhirnya Python akan menghentikan proses tersebut dan menghasilkan kesalahan yang berkaitan dengan kedalaman rekursi. Karena itu, fungsi rekursif harus selalu mempunyai kondisi dasar.

Kesalahan yang Sering Terjadi

Berikut dijelaskan beberapa bentuk kesalahan yang sering terjadi pada proses rekursi dalam Python.

satu, Tidak mempunyai kondisi dasar.

Contoh:
def hitung(n):
print(n)
hitung(n - 1)

Fungsi tidak mempunyai kondisi untuk berhenti.

dua, Kondisi dasar tidak pernah tercapai.

Contoh:
def hitung(n):
if n == 0:
return
print(n)
hitung(n + 1)

Jika dimulai dari angka positif, nilai `n` terus bertambah sehingga tidak pernah mencapai `0`. Solusinya adalah memastikan perubahan nilai mengarah menuju kondisi dasar.

tiga, Salah menentukan perubahan nilai.

Contoh:
def hitung(n):
if n <= 0:
return
print(n)
hitung(n - 1)

Pada contoh tersebut, nilai `n` berkurang sehingga akhirnya mencapai kondisi dasar.

empat, Lupa menggunakan return.

Pada rekursi yang menghitung nilai, hasil pemanggilan biasanya perlu dikembalikan. Contoh yang benar:
def faktorial(n):
if n == 1:
return 1
return n * faktorial(n - 1)

Jika `return` tidak digunakan pada bagian yang diperlukan, hasil perhitungan dapat menjadi tidak sesuai.

Tips Membuat Fungsi Rekursif

Beberapa hal yang perlu diperhatikan:

• Tentukan kondisi dasar terlebih dahulu.
• Pastikan kondisi dasar dapat dicapai.
• Pastikan setiap pemanggilan mendekati kondisi dasar.
• Gunakan nama parameter yang mudah dipahami.
• Gunakan `return` ketika fungsi perlu menghasilkan nilai.
• Jangan menggunakan rekursi hanya karena dapat digunakan.
• Gunakan perulangan jika masalah lebih sederhana diselesaikan dengan perulangan.
• Perhatikan jumlah pemanggilan rekursif.
• Uji fungsi dengan nilai kecil terlebih dahulu.

Contoh Program Lengkap

Berikut contoh program yang menggunakan rekursi untuk menghitung faktorial:
def faktorial(n):
if n < 0:
return "Bilangan tidak valid"

if n == 0 or n == 1:
return 1

return n * faktorial(n - 1)
angka = 5
hasil = faktorial(angka)

print("Angka:", angka)
print("Faktorial:", hasil)

Hasil:
Angka: 5
Faktorial: 120

Program tersebut mempunyai tiga bagian utama:

1. Pemeriksaan bilangan negatif.
2. Kondisi dasar ketika nilai `n` adalah `0` atau `1`.
3. Pemanggilan fungsi secara rekursif untuk nilai lainnya.

Latihan Pemahaman

Berikut diberikan beberapa contoh latihan pemahaman yang dapat dikerjakan untuk meningkatkan kemampuan dalam penggunaan rekursi dalam Python.

Latihan 1: Menghitung Mundur

Buat fungsi rekursif bernama `hitung_mundur()` yang menampilkan angka dari `10` sampai `1`.

Hasil:
10
9
8
7
6
5
4
3
2
1

Latihan 2: Menghitung Jumlah

Buat fungsi rekursif untuk menghitung:
1 + 2 + 3 + 4 + 5

Hasil yang diharapkan:
15

Latihan 3: Faktorial

Buat fungsi rekursif untuk menghitung:
6!

Hasil:
720

Latihan 4: Fibonacci

Buat fungsi rekursif untuk mendapatkan nilai Fibonacci ke-7.

Gunakan pola:
0, 1, 1, 2, 3, 5, 8, ...

Tentukan hasil yang diperoleh.

Ringkasan Materi

Beberapa poin penting tentang rekursi:

• Rekursi adalah teknik ketika fungsi memanggil dirinya sendiri.
• Fungsi rekursif harus mempunyai kondisi dasar.
• Kondisi dasar menentukan kapan rekursi berhenti.
• Setiap pemanggilan harus bergerak menuju kondisi dasar.
• `return` dapat digunakan untuk mengembalikan hasil rekursi.
• Rekursi dapat digunakan untuk menghitung faktorial.
• Rekursi dapat digunakan untuk menghitung deret Fibonacci.
• Rekursi dapat digunakan untuk menjumlahkan nilai.
• Rekursi dapat digunakan untuk memproses data bertingkat.
• Rekursi dapat digunakan untuk struktur folder dan struktur pohon.
• Rekursi dan perulangan dapat menyelesaikan beberapa masalah yang sama.
• Rekursi dapat menggunakan lebih banyak ruang penyimpanan karena setiap pemanggilan fungsi perlu disimpan.
• Rekursi tanpa kondisi berhenti dapat menyebabkan kesalahan kedalaman rekursi.

Kesimpulan

Rekursi merupakan teknik pemrograman yang memungkinkan sebuah fungsi memanggil dirinya sendiri. Teknik ini digunakan untuk menyelesaikan masalah dengan cara memecah masalah menjadi bagian yang lebih kecil tetapi memiliki pola penyelesaian yang sama.

Dua bagian terpenting dalam fungsi rekursif adalah kondisi dasar dan pemanggilan rekursif. Kondisi dasar berfungsi menghentikan proses, sedangkan pemanggilan rekursif membuat fungsi mengerjakan bagian masalah yang lebih kecil.

Rekursi dapat digunakan untuk berbagai kebutuhan, seperti menghitung faktorial, membuat deret Fibonacci, menjumlahkan bilangan, memproses daftar, serta menangani struktur data bertingkat.

Walaupun sangat berguna, rekursi tidak selalu menjadi pilihan yang paling sederhana. Untuk pengulangan biasa, struktur `for` atau `while` sering lebih mudah digunakan. Rekursi lebih menarik ketika masalah mempunyai struktur bertingkat atau ketika suatu masalah dapat dipecah menjadi masalah yang lebih kecil dengan pola yang sama.

Dengan memahami kondisi dasar, pemanggilan rekursif, `return`, dan cara kerja pemanggilan fungsi, konsep rekursi akan menjadi lebih mudah dipahami dan diterapkan dalam berbagai program Python.

Artikel ini akan dibaca oleh: Caesarrio Bina Putra, Cahya Purnama Sejati, Cantika Tiara Kusuma Dewi, Chelsea Nadia Syahrani, dan Clara Maurin Angelina.

Location: Kota Semarang, Jawa Tengah, Indonesia

Berbagi :