Rekursi: kasus dasar dan langkah yang mengecil

Fungsi rekursif adalah fungsi yang memanggil dirinya sendiri untuk menyelesaikan versi masalah yang lebih kecil. Setiap fungsi rekursif punya dua bagian. Kasus dasar adalah masukan yang jawabannya langsung diketahui tanpa memanggil apa pun. Langkah rekursif memanggil fungsi yang sama dengan masukan yang lebih dekat ke kasus dasar, lalu memakai hasilnya. Kalau salah satu bagian hilang, fungsi itu tidak pernah selesai.

Rekursi dipakai ketika bentuk datanya sendiri bersarang dan kedalamannya tidak diketahui sebelumnya: folder di dalam folder, komentar yang membalas komentar, menu bertingkat. Perulangan for biasa butuh tahu berapa tingkat yang harus dibuka; rekursi cukup tahu cara membuka satu tingkat dan kapan berhenti.

def pangkat(basis, n):
    if n == 0:          # kasus dasar
        return 1
    return basis * pangkat(basis, n - 1)   # langkah yang mengecil

# pangkat(3, 4) -> 3 * pangkat(3, 3) -> ... -> 3 * 3 * 3 * 3 * 1 = 81

Setiap panggilan yang belum selesai disimpan di tumpukan panggilan bersama variabel lokalnya, lalu menunggu panggilan di bawahnya kembali. Panggilan pangkat(3, 4) menumpuk lima bingkai sebelum kasus dasar tercapai, lalu hasilnya dikalikan saat tumpukan dilepas satu per satu. Python membatasi kedalaman tumpukan ini; batasnya dapat dibaca dengan sys.getrecursionlimit(). Rekursi yang melewatinya berhenti dengan RecursionError: maximum recursion depth exceeded.