Pengantar rekursi

Rekursi adalah teknik ketika sebuah fungsi memanggil dirinya sendiri. Rekursi cocok untuk masalah yang bisa dipecah menjadi versi lebih kecil dari masalah yang sama.

Contoh klasiknya faktorial: 5! = 5 × 4!, dan 4! = 4 × 3!, dan seterusnya sampai 1! = 1.

1def faktorial(n):2    if n <= 1:3        return 14    return n * faktorial(n - 1)56print(faktorial(5))7print(faktorial(10))

120
3628800

Setiap fungsi rekursif punya dua bagian:

1. 1Kasus dasar: kondisi berhenti yang langsung mengembalikan jawaban, di sini n <= 1.
2. 2Kasus rekursif: memanggil dirinya sendiri dengan masalah yang lebih kecil, di sini faktorial(n - 1).

Menelusuri panggilan

Panggilan-panggilan itu ditumpuk di memori yang disebut call stack. Setelah kasus dasar tercapai, jawabannya dikembalikan satu per satu dari bawah ke atas.

Contoh lain: jumlah digit

1def jumlah_digit(n):2    if n < 10:3        return n4    return n % 10 + jumlah_digit(n // 10)56print(jumlah_digit(2026))

10

2026 dipecah menjadi digit terakhir (6) ditambah jumlah digit dari 202. Prosesnya berulang sampai tersisa satu digit.

Rekursi tidak selalu efisien

Bilangan Fibonacci (0, 1, 1, 2, 3, 5, 8, ...) bisa ditulis secara rekursif, tetapi versi sederhananya menghitung nilai yang sama berulang-ulang:

1panggilan = 023def fib(n):4    global panggilan5    panggilan += 16    if n < 2:7        return n8    return fib(n - 1) + fib(n - 2)910print(fib(20), "dengan", panggilan, "panggilan fungsi")

6765 dengan 21891 panggilan fungsi

Lebih dari dua puluh ribu panggilan hanya untuk fib(20)! Versi dengan perulangan biasa cukup 20 langkah. Teknik untuk mengatasi masalah ini, yaitu menyimpan hasil yang sudah dihitung, dipelajari di kursus Desain dan Analisis Algoritma.

1def palindrom(kata):2    if len(kata) <= 1:3        return True4    if kata[0] != kata[-1]:5        return False6    return palindrom(kata[1:-1])78for k in ["katak", "kasur", "malam", "a"]:9    print(k, palindrom(k))

katak True
kasur False
malam True
a True