Program Studi Bisnis Digital • FEB UNDIP

Algoritma dan Pemrograman

Pertemuan 10 — Rekursi dan Algoritma Pengurutan (Sorting)

Bagaimana fungsi memanggil dirinya sendiri, dan bagaimana komputer merapikan data secara otomatis — dua fondasi yang dipakai mesin pencari produk, sistem rekomendasi, dan laporan keuangan digital.

RPS MINGGU 11 • 2 × 50 MENIT

Selamat datang di pertemuan kesepuluh Algoritma dan Pemrograman. Hari ini Anda akan belajar dua konsep yang sekilas terasa abstrak tapi sangat konkret dampaknya: rekursi, yaitu fungsi yang memanggil dirinya sendiri, dan algoritma pengurutan atau sorting, yaitu cara komputer merapikan data dari kecil ke besar atau sebaliknya. Sampaikan kepada mahasiswa bahwa setiap kali mereka mengurutkan produk termurah di Tokopedia atau melihat daftar transaksi terbaru di aplikasi bank, di baliknya ada algoritma sorting yang bekerja. Ingatkan juga bahwa materi ini murni konseptual dan tidak memerlukan pengetahuan pemrograman lanjutan, cukup pemahaman dasar fungsi dari pertemuan 6 dan list dari pertemuan 7. Ajak mahasiswa untuk aktif mengikuti proses hitung manual di layar, karena rekursi dan sorting paling mudah dipahami lewat jejak langkah demi langkah, bukan hafalan definisi.

Bagian 1 dari 3

Konsep Rekursi

Fungsi yang memanggil dirinya sendiri: definisi, anatomi, jejak eksekusi, dan risikonya.

Tujuan Pembelajaran Hari Ini

Setelah pertemuan ini, Anda diharapkan mampu memahami empat hal berikut (Sub-CPMK Minggu 11).

TUJUAN 1

Menjelaskan konsep rekursi, base case, dan recursive case pada fungsi Python.

TUJUAN 2

Menelusuri jejak eksekusi (call stack) fungsi rekursif secara manual, langkah demi langkah.

TUJUAN 3

Menjelaskan cara kerja algoritma bubble sort, selection sort, dan quick sort.

TUJUAN 4

Membandingkan efisiensi algoritma sorting untuk memilih pendekatan yang tepat pada kasus bisnis.

Dari Mana Kita Melangkah?

Pertemuan 9 membahas array dengan NumPy. Rekursi dan sorting hari ini memakai fondasi fungsi (P6) dan list (P7) untuk memproses data terurut.

Pertemuan 6

Parameter & argumen
Nilai kembali (return)
Fungsi memanggil fungsi lain

Pertemuan 7–9

List dan indexing
Perulangan atas list
Array NumPy

Pertemuan 10 (hari ini)

Fungsi memanggil dirinya sendiri
Merapikan urutan list/array
Fondasi untuk pencarian (P11)

Apa Itu Rekursi?

Rekursi adalah teknik di mana sebuah fungsi memanggil dirinya sendiri untuk memecah masalah besar menjadi versi yang lebih kecil, sampai mencapai kondisi paling sederhana.

Base Case (Kondisi Dasar)

Kondisi paling sederhana yang jawabannya sudah diketahui langsung, tanpa perlu memanggil fungsi lagi.

Contoh: faktorial dari 1 adalah 1.

Recursive Case (Kondisi Rekursif)

Kondisi di mana fungsi memanggil dirinya sendiri dengan masalah yang lebih kecil dari sebelumnya.

Contoh: faktorial dari n = n × faktorial dari (n−1).

Setiap fungsi rekursif wajib punya base case. Tanpa itu, fungsi akan memanggil dirinya terus-menerus hingga error RecursionError.

Anatomi Fungsi Rekursif di Python

def faktorial(n):
  if n == 1:    # base case
    return 1
  else:        # recursive case
    return n * faktorial(n - 1)

BARIS 2–3

Cek apakah sudah sampai kondisi paling sederhana. Jika ya, langsung kembalikan nilai pasti.

BARIS 4–5

Jika belum, panggil fungsi yang sama dengan n − 1 agar masalah mengecil tiap panggilan.

Hitung dari Nol: Jejak faktorial(5)

Setiap panggilan menunggu hasil panggilan di bawahnya, lalu mengalikan setelah base case tercapai.

Proses Unwind (dari base case naik kembali)

Langkah	Perhitungan	Nilai
faktorial(1)	base case	1
faktorial(2)	2 × 1	2
faktorial(3)	3 × 2	6
faktorial(4)	4 × 6	24
faktorial(5)	5 × 24	120

HASIL AKHIR faktorial(5)

120

Call Stack: Tumpukan Pemanggilan Fungsi

Python menyimpan setiap panggilan yang belum selesai di sebuah tumpukan (stack), lalu menyelesaikannya dari atas ke bawah — mirip tumpukan piring.

Coba Sendiri: Menelusuri Call Stack Rekursi

Panggil fungsi rekursif langkah demi langkah dan lihat tumpukan bertambah saat memanggil turun, lalu mengurai saat base case tercapai.

Rekursi vs Iterasi: Dua Cara Mencapai Hasil Sama

Iterasi (Perulangan for/while)

hasil = 1
for i in range(1, n+1):
hasil = hasil * i

Memakai satu variabel penampung yang diperbarui
Tidak menambah beban tumpukan panggilan

Rekursi (Fungsi memanggil diri)

def faktorial(n):
if n==1: return 1
return n*faktorial(n-1)

Kode lebih ringkas untuk pola berulang bersarang
Cocok untuk struktur yang sifatnya alami rekursif

Kasus Bisnis: Diskon Berjenjang UMKM

Toko online UMKM memberi diskon 10% tiap kelipatan Rp 100.000 belanja, maksimum 3 tingkat. Kita hitung total diskon untuk belanja Rp 350.000 secara rekursif.

Walkthrough Bertahap

Tingkat 1: belanja ≥ Rp 100.000 → diskon 10% dari Rp 100.000 = Rp 10.000, sisa dihitung untuk tingkat berikutnya
Tingkat 2: belanja ≥ Rp 100.000 lagi → diskon 10% dari Rp 100.000 = Rp 10.000
Tingkat 3: belanja ≥ Rp 100.000 lagi → diskon 10% dari Rp 100.000 = Rp 10.000
Base case: sisa belanja Rp 50.000 < Rp 100.000 → berhenti, tidak ada diskon tambahan

TOTAL DISKON (3 × Rp 10.000)

Rp 30.000

Waspada: Bahaya Rekursi Tanpa Kendali

Kesalahan Umum

Lupa menulis base case sama sekali
Base case ada, tapi tidak pernah tercapai (n bertambah, bukan berkurang)
Rekursi terlalu dalam untuk data besar (ribuan level)

Akibatnya

Tumpukan panggilan terus bertambah tanpa henti
Python menghentikan program: RecursionError: maximum recursion depth exceeded
Program terasa "hang" sebelum akhirnya error

Selalu pastikan setiap panggilan rekursif membawa masalah yang lebih kecil menuju base case — ini aturan emas menulis fungsi rekursif yang aman.

Bagian ini penting untuk disampaikan dengan tegas, karena kesalahan rekursi adalah salah satu bug yang paling membingungkan bagi programmer pemula ketika pertama kali muncul di layar mereka. Jelaskan bahwa Python sengaja membatasi kedalaman rekursi, biasanya sekitar seribu level, sebagai pengaman agar komputer tidak kehabisan memori akibat tumpukan panggilan yang tidak pernah selesai. Tunjukkan bahwa penyebab paling umum adalah base case yang lupa ditulis, atau base case yang ada tapi nilai parameternya justru membesar bukannya mengecil setiap pemanggilan. Ingatkan mahasiswa bahwa aturan emasnya sederhana, setiap panggilan rekursif baru harus membawa versi masalah yang lebih kecil dan pasti bergerak menuju base case, sama seperti yang mereka lihat pada faktorial dan diskon berjenjang tadi.

Bagian 2 dari 3

Algoritma Pengurutan (Sorting)

Bubble sort, selection sort, dan quick sort — tiga cara komputer merapikan data.

Sekarang kita berpindah ke topik kedua hari ini, algoritma pengurutan atau sorting, yang jawabannya sudah sangat sering Anda gunakan tanpa sadar setiap kali menekan tombol urutkan harga termurah di aplikasi belanja online. Anda akan mempelajari tiga algoritma klasik, bubble sort dan selection sort yang sederhana namun kurang efisien untuk data besar, serta quick sort yang lebih canggih dengan pendekatan membagi masalah menjadi lebih kecil. Kita akan menelusuri bubble sort langkah demi langkah secara manual, mirip dengan yang kita lakukan pada faktorial tadi, supaya Anda benar-benar memahami mekanismenya bukan hanya menghafal kodenya. Di akhir bagian ini Anda akan bisa membandingkan efisiensi ketiga algoritma dan memahami mengapa quick sort lebih disukai untuk data dalam jumlah besar seperti daftar transaksi harian sebuah e-commerce.

Mengapa Sorting Penting dalam Bisnis Digital?

Data yang terurut mempercepat pencarian, memperjelas laporan, dan menjadi dasar keputusan bisnis.

E-COMMERCE

Urutkan produk dari harga termurah/termahal atau rating tertinggi di Tokopedia/Shopee.

KEUANGAN

Urutkan transaksi berdasarkan tanggal atau nominal terbesar pada laporan mutasi rekening.

UMKM

Urutkan pelanggan berdasarkan total belanja untuk menentukan target promosi loyalitas.

Mulai bagian ini dengan bertanya kepada mahasiswa, kapan terakhir kali mereka menekan tombol urutkan di sebuah aplikasi, jawabannya hampir pasti baru saja terjadi hari ini. Jelaskan bahwa di balik tombol sederhana itu, komputer menjalankan algoritma sorting yang membandingkan dan menukar posisi data hingga urutannya benar sesuai kriteria yang diminta. Tiga contoh di layar menunjukkan bahwa sorting bukan sekadar latihan akademik, melainkan kebutuhan nyata mulai dari mengurutkan produk di marketplace, transaksi di aplikasi perbankan, sampai data pelanggan pada sistem UMKM sederhana yang mungkin mereka bangun sendiri kelak. Tekankan bahwa memahami cara kerja sorting membantu mahasiswa memilih algoritma yang tepat, karena algoritma yang salah pilih bisa membuat aplikasi terasa lambat ketika data sudah membesar.

Bubble Sort: Bandingkan & Tukar Berulang

Membandingkan dua elemen bersebelahan, menukarnya jika urutan salah, lalu mengulang dari awal array hingga tidak ada lagi pertukaran.

for i in range(len(data)-1):
  for j in range(len(data)-1-i):
    if data[j] > data[j+1]:
      data[j], data[j+1] = data[j+1], data[j]

Disebut “bubble” (gelembung) karena elemen terbesar perlahan “naik” ke posisi paling kanan tiap putaran, seperti gelembung udara naik ke permukaan.

Hitung dari Nol: Bubble Sort Harga Produk

Array harga (ribuan rupiah) sebuah toko online: [50, 20, 80, 10]. Urutkan naik (ascending).

Jejak Perbandingan & Pertukaran

Langkah	Perhitungan	Nilai (Array)
Putaran 1, Bandingkan 1	50 vs 20 → tukar	[20,50,80,10]
Putaran 1, Bandingkan 2	50 vs 80 → tetap	[20,50,80,10]
Putaran 1, Bandingkan 3	80 vs 10 → tukar	[20,50,10,80]
Putaran 2, Bandingkan 1	20 vs 50 → tetap	[20,50,10,80]
Putaran 2, Bandingkan 2	50 vs 10 → tukar	[20,10,50,80]
Putaran 3, Bandingkan 1	20 vs 10 → tukar	[10,20,50,80]

ARRAY TERURUT

[10, 20, 50, 80]

Klik tabel ini baris demi baris dan minta mahasiswa menebak hasil sebelum Anda menampilkan kolom nilai, supaya mereka aktif berpikir bukan hanya membaca. Pada putaran pertama, kita membandingkan tiga pasang elemen bersebelahan dan menukar posisi setiap kali elemen kiri lebih besar dari elemen kanan, sehingga angka delapan puluh, yang terbesar, berpindah ke posisi paling kanan di akhir putaran. Pada putaran kedua kita tidak perlu lagi memeriksa posisi terakhir karena sudah pasti benar, sehingga jumlah perbandingan berkurang satu, dan pola ini berulang hingga putaran ketiga menghasilkan array yang sepenuhnya terurut. Tekankan bahwa proses bandingkan-dan-tukar seperti ini persis yang terjadi ketika sebuah sistem UMKM mengurutkan daftar harga produk dari termurah, hanya saja pada data ribuan produk prosesnya dilakukan otomatis oleh komputer dalam hitungan milidetik.

Selection Sort: Pilih yang Terkecil, Lalu Tukar

Mencari elemen terkecil di sisa array, menukarnya ke posisi terdepan yang belum terurut, lalu mengulang untuk sisa array berikutnya.

for i in range(len(data)):
  idx_min = i
  for j in range(i+1, len(data)):
    if data[j] < data[idx_min]:
      idx_min = j
  data[i], data[idx_min] = data[idx_min], data[i]

Beda dari bubble sort: selection sort hanya menukar satu kali per putaran (setelah elemen terkecil ditemukan), bukan setiap kali perbandingan.

Selection sort punya logika yang sedikit berbeda dari bubble sort meski tujuannya sama, yaitu merapikan urutan data dari kecil ke besar. Jelaskan bahwa algoritma ini bekerja dengan mencari elemen paling kecil di seluruh sisa array yang belum terurut, mencatat posisinya, baru kemudian menukarnya ke posisi terdepan yang tersisa, seperti memilih siswa terpendek dalam barisan lalu memindahkannya ke depan satu per satu. Tekankan perbedaan penting yang tertulis di layar, selection sort hanya melakukan satu kali pertukaran per putaran setelah proses pencarian selesai, berbeda dengan bubble sort yang bisa menukar berkali-kali dalam satu putaran. Ajak mahasiswa membayangkan efisiensi ini penting saat operasi tukar data itu mahal secara komputasi, misalnya menukar baris data pelanggan yang besar pada sebuah sistem UMKM.

Quick Sort: Bagi, Taklukkan, Gabungkan

Pilih satu elemen sebagai pivot, kelompokkan data lebih kecil di kiri dan lebih besar di kanan, lalu ulangi (rekursif) pada tiap kelompok.

Quick sort adalah algoritma yang lebih canggih dan langsung menghubungkan kita kembali ke konsep rekursi yang dipelajari di awal pertemuan hari ini. Jelaskan diagram di layar tahap demi tahap, kita memilih satu elemen sebagai pivot, di sini angka empat puluh, lalu memisahkan sisa elemen menjadi dua kelompok, yang lebih kecil di kiri dan yang lebih besar di kanan pivot. Setiap kelompok kecil itu kemudian diurutkan lagi dengan cara yang sama secara rekursif, memanggil fungsi quick sort pada dirinya sendiri untuk kelompok yang lebih kecil, sampai akhirnya setiap kelompok tinggal berisi satu atau nol elemen dan otomatis terurut. Tekankan bahwa pendekatan bagi-dan-taklukkan seperti ini jauh lebih cepat dibanding bubble sort atau selection sort untuk data besar, itulah sebabnya quick sort banyak dipakai pada sistem nyata seperti pengurutan jutaan produk di marketplace besar Indonesia.

Perbandingan Efisiensi Tiga Algoritma Sorting

Kompleksitas Waktu (Notasi Big-O)

Algoritma	Rata-rata	Terburuk	Cocok Untuk
Bubble Sort	O(n²)	O(n²)	Data sangat kecil, tujuan belajar
Selection Sort	O(n²)	O(n²)	Data kecil, minim operasi tukar
Quick Sort	O(n log n)	O(n²)	Data besar, kebutuhan produksi

Untuk 1.000 produk di sebuah marketplace: bubble/selection sort butuh ∼1.000.000 operasi, quick sort hanya ∼10.000 operasi — jauh lebih cepat.

Tabel ini merangkum apa yang sudah kita pelajari sekaligus menjawab pertanyaan praktis, algoritma mana yang sebaiknya dipilih untuk kebutuhan nyata. Notasi O besar ini menggambarkan seberapa cepat pertumbuhan jumlah operasi ketika jumlah data bertambah, semakin kecil pangkatnya semakin efisien algoritma tersebut untuk data besar. Perhatikan bahwa bubble sort dan selection sort punya kompleksitas n kuadrat, artinya kalau data menjadi dua kali lipat, jumlah operasinya bisa menjadi empat kali lipat, sementara quick sort jauh lebih hemat dengan kompleksitas n log n. Contoh angka pada callout di layar menunjukkan perbedaan nyata pada seribu produk, jadi sekarang mahasiswa bisa memahami mengapa aplikasi seperti Tokopedia atau Bukalapak tidak mungkin memakai bubble sort untuk mengurutkan jutaan produknya secara real-time.

Coba Sendiri: Membandingkan Bubble, Selection, dan Quick Sort

Jalankan ketiga algoritma sorting pada deretan data yang sama dan amati jumlah langkah serta kurva Big-O saat data bertambah.

Bagian 3 dari 3

Latihan & Rangkuman

Uji pemahaman Anda dengan latihan mandiri, lalu kita rangkum sebelum melanjutkan ke pertemuan berikutnya.

Latihan Mandiri & Ringkasan

Latihan (kerjakan di Python)

Tulis fungsi rekursif jumlah_hingga(n) yang menghitung 1+2+…+n
Telusuri manual jejak jumlah_hingga(4) seperti contoh faktorial
Urutkan array harga [70, 30, 90, 40] dengan bubble sort, tulis tiap putaran

Ringkasan Hari Ini

Rekursi = fungsi memanggil diri sendiri; wajib punya base case
Call stack menyimpan panggilan yang belum selesai
Bubble/selection sort sederhana; quick sort lebih efisien (O(n log n))
Selanjutnya: Pertemuan 11 — Pencarian Data (linear vs binary search)

Berikan waktu sekitar sepuluh menit bagi mahasiswa mengerjakan latihan ini secara mandiri atau berpasangan, dan dorong mereka menuliskan jejak eksekusi seperti tabel yang sudah kita telusuri bersama tadi, bukan hanya menebak jawaban akhir. Latihan jumlah_hingga sengaja mirip pola faktorial supaya mahasiswa berlatih mengenali base case dan recursive case pada kasus baru secara mandiri, sementara latihan bubble sort menguatkan kemampuan menelusuri proses bandingkan dan tukar. Saat menutup pertemuan, ingatkan kembali empat poin ringkasan di layar dan tekankan bahwa rekursi serta sorting bukan topik yang berdiri sendiri, melainkan fondasi untuk pertemuan sebelas tentang pencarian data, di mana binary search yang efisien hanya bisa bekerja pada data yang sudah terurut seperti yang baru saja kita pelajari. Ucapkan Terima Kasih atas partisipasi aktif mahasiswa dan ingatkan mereka membawa laptop dengan Python siap pakai untuk sesi pencarian data minggu depan.