Rekursi adalah ketika sebuah fungsi memanggil dirinya sendiri untuk menyelesaikan versi lebih kecil dari masalah yang sama. Setiap rekursi membutuhkan kasus dasar yang menghentikannya dan kasus rekursif yang bergerak menuju dasar.
Pecah masalah menjadi submasalah yang lebih kecil dan identik. Setiap pemanggilan mendorong bingkai ke call stack; pengembalian mengeluarkannya.
def factorial(n):
if n <= 1: # base case: stop recursing
return 1
return n * factorial(n - 1) # recursive case: smaller problem
factorial(4) # 4 * 3 * 2 * 1 -> 24
factorial(4)
= 4 * factorial(3)
= 4 * (3 * factorial(2))
= 4 * (3 * (2 * factorial(1)))
= 4 * 3 * 2 * 1 = 24
Di sini O(n) waktu dan O(n) ruang stack (satu bingkai per pemanggilan).
Rekursi mengekspresikan secara alami masalah yang serupa dengan diri sendiri — pohon, grafik, bagi dan taklukkan — jauh lebih bersih daripada loop.
Ini adalah model mental di balik merge sort, backtracking, dan pemrograman dinamis.
Memahami call stack juga membuat Anda lebih baik dalam debugging dan penalaran tentang memori.
Perpustakaan pertanyaan wawancara IT dengan jawaban mendetail — dari Junior hingga Senior.
Donasi