Perulangan dan rekursi
Dua cara mengulang pekerjaan: perulangan yang menelusuri data, dan fungsi yang memanggil dirinya sendiri. for, while, break, off-by-one, base case, batas stack, dan memoization, lengkap dengan output asli.
Bagian 5 membahas cara mengambil keputusan. Bagian ini membahas struktur kontrol ketiga dari bagian 0: perulangan, mengerjakan sesuatu lebih dari sekali. Ada dua caranya. Loop mengulang sebuah blok kode. Rekursi membuat sebuah fungsi memanggil dirinya sendiri untuk potongan masalah yang lebih kecil. Keduanya bisa menyelesaikan masalah yang sama; yang berguna adalah tahu kapan masing-masing paling cocok.
Menelusuri sebuah koleksi
Kebanyakan loop menelusuri koleksi: setiap item di list, setiap baris di file, setiap baris hasil query. Python dibangun di sekitar ide ini. Tutorialnya menyebut: “Python’s for statement iterates over the items of any sequence (a list or a string), in the order that they appear in the sequence”, yang “differs a bit from what you may be used to in C or Pascal”. Jadi for di Python langsung menelusuri item, agak berbeda dari C atau Pascal.
prices = [12, 5, 30]
for price in prices:
print(price)
12
5
30
Kalau butuh posisinya juga, minta saja daripada menghitung sendiri:
for i, price in enumerate(prices):
print(i, price)
0 12
1 5
2 30
Kalau butuh deretan angka, range menyediakannya. Perhatikan di mana ia berhenti:
>>> list(range(5)), list(range(1, 5))
([0, 1, 2, 3, 4], [1, 2, 3, 4])
range(5) adalah 0 sampai 4, bukan 0 sampai 5. Ujungnya tidak pernah ikut, dan itu pas untuk indeks list berisi 5 item.
Padanannya di JavaScript adalah for...of, yang “executes a loop that operates on a sequence of values sourced from an iterable object.” Jangan tertukar dengan for...in, yang “iterates over all enumerable string properties of an object”, sehingga pada array yang didapat adalah indeks dalam bentuk string:
const prices = [12, 5, 30];
for (const p of prices) console.log(p); // 12, 5, 30
for (const k in prices) console.log(typeof k, k); // string 0, string 1, string 2
Saran MDN untuk array: “It is better to use a for loop with a numeric index, Array.prototype.forEach(), or the for...of loop”.
Go: satu loop untuk semuanya
Go hanya punya satu kata kunci perulangan. Effective Go menyebut for di Go “unifies for and while and there is no do-while”: menyatukan for dan while, dan tidak ada do-while. Kata kunci yang sama dipakai untuk tiga bentuk:
// penghitung klasik
for i := 0; i < 3; i++ {
fmt.Print(i, " ")
}
// "while": hanya kondisi
for n != 1 {
// ...
}
// menelusuri koleksi
for i, p := range prices {
fmt.Println(i, p)
}
PHP: foreach dan jebakan referensi
foreach di PHP bekerja seperti for di Python, dengan key yang tersedia kalau dibutuhkan:
$prices = [12, 5, 30];
foreach ($prices as $i => $price) {
echo "$i $price\n";
}
// 0 12
// 1 5
// 2 30
Untuk mengubah item di tempatnya, PHP membolehkan loop dengan referensi &. Ini membawa jebakan terkenal yang tercatat di manual: “A reference to the $value of the last array element remains even after the foreach loop. It is recommended to destroy it using unset().” Referensi ke elemen terakhir tetap tertinggal setelah loop selesai, jadi sebaiknya di-unset(). Beginilah yang terjadi kalau lupa:
$prices = [12, 5, 30];
foreach ($prices as &$p) {
$p = $p * 2;
}
foreach ($prices as $p) { } // memakai ulang $p, yang masih menunjuk item terakhir
echo json_encode($prices); // [24,10,10] ← 60 tertimpa
Tambahkan unset($p); setelah loop pertama, dan hasilnya menjadi [24,10,60] seperti yang diharapkan.
while: ulangi sampai ada yang berubah
Loop while mengulang selama kondisinya benar. Cocok saat kita tidak tahu sejak awal berapa langkah yang dibutuhkan. Contoh ini terus menerapkan aturan sederhana sampai angkanya menjadi 1:
n = 10
steps = 0
while n != 1:
n = n // 2 if n % 2 == 0 else 3 * n + 1
steps += 1
print("steps:", steps) # steps: 6
Risiko while adalah loop yang tidak pernah berhenti. Sebelum menulisnya, tanyakan: apa yang berubah di setiap putaran, dan bagaimana saya tahu perubahan itu pada akhirnya membuat kondisinya salah?
Berhenti lebih awal: break, continue, dan else pada loop Python
breaklangsung keluar dari loop.continuemelewati sisa putaran ini dan lanjut ke putaran berikutnya.
Python punya tambahan yang tidak biasa: else pada loop. Kata tutorialnya: “If the loop finishes without executing the break, the else clause executes.” Blok else jalan kalau loop selesai tanpa break. Ini berguna untuk pencarian:
for name in ["ana", "budi", "citra"]:
if name.startswith("b"):
print("found", name)
break
else:
print("not found")
Kalau budi ada di list, hasilnya found budi; kalau tidak ada, not found.
Satu detail JavaScript yang perlu diketahui: “There is no way to stop or break a forEach() loop other than by throwing an exception.” forEach tidak bisa dihentikan kecuali dengan melempar exception. Kalau mungkin perlu berhenti lebih awal, pakai for...of dengan break, atau method seperti find dan some yang berhenti sendiri.
Error off-by-one
Error off-by-one adalah “a logic error that involves a number that differs from its intended value by 1”, kesalahan logika karena sebuah angka meleset satu dari yang dimaksud. Loop adalah habitat alaminya: < atau <=, mulai dari 0 atau 1, ujungnya ikut atau tidak.
items = ["a", "b", "c"]
for i in range(len(items) + 1):
print(items[i])
a
b
c
IndexError: list index out of range
Cara termudah menghindari sebagian besar kesalahan ini adalah tidak mengurus indeks sama sekali: telusuri item-nya langsung, dan pakai enumerate atau range(len(...)) hanya kalau posisinya memang dibutuhkan.
Rekursi: fungsi yang memanggil dirinya sendiri
Rekursi adalah “a method of solving a computational problem where the solution depends on solutions to smaller instances of the same problem”: cara menyelesaikan masalah dengan menyelesaikan versi lebih kecil dari masalah yang sama. Setiap fungsi rekursif butuh dua bagian:
- Base case, yang “specifies input values for which the function can provide a result directly, without any further recursion”: kasus yang bisa langsung dijawab tanpa rekursi lagi.
- Kasus rekursif, yang mengerjakan satu potongan lalu memanggil fungsi itu untuk sisanya.
def total(items):
if not items: # base case: list kosong jumlahnya 0
return 0
return items[0] + total(items[1:]) # item pertama + total sisanya
print(total([12, 5, 30])) # 47
Untuk list datar, loop lebih sederhana. Rekursi bersinar saat datanya sendiri bersarang, seperti folder di dalam folder, komentar dengan balasan, atau JSON di dalam JSON:
def count_files(node):
if isinstance(node, str): # sebuah file
return 1
return sum(count_files(child) for child in node) # sebuah folder
tree = ["a.txt", ["b.txt", "c.txt", ["d.txt"]], "e.txt"]
print(count_files(tree)) # 5
Kalau ditulis dengan loop, kita harus menyimpan sendiri daftar folder yang belum dikunjungi. Versi rekursif cukup mengikuti bentuk datanya.
Saat rekursi salah: stack habis
Setiap pemanggilan fungsi memakai sedikit ruang di call stack (stack dari bagian 3). Rekursi tanpa base case yang benar akan terus memanggil sampai ruangnya habis. “Base cases are essential because they prevent infinite regress”: base case wajib ada supaya tidak berulang tanpa akhir.
def forever(n):
return forever(n + 1)
RecursionError: maximum recursion depth exceeded
Python memunculkan RecursionError “when the interpreter detects that the maximum recursion depth (see sys.getrecursionlimit()) is exceeded.” Batas bawaannya di sini 1000. JavaScript punya jaring pengaman serupa:
RangeError: Maximum call stack size exceeded
PHP tidak punya error rekursi yang ramah. Manualnya mengingatkan bahwa “Recursive function/method calls with over 100-200 recursion levels can smash the stack and cause a termination of the current script”: rekursi lebih dari 100–200 level bisa merusak stack dan menghentikan script. Dalam praktiknya, dengan memory_limit umum 128M, rekursi tanpa akhir berakhir seperti ini:
PHP Fatal error: Allowed memory size of 134217728 bytes exhausted (tried to allocate 2097152 bytes)
Karena itu pula data yang sangat dalam, misalnya list berisi seratus ribu item, lebih baik ditangani dengan loop daripada rekursi.
Biaya tersembunyi: mengerjakan ulang hal yang sama
Ada solusi rekursif yang terlihat elegan tapi sangat lambat, karena menyelesaikan masalah kecil yang sama berulang-ulang. Contoh klasiknya bilangan Fibonacci:
def fib(n):
return n if n < 2 else fib(n - 1) + fib(n - 2)
Untuk menghitung fib(25) dengan cara ini, fungsinya dipanggil 242.785 kali. Solusinya adalah mengingat jawaban yang sudah pernah dihitung, disebut memoization. Python sudah menyediakannya:
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_memo(n):
return n if n < 2 else fib_memo(n - 1) + fib_memo(n - 2)
Hasilnya sama (75025), dengan 26 pemanggilan. Jarak antara 242.785 dan 26 itu adalah cuplikan dari bagian 10 tentang algoritma: cara menyelesaikan masalah bisa jauh lebih berpengaruh daripada secepat apa komputernya.
Loop atau rekursi?
- Pakai loop untuk data datar, menghitung, dan apa pun yang bisa sangat panjang. Biasanya lebih jelas dan tidak pernah menabrak batas stack.
- Pakai rekursi saat data atau masalahnya bersarang: tree, folder, menu, parser. Kodenya jadi mencerminkan strukturnya.
- Apa pun pilihannya, pastikan ia berhenti: kondisi yang pada akhirnya jadi salah, atau base case yang pasti tercapai.
Coba sendiri
- Tulis ulang
totaldengan loopfor. Versi mana yang lebih mudah dibaca? - Ubah contoh
whilesupaya mulai dari 27 lalu hitung langkahnya. Tebak dulu; jumlahnya jauh lebih banyak dari yang Anda kira. - Panggil
fib(30)biasa danfib_memo(30), lalu hitung jumlah pemanggilan masing-masing. - Di JavaScript, coba
breakdari dalamforEach, lalu tulis ulang denganfor...of.
Ringkasan
- Loop mengulang sebuah blok; rekursi menyelesaikan masalah dengan menyelesaikan versi yang lebih kecil.
- Utamakan menelusuri item langsung (
for item in items,for...of,foreach,rangedi Go) daripada mengurus indeks. Di PHP,unset()variabelnya setelahforeachdengan referensi. range(n)berhenti sebelumn. Banyak bug off-by-one ada di ujung-ujung loop.- Setiap loop
whiledan setiap fungsi rekursif butuh jalan berhenti yang pasti. - Rekursi cocok untuk data bersarang; rekursi yang terlalu dalam menabrak batas stack (
RecursionError,RangeError). - Menghitung ulang hal yang sama itu mahal; memoization bisa mengubah ratusan ribu pemanggilan menjadi beberapa puluh.
Referensi
- More Control Flow Tools: for Statements, break and continue, else clauses on loops, tutorial Python.
- Built-in Exceptions: RecursionError, dokumentasi Python.
- Effective Go: For, The Go Programming Language.
- for…of, for…in, dan Array.prototype.forEach(), MDN.
- Recursion (computer science) dan Off-by-one error, Wikipedia.
- foreach dan User-defined functions, PHP Manual.