DSA Interview Prep · Pelajaran

Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan

Gunakan kaedah tiga langkah untuk menulis penyelesaian rekursif yang betul bagi faktorial, kuasa dan jumlah digit tanpa menjejaki setiap panggilan.

Pelajaran 1 daripada 413 langkah

Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan ialah pelajaran DSA Interview Prep percuma di CoddyKit. Ini ialah pelajaran 1 daripada 4. Sebanyak 3 pelajaran dalam laluan pembelajaran ini boleh dibaca sepenuhnya secara percuma — selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan praktikal dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran DSA Interview Prep, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Mengapa Rekursi Terasa Sukar

Kebanyakan pemula cuba menjejaki setiap panggilan rekursif secara mental, yang dengan cepat menjadi sukar dikendalikan walaupun untuk rekursi sedalam lima aras. Pendekatan profesional ialah menggunakan kerangka tiga langkah — Kes Asas, Kepercayaan, Pembinaan — yang membolehkan anda menulis fungsi rekursif yang betul tanpa mensimulasikan keseluruhan pepohon panggilan secara mental.

Kerangka ini kadangkala dipanggil lompatan kepercayaan: anda mempercayai bahawa fungsi anda berfungsi pada masukan yang lebih kecil, lalu menggunakan andaian itu untuk membina penyelesaian bagi masukan yang lebih besar.

Langkah 1: Takrifkan Kes Asas

kes asas ialah masukan paling mudah yang jawapannya diketahui tanpa rekursi selanjutnya. Setiap fungsi rekursif mesti mempunyai sekurang-kurangnya satu kes asas; tanpanya fungsi akan berulang selama-lamanya (limpahan tindanan). Kes asas yang baik ialah: senarai kosong, satu unsur, n == 0, n == 1, atau masalah itu mengecil menjadi identiti remeh.

Tuliskan kes asas dahulu, sebelum sebarang logik rekursif. Kenal pastinya dengan bertanya: 'Apakah versi paling kecil bagi masalah ini yang boleh saya jawab serta-merta?'

# 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 kepercayaan ialah lompatan keyakinan: anggap fungsi anda sudah berfungsi dengan betul untuk sebarang masukan yang lebih kecil sepenuhnya daripada masukan semasa. Anda tidak perlu membuktikannya untuk setiap masukan yang lebih kecil sekarang — bukti induktif menjaminnya. Panggil sahaja fungsi anda pada submasalah yang lebih kecil dan percayai fungsi itu mengembalikan hasil yang betul.

Inilah langkah yang sering dilangkau oleh pemula; sebaliknya, mereka cuba mensimulasikannya secara mental. Tahan dorongan itu; pendekatan ini boleh digunakan untuk rekursi sedalam mana-mana selepas anda menghayati rangka kerja ini.

# 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: Bina Penyelesaian

Langkah pembinaan menggabungkan hasil submasalah yang dipercayai dengan sumbangan unsur semasa untuk menghasilkan jawapan bagi keseluruhan masukan. Biasanya, langkah ini hanya memerlukan satu baris: gunakan operasi pada unsur semasa dan hasil panggilan rekursif. Pembinaan lazim: tambahkan pada jumlah, letakkan di hadapan senarai, tambah nilai kiraan, atau gabungkan 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 Rangka Kerja pada Jumlah Digit

Masalah: kira jumlah digit bagi integer bukan negatif. Kes asas: n == 0 → jumlahnya ialah 0 (atau n < 10 → n itu sendiri). Kepercayaan: sumDigits(n // 10) mengembalikan jumlah semua digit kecuali digit terakhir. Pembinaan: tambahkan digit terakhir n % 10 pada hasil yang dipercayai. Rangka kerja ini menghasilkan penyelesaian 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 rangka kerja ini: kes asasnya ialah fib(0) = 0 dan fib(1) = 1. Kepercayaan: kedua-dua panggilan yang lebih kecil mengembalikan nilai Fibonacci yang betul. Pembinaan: kembalikan jumlah kedua-duanya. Pelaksanaan naif ini mempunyai kerumitan O(2^n) — kita akan membaikinya dalam pelajaran memoisation.

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

Balikkan Rentetan Secara Rekursif

Masalah: balikkan rentetan secara rekursif. Kes asas: rentetan kosong atau satu aksara — sudah pun terbalik. Kepercayaan: reverse(s[1:]) mengembalikan balikan semua aksara selepas aksara pertama. Pembinaan: tambahkan aksara pertama pada hujung akhiran yang telah diterbalikkan. Rangka kerja ini menghasilkan penyelesaian 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'

Mengira Kemunculan Secara Rekursif

Masalah: kira bilangan kemunculan nilai sasaran dalam senarai secara rekursif. Kes asas: senarai kosong — bilangannya ialah 0. Kepercayaan: count(lst[1:], target) mengembalikan bilangan kemunculan dalam ekor senarai. Pembinaan: tambahkan 1 jika unsur pertama sepadan dengan sasaran, atau tambahkan 0 jika tidak. Setiap langkah rekursif bergerak ke arah kes asas dengan mengurangkan saiz senarai 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

Semak Sama Ada Senarai Diisih

Masalah: semak sama ada senarai diisih mengikut tertib menaik secara rekursif. Kes asas: senarai yang mempunyai 0 atau 1 unsur sentiasa diisih. Kepercayaan: is_sorted(lst[1:]) memberitahu anda sama ada ekor senarai telah diisih. Pembinaan: senarai itu diisih jika unsur pertama <= unsur kedua DAN ekornya telah diisih. Ini ialah contoh jelas yang menggunakan operasi logik AND bagi dua syarat dalam langkah pembinaan.

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

Carian Binari Secara Rekursif (Diulang Kaji)

Carian binari yang dinyatakan secara rekursif melalui rangka kerja ini: kes asas: lo > hi → tidak ditemui (kembalikan -1). Kepercayaan: panggilan rekursif pada bahagian yang betul akan menemui sasaran atau mengembalikan -1. Pembinaan: kira mid, buat perbandingan, kemudian panggil bahagian yang sesuai. Bentuk rekursif ini menunjukkan struktur bahagi dan takluk dengan jelas, walaupun bentuk beriterasi lebih disukai dalam pengeluaran kerana 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

Bila Perlu Menggunakan Rekursi berbanding Iterasi

Rekursi sangat sesuai apabila masalah terurai secara semula jadi kepada submasalah yang lebih kecil tetapi daripada jenis yang sama (pepohon, bahagi dan takluk, penjejakan balik). Iterasi lebih disukai apabila: kedalaman rekursi besar (berisiko menyebabkan limpahan tindanan dalam Python, yang lalainya ialah ~1000), versi rekursif dan beriterasi sama jelas, atau masalah itu hanyalah gelung mudah (factorial, Fibonacci tanpa memoisation).

Petua umum yang baik: jika melukis pepohon rekursi terasa semula jadi, gunakan rekursi. Jika pepohon itu hanya garis lurus (rekursi ekor), tukarkannya kepada 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

Semakan Pantas

Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.

Jawab dalam pelajaran interaktif

Rumusan Pelajaran

Dalam pelajaran ini, anda telah mempelajari: rangka kerja tiga langkah ialah Kes Asas (jawapan paling mudah yang diketahui), Kepercayaan (anggap submasalah telah diselesaikan), dan Pembinaan (gabungkan unsur semasa dengan hasil yang dipercayai), tuliskan kes asas dahulu dan elakkan menjejaki keseluruhan pepohon panggilan secara mental, serta gunakan iterasi apabila kedalaman rekursi berisiko menyebabkan limpahan tindanan atau apabila bentuk rekursif dan beriterasi sama jelas. Seterusnya, kita akan memvisualisasikan tindanan panggilan dengan lebih terperinci.

Percuma untuk bermula

Pelajari Python dengan tutor kecerdasan buatan — percuma

Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.

Kursus: 30
Pelajaran: 120

Mula belajar secara percuma Lihat kursus penuh

Soalan Lazim

Adakah pelajaran “Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan” percuma?

Ya — sebanyak 3 pelajaran dalam laluan pembelajaran DSA Interview Prep, termasuk “Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan”, boleh dibaca sepenuhnya secara percuma di web ini. Selepas itu, CoddyKit PRO membuka akses kepada semua pelajaran, serta latihan interaktif dengan penyunting kod terbina dalam dan tutor kecerdasan buatan yang tersedia 24/7. Kursus DSA Interview Prep merangkumi sejumlah 4 pelajaran.

Apakah yang akan saya pelajari dalam “Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan”?

Gunakan kaedah tiga langkah untuk menulis penyelesaian rekursif yang betul bagi faktorial, kuasa dan jumlah digit tanpa menjejaki setiap panggilan. Anda berlatih DSA Interview Prep menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.

Adakah saya memerlukan pengalaman untuk memulakan DSA Interview Prep?

Tiada pengalaman terdahulu diperlukan. Pembelajaran DSA Interview Prep di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 1 daripada 4.

Berapa lamakah pelajaran “Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan” diambil?

Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.

Bolehkah saya menulis dan menjalankan kod dalam pelajaran DSA Interview Prep ini?

Ya. Setiap pelajaran DSA Interview Prep menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.

Semua pelajaran dalam kursus ini

Rangka Kerja Rekursi: Kes Asas, Kepercayaan, Binaan
Menggambarkan Tindanan Panggilan
Pertukaran Rekursif dan Lelaran
Memoisasi: Menyimpan Keputusan Rekursif

← Kembali ke DSA Interview Prep