0Pricing
DSA Interview Prep · Pelajaran

Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan

Terapkan metode tiga langkah untuk menulis solusi rekursif yang benar bagi faktorial, perpangkatan, dan jumlah digit tanpa menelusuri setiap pemanggilan.

Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan adalah pelajaran DSA Interview Prep gratis di CoddyKit. Ini adalah pelajaran 1 dari 4. Kamu bisa membaca pelajaran lengkapnya di bawah secara gratis — lalu praktikkan langsung di browser dengan editor kode bawaan dan tutor AI 24/7. Ini adalah bagian dari jalur belajar DSA Interview Prep, dan progresmu tersinkronisasi di web dan aplikasi CoddyKit. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Mengapa Rekursi Terasa Sulit

Sebagian besar pemula mencoba menelusuri setiap pemanggilan rekursif dalam pikiran, yang segera terasa membebani bahkan untuk rekursi sedalam lima tingkat. Pendekatan profesional adalah menggunakan kerangka tiga langkah — Kasus Dasar, Kepercayaan, Pembangunan — yang memungkinkan Anda menulis fungsi rekursif yang benar tanpa mensimulasikan seluruh pohon pemanggilan dalam pikiran.

Kerangka ini terkadang disebut lompatan keyakinan: Anda mempercayai bahwa fungsi Anda bekerja pada masukan yang lebih kecil dan menggunakan asumsi itu untuk membangun solusi bagi masukan yang lebih besar.

Langkah 1: Tentukan Kasus Dasar

Kasus dasar adalah masukan paling sederhana yang jawabannya sudah diketahui tanpa rekursi lebih lanjut. Setiap fungsi rekursif harus memiliki setidaknya satu kasus dasar; tanpa kasus dasar, fungsi akan terus melakukan rekursi selamanya (luapan tumpukan). Kasus dasar yang baik meliputi: daftar kosong, satu elemen, n == 0, n == 1, atau masalah yang dapat direduksi menjadi identitas trivial.

Tuliskan kasus dasar terlebih dahulu, sebelum logika rekursif apa pun. Kenali kasus tersebut dengan bertanya: 'Apa versi terkecil dari masalah ini yang dapat langsung saya jawab?'

# Base cases for common problems
def factorial(n):
    if n == 0:          # base case: 0! = 1
        return 1
    # ... recursive step below

def sum_list(lst):
    if not lst:         # base case: sum of empty list is 0
        return 0
    # ...

def height(node):
    if node is None:    # base case: height of null node is 0
        return 0
    # ...

print('Base cases identified')

Langkah 2: Percayai Panggilan Rekursif

Langkah memercayai adalah lompatan keyakinan: anggap fungsi Anda sudah bekerja dengan benar untuk masukan apa pun yang ukurannya benar-benar lebih kecil daripada masukan saat ini. Anda tidak perlu membuktikannya untuk setiap masukan yang lebih kecil sekarang—pembuktian induktif menjaminnya. Cukup panggil fungsi Anda pada submasalah yang lebih kecil dan percayai bahwa fungsi tersebut mengembalikan hasil yang benar.

Inilah langkah yang sering dilewati pemula karena mereka mencoba menyimulasikannya secara mental. Tahan dorongan itu; pendekatan ini dapat diterapkan pada rekursi sedalam apa pun setelah Anda memahami kerangkanya.

# Trust example: sum_list([3, 1, 4, 1, 5])
# Trust: sum_list([1, 4, 1, 5]) = 11  (we TRUST this, don't trace it)
# Build: 3 + 11 = 14

# So:
def sum_list(lst):
    if not lst:
        return 0
    # Trust that sum_list(lst[1:]) returns sum of the rest
    return lst[0] + sum_list(lst[1:])

print(sum_list([3, 1, 4, 1, 5]))  # 14

Langkah 3: Bangun Solusinya

Langkah membangun menggabungkan hasil submasalah yang telah dipercayai dengan kontribusi elemen saat ini untuk menghasilkan jawaban bagi seluruh masukan. Biasanya langkah ini hanya terdiri dari satu baris: terapkan operasi pada elemen saat ini dan hasil dari panggilan rekursif. Contoh pembangunan yang umum: menambahkan ke jumlah, menambahkan di awal daftar, menambah hitungan, atau menggabungkan dua hasil submasalah.

def factorial(n):
    if n == 0:
        return 1
    # Trust: factorial(n-1) gives (n-1)!
    # Build: n * (n-1)! = n!
    return n * factorial(n - 1)

def power(base, exp):
    if exp == 0:
        return 1
    # Trust: power(base, exp-1) gives base^(exp-1)
    # Build: base * base^(exp-1) = base^exp
    return base * power(base, exp - 1)

print(factorial(6))    # 720
print(power(2, 10))    # 1024

Menerapkan Kerangka Kerja pada Jumlah Digit

Masalah: hitung jumlah digit bilangan bulat non-negatif. Kasus dasar: n == 0 → jumlahnya 0 (atau n < 10 → n itu sendiri). Kepercayaan: sumDigits(n // 10) mengembalikan jumlah semua digit kecuali digit terakhir. Pembangunan: tambahkan digit terakhir n % 10 ke hasil yang telah dipercayai. Kerangka kerja ini menghasilkan solusi dalam tiga langkah deklaratif.

def sumDigits(n):
    if n < 10:
        return n            # base case: single digit
    # Trust: sumDigits(n // 10) gives sum of all digits except last
    # Build: add the last digit
    return n % 10 + sumDigits(n // 10)

print(sumDigits(0))      # 0
print(sumDigits(7))      # 7
print(sumDigits(123))    # 6
print(sumDigits(9999))   # 36

Fibonacci: Dua Submasalah

Fibonacci memerlukan dua panggilan rekursif: fib(n-1) dan fib(n-2). Terapkan kerangka kerja tersebut: kasus dasarnya adalah fib(0) = 0 dan fib(1) = 1. Kepercayaan: kedua panggilan yang lebih kecil mengembalikan nilai Fibonacci yang benar. Pembangunan: kembalikan jumlah keduanya. Implementasi naif ini memiliki waktu O(2^n)—kita akan memperbaikinya dalam pelajaran memoisisasi.

def fib(n):
    if n <= 1:
        return n      # base cases: fib(0)=0, fib(1)=1
    # Trust both smaller sub-problems
    return fib(n - 1) + fib(n - 2)

for i in range(8):
    print(f'fib({i}) = {fib(i)}')  # 0,1,1,2,3,5,8,13

Membalik String secara Rekursif

Masalah: balik sebuah string secara rekursif. Kasus dasar: string kosong atau satu karakter—sudah terbalik. Kepercayaan: reverse(s[1:]) mengembalikan pembalikan semua karakter setelah karakter pertama. Pembangunan: gunakan append untuk menambahkan karakter pertama di akhir sufiks yang telah dibalik. Kerangka kerja ini menghasilkan solusi tiga baris.

def reverse_str(s):
    if len(s) <= 1:
        return s            # base case
    # Trust: reverse_str(s[1:]) = reverse of 'ello' for 'hello'
    # Build: append first character at end
    return reverse_str(s[1:]) + s[0]

print(reverse_str(''))        # ''
print(reverse_str('a'))       # 'a'
print(reverse_str('hello'))   # 'olleh'
print(reverse_str('racecar')) # 'racecar'

Menghitung Kemunculan secara Rekursif

Masalah: hitung kemunculan suatu nilai target dalam daftar secara rekursif. Kasus dasar: daftar kosong—hitungannya 0. Kepercayaan: count(lst[1:], target) mengembalikan hitungan pada bagian ekor. Pembangunan: tambahkan 1 jika elemen pertama cocok dengan target, atau tambahkan 0 jika tidak. Setiap langkah rekursif bergerak menuju kasus dasar dengan mengurangi ukuran daftar sebanyak 1.

def count_occurrences(lst, target):
    if not lst:
        return 0
    # Trust: count in rest of list is handled recursively
    # Build: add 1 if first element matches, else 0
    return (1 if lst[0] == target else 0) + count_occurrences(lst[1:], target)

print(count_occurrences([1, 2, 3, 2, 4, 2], 2))  # 3
print(count_occurrences([], 5))                    # 0
print(count_occurrences([7, 7, 7], 7))             # 3

Memeriksa Apakah Daftar Terurut

Masalah: periksa apakah sebuah daftar terurut menaik secara rekursif. Kasus dasar: daftar dengan 0 atau 1 elemen selalu terurut. Kepercayaan: is_sorted(lst[1:]) memberi tahu Anda apakah bagian ekornya terurut. Pembangunan: daftar terurut jika elemen pertama <= elemen kedua DAN bagian ekornya terurut. Ini adalah contoh jelas ketika langkah pembangunan menggunakan AND logis dari dua kondisi.

def is_sorted(lst):
    if len(lst) <= 1:
        return True
    # Trust: is_sorted(lst[1:]) tells us if tail is sorted
    # Build: head <= second element AND tail is sorted
    return lst[0] <= lst[1] and is_sorted(lst[1:])

print(is_sorted([]))           # True
print(is_sorted([1]))          # True
print(is_sorted([1, 2, 3, 4])) # True
print(is_sorted([1, 3, 2, 4])) # False

Pencarian Biner secara Rekursif (Ditinjau Ulang)

Pencarian biner yang dinyatakan secara rekursif melalui kerangka kerja: kasus dasar: lo > hi → tidak ditemukan (kembalikan -1). Kepercayaan: panggilan rekursif pada bagian yang tepat menemukan target atau mengembalikan -1. Pembangunan: hitung mid, lakukan perbandingan, lalu panggil bagian yang sesuai. Bentuk rekursif ini memperlihatkan struktur bagi-dan-taklukkan dengan jelas, meskipun dalam produksi bentuk iteratif lebih disukai karena menggunakan ruang O(1).

def binary_search(arr, target, lo, hi):
    if lo > hi:          # base case: search space exhausted
        return -1
    mid = lo + (hi - lo) // 2
    if arr[mid] == target:
        return mid
    # Trust both halves return correct results
    if arr[mid] < target:
        return binary_search(arr, target, mid + 1, hi)
    else:
        return binary_search(arr, target, lo, mid - 1)

arr = [1, 3, 5, 7, 9, 11]
print(binary_search(arr, 7, 0, len(arr) - 1))   # 3
print(binary_search(arr, 4, 0, len(arr) - 1))   # -1

Kapan Menggunakan Rekursi atau Iterasi

Rekursi sangat baik digunakan ketika masalah secara alami dapat diuraikan menjadi submasalah yang lebih kecil dengan jenis yang sama (pohon, bagi-dan-taklukkan, penelusuran balik). Iterasi lebih disukai ketika: kedalaman rekursinya besar (berisiko menyebabkan luapan tumpukan dalam Python, yang secara bawaan memiliki batas sekitar 1000), versi rekursif dan iteratif sama-sama jelas, atau masalahnya adalah perulangan sederhana (factorial, Fibonacci tanpa memoisisasi).

Aturan praktis yang baik: jika menggambar pohon rekursi terasa alami, gunakan rekursi. Jika pohonnya berupa garis lurus (rekursi ekor), ubah menjadi iterasi.

import sys

# Python's default recursion limit
print('Recursion limit:', sys.getrecursionlimit())  # 1000

# A list of 2000 elements would overflow the recursive sum_list
# Use iteration for safety:
def sum_list_iter(lst):
    total = 0
    for x in lst:
        total += x
    return total

big = list(range(2000))
print(sum_list_iter(big))  # 1999000 — no stack overflow

Pemeriksaan Singkat

Uji pemahaman Anda tentang konsep Struktur Data & Algoritme — Persiapan Wawancara Pemrograman dari pelajaran ini.

Rangkuman Pelajaran

Dalam pelajaran ini Anda mempelajari: kerangka kerja tiga langkah terdiri dari Kasus Dasar (jawaban sederhana yang diketahui), Kepercayaan (anggap submasalah sudah terselesaikan), dan Pembangunan (gabungkan elemen saat ini dengan hasil yang telah dipercayai), tuliskan kasus dasar terlebih dahulu dan hindari menelusuri seluruh pohon panggilan secara mental, serta gunakan iterasi ketika kedalaman rekursi berisiko menyebabkan luapan tumpukan atau ketika bentuk rekursif dan iteratif sama-sama jelas. Selanjutnya kita akan memvisualisasikan tumpukan panggilan secara mendetail.

Pertanyaan yang Sering Diajukan

Apakah pelajaran “Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan” gratis?

Ya — teks lengkap “Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan” gratis dibaca di sini di web. Untuk praktiknya secara interaktif (editor kode bawaan dan tutor AI 24/7) dan buka sisa kursus DSA Interview Prep, upgrade ke CoddyKit PRO. Kursus DSA Interview Prep mencakup 4 pelajaran total.

Apa yang akan aku pelajari di “Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan”?

Terapkan metode tiga langkah untuk menulis solusi rekursif yang benar bagi faktorial, perpangkatan, dan jumlah digit tanpa menelusuri setiap pemanggilan. Kamu berlatih DSA Interview Prep dengan kode praktik yang langsung kamu jalankan di browser, dan tutor AI 24/7 menjawab pertanyaanmu saat kamu mengerjakan pelajaran ini.

Apakah aku perlu pengalaman untuk memulai DSA Interview Prep?

Tidak diperlukan pengalaman sebelumnya. DSA Interview Prep di CoddyKit dirancang untuk pemula hingga pelajar tingkat lanjut, jadi kamu bisa memulai di sini atau dari awal dan belajar sesuai kecepatan kamu sendiri. Ini adalah pelajaran 1 dari 4.

Berapa lama pelajaran “Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan” memakan waktu?

Sebagian besar pelajaran CoddyKit memakan waktu sekitar 5–10 menit. Setiap pelajaran ringkas dan interaktif, jadi kamu membuat kemajuan stabil dan melanjutkan dari tempat kamu tinggalkan di web dan aplikasi.

Bisakah aku menulis dan menjalankan kode dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan editor kode bawaan, jadi kamu menulis dan menjalankan kode nyata langsung di browser dan mendapatkan umpan balik AI instan — tidak diperlukan penyiapan lokal.

Semua pelajaran dalam kursus ini

  1. Kerangka Rekursi: Kasus Dasar, Kepercayaan, Pembangunan
  2. Memvisualisasikan Tumpukan Pemanggilan
  3. Pertukaran Rekursif dan Iteratif
  4. Memoization: Menyimpan Hasil Rekursif
← Kembali ke DSA Interview Prep