กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง
ใช้วิธีสามขั้นตอนเขียนคำตอบแบบเรียกซ้ำที่ถูกต้องสำหรับแฟกทอเรียล การยกกำลัง และผลรวมหลักตัวเลข โดยไม่ต้องติดตามทุกการเรียก
กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง เป็นบทเรียน Coding Interview Prep ฟรีบน CoddyKit นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน คุณสามารถอ่านบทเรียนทั้งหมดด้านล่างฟรี — จากนั้นลองปฏิบัติด้วยตัวคุณเองในเบราว์เซอร์พร้อมตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7 บทเรียนนี้เป็นส่วนหนึ่งของเส้นทางการเรียน Coding Interview Prep และความก้าวหน้าของคุณจะซิงค์ข้ามเว็บและแอป CoddyKit คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
เหตุใดการเรียกซ้ำจึงรู้สึกว่ายาก
ผู้เริ่มต้นส่วนใหญ่มักพยายามติดตามการเรียกฟังก์ชันแบบเรียกซ้ำทุกครั้งในใจ ซึ่งจะทำให้สับสนอย่างรวดเร็ว แม้การเรียกซ้ำจะมีความลึกเพียงห้าระดับ แนวทางแบบมืออาชีพคือใช้ กรอบการทำงานสามขั้นตอน ได้แก่ กรณีฐาน ความไว้วางใจ และการสร้างคำตอบ ซึ่งช่วยให้คุณเขียนฟังก์ชันแบบเรียกซ้ำที่ถูกต้องได้โดยไม่ต้องจำลองต้นไม้การเรียกทั้งหมดในใจ
กรอบการทำงานนี้บางครั้งเรียกว่า การก้าวกระโดดด้วยศรัทธา: คุณเชื่อมั่นว่าฟังก์ชันทำงานได้กับข้อมูลนำเข้าที่เล็กลง และใช้ข้อสมมตินั้นสร้างคำตอบสำหรับข้อมูลนำเข้าที่ใหญ่ขึ้น
ขั้นตอนที่ 1: กำหนดกรณีฐาน
กรณีฐานคือข้อมูลเข้าที่ง่ายที่สุดซึ่งทราบคำตอบได้โดยไม่ต้องเรียกซ้ำต่อ ฟังก์ชันแบบเรียกซ้ำทุกฟังก์ชันต้องมีกรณีฐานอย่างน้อยหนึ่งกรณี หากไม่มี ฟังก์ชันจะเรียกซ้ำไปเรื่อย ๆ (สแตกโอเวอร์โฟลว์) กรณีฐานที่ดี ได้แก่ รายการว่าง องค์ประกอบเดียว n == 0, n == 1 หรือปัญหาลดรูปลงเป็นเอกลักษณ์ที่แก้ได้ง่าย
เขียนกรณีฐานก่อนตรรกะแบบเรียกซ้ำ ถามเพื่อระบุกรณีฐานว่า “ปัญหานี้ในรูปแบบที่เล็กที่สุดซึ่งฉันตอบได้ทันทีคืออะไร”
# 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')ขั้นตอนที่ 2: เชื่อมั่นในการเรียกซ้ำ
ขั้นตอนเชื่อมั่นคือการก้าวกระโดดด้วยศรัทธา นั่นคือสมมติว่าฟังก์ชันของคุณทำงานได้ถูกต้องอยู่แล้วสำหรับข้อมูลเข้าทุกชุดที่มีขนาดเล็กกว่าชุดปัจจุบันอย่างเคร่งครัด คุณไม่จำเป็นต้องพิสูจน์ตอนนี้ว่าฟังก์ชันทำงานได้กับข้อมูลเข้าที่เล็กกว่าทุกชุด เพราะการพิสูจน์แบบอุปนัยรับรองเรื่องนี้ไว้แล้ว เพียงเรียกฟังก์ชันของคุณกับปัญหาย่อยที่เล็กลง และเชื่อมั่นว่าฟังก์ชันจะส่งคืนผลลัพธ์ที่ถูกต้อง
นี่คือขั้นตอนที่ผู้เริ่มต้นมักข้าม โดยพยายามจำลองการทำงานในใจแทน จงฝืนความอยากนั้น เพราะเมื่อเข้าใจกรอบแนวคิดนี้อย่างถ่องแท้ วิธีนี้จะรองรับการเรียกซ้ำที่ลึกได้โดยไม่จำกัด
# 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ขั้นตอนที่ 3: สร้างคำตอบ
ขั้นตอนสร้างคำตอบรวมผลลัพธ์ของปัญหาย่อยที่เชื่อมั่นแล้วเข้ากับส่วนที่องค์ประกอบปัจจุบันมีส่วนเพิ่ม เพื่อสร้างคำตอบสำหรับข้อมูลเข้าทั้งหมด โดยปกติจะเป็นเพียงบรรทัดเดียว นั่นคือใช้การดำเนินการกับองค์ประกอบปัจจุบันและผลลัพธ์จากการเรียกซ้ำ ตัวอย่างการสร้างคำตอบที่พบบ่อย ได้แก่ เพิ่มลงในผลรวม เติมไว้หน้ารายการ เพิ่มค่าตัวนับ และรวมผลลัพธ์ย่อยสองรายการเข้าด้วยกัน
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การประยุกต์ใช้กรอบแนวคิดกับผลรวมของตัวเลข
ปัญหา: คำนวณผลรวมของตัวเลขในจำนวนเต็มที่ไม่ติดลบ กรณีฐาน: n == 0 → ผลรวมเป็น 0 (หรือ n < 10 → ตัว n เอง) ขั้นตอนเชื่อมั่น: sumDigits(n // 10) ส่งคืนผลรวมของตัวเลขทั้งหมด ยกเว้นตัวสุดท้าย ขั้นตอนสร้างคำตอบ: นำตัวเลขสุดท้าย n % 10 ไปบวกกับผลลัพธ์ที่เชื่อมั่นแล้ว กรอบแนวคิดนี้สร้างคำตอบได้ด้วยสามขั้นตอนเชิงประกาศ
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ฟีโบนักชี: ปัญหาย่อยสองรายการ
ฟีโบนักชีต้องใช้การเรียกซ้ำสองครั้ง ได้แก่ fib(n-1) และ fib(n-2) ใช้กรอบแนวคิดนี้ดังนี้ กรณีฐานคือ fib(0) = 0 และ fib(1) = 1 ขั้นตอนเชื่อมั่นคือการเชื่อว่าการเรียกที่เล็กลงทั้งสองครั้งส่งคืนค่าฟีโบนักชีที่ถูกต้อง ขั้นตอนสร้างคำตอบคือส่งคืนผลรวมของทั้งสองค่า การนำไปใช้งานแบบพื้นฐานนี้ใช้เวลา O(2^n) — เราจะปรับปรุงในบทเรียนการจดจำผลลัพธ์
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กลับลำดับสตริงด้วยการเรียกซ้ำ
ปัญหา: กลับลำดับสตริงด้วยการเรียกซ้ำ กรณีฐาน: สตริงว่างหรืออักขระเดียว ซึ่งกลับลำดับเรียบร้อยแล้ว ขั้นตอนเชื่อมั่น: reverse(s[1:]) ส่งคืนสตริงที่กลับลำดับของทุกอย่างหลังอักขระตัวแรก ขั้นตอนสร้างคำตอบ: ต่ออักขระตัวแรกไว้ท้ายส่วนต่อท้ายที่กลับลำดับแล้ว กรอบแนวคิดนี้ให้คำตอบสามบรรทัด
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'นับจำนวนการปรากฏด้วยการเรียกซ้ำ
ปัญหา: นับจำนวนครั้งที่ค่าเป้าหมายปรากฏในรายการด้วยการเรียกซ้ำ กรณีฐาน: รายการว่าง ซึ่งมีจำนวนเป็น 0 ขั้นตอนเชื่อมั่น: count(lst[1:], target) ส่งคืนจำนวนในส่วนท้ายของรายการ ขั้นตอนสร้างคำตอบ: บวก 1 หากองค์ประกอบตัวแรกตรงกับค่าเป้าหมาย มิฉะนั้นบวก 0 ทุกขั้นตอนแบบเรียกซ้ำจะคืบหน้าเข้าใกล้กรณีฐานด้วยการลดขนาดรายการลง 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ตรวจสอบว่ารายการเรียงลำดับแล้วหรือไม่
ปัญหา: ตรวจสอบว่ารายการเรียงลำดับจากน้อยไปมากด้วยการเรียกซ้ำหรือไม่ กรณีฐาน: รายการที่มีองค์ประกอบ 0 หรือ 1 รายการถือว่าเรียงลำดับแล้วเสมอ ขั้นตอนเชื่อมั่น: is_sorted(lst[1:]) บอกว่าส่วนท้ายของรายการเรียงลำดับแล้วหรือไม่ ขั้นตอนสร้างคำตอบ: รายการจะเรียงลำดับแล้วก็ต่อเมื่อองค์ประกอบตัวแรก <= ตัวที่สอง AND ส่วนท้ายของรายการเรียงลำดับแล้ว นี่เป็นตัวอย่างที่ชัดเจนซึ่งขั้นตอนสร้างคำตอบใช้ AND เชิงตรรกะของเงื่อนไขสองข้อ
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การค้นหาแบบทวิภาคด้วยการเรียกซ้ำ (ทบทวน)
การค้นหาแบบทวิภาคที่เขียนด้วยการเรียกซ้ำตามกรอบแนวคิดนี้มีดังนี้ กรณีฐาน: lo > hi → ไม่พบ (ส่งคืน -1) ขั้นตอนเชื่อมั่น: การเรียกซ้ำกับครึ่งที่ถูกต้องจะพบค่าเป้าหมายหรือส่งคืน -1 ขั้นตอนสร้างคำตอบ: คำนวณ mid เปรียบเทียบค่า และเรียกใช้ครึ่งที่เหมาะสม รูปแบบแบบเรียกซ้ำแสดงโครงสร้างการแบ่งแล้วพิชิตได้อย่างชัดเจน แม้ว่าในระบบใช้งานจริงจะนิยมรูปแบบแบบวนซ้ำมากกว่าเพื่อใช้พื้นที่ 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เมื่อใดควรใช้การเรียกซ้ำเทียบกับการวนซ้ำ
การเรียกซ้ำเหมาะอย่างยิ่งเมื่อปัญหาแบ่งออกตามธรรมชาติเป็นปัญหาย่อยที่มีชนิดเดียวกัน (ต้นไม้ การแบ่งแล้วพิชิต และการย้อนกลับ) ควรใช้การวนซ้ำเมื่อความลึกของการเรียกซ้ำมาก (เสี่ยงต่อสแตกโอเวอร์โฟลว์ในไพธอน ซึ่งมีค่าเริ่มต้นประมาณ 1000) เมื่อรูปแบบแบบเรียกซ้ำและแบบวนซ้ำเข้าใจได้ชัดเจนพอ ๆ กัน หรือเมื่อปัญหาเป็นเพียงลูปง่าย ๆ (factorial, ฟีโบนักชีที่ไม่มีการจดจำผลลัพธ์)
กฎง่าย ๆ ที่ใช้ได้ดีคือ หากการวาดต้นไม้การเรียกซ้ำให้ความรู้สึกเป็นธรรมชาติ ให้ใช้การเรียกซ้ำ หากต้นไม้เป็นเพียงเส้นตรง (การเรียกซ้ำแบบหาง) ให้เปลี่ยนเป็นการวนซ้ำ
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ตรวจสอบความเข้าใจอย่างรวดเร็ว
ทดสอบความเข้าใจแนวคิดโครงสร้างข้อมูลและอัลกอริทึม — การเตรียมตัวสัมภาษณ์การเขียนโปรแกรมจากบทเรียนนี้
ทบทวนบทเรียน
ในบทเรียนนี้ คุณได้เรียนรู้ว่า กรอบแนวคิดสามขั้นตอนคือ กรณีฐาน (คำตอบที่ทราบและง่ายที่สุด) ขั้นตอนเชื่อมั่น (สมมติว่าปัญหาย่อยได้รับการแก้แล้ว) และขั้นตอนสร้างคำตอบ (รวมองค์ประกอบปัจจุบันเข้ากับผลลัพธ์ที่เชื่อมั่นแล้ว), ควรเขียนกรณีฐานก่อนและหลีกเลี่ยงการจำลองต้นไม้การเรียกทั้งหมดในใจ และ ควรใช้การวนซ้ำเมื่อความลึกของการเรียกซ้ำเสี่ยงต่อสแตกโอเวอร์โฟลว์ หรือเมื่อรูปแบบแบบเรียกซ้ำและแบบวนซ้ำเข้าใจได้ชัดเจนพอ ๆ กัน บทถัดไป เราจะเห็นสแตกการเรียกโดยละเอียด
คำถามที่พบบ่อย
บทเรียน “กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง” ฟรีหรือไม่
ใช่ — ข้อความเต็มของ “กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง” ฟรีให้อ่านที่นี่บนเว็บ เพื่อปฏิบัติแบบโต้ตอบ (ตัวแก้ไขโค้ดในตัวและติวเตอร์ AI ตลอด 24/7) และปลดล็อคส่วนที่เหลือของคอร์ส Coding Interview Prep ให้อัปเกรดเป็น CoddyKit PRO คอร์ส Coding Interview Prep มีบทเรียนทั้งหมด 4 บทเรียน
คุณจะเรียนรู้อะไรในบทเรียน “กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง”
ใช้วิธีสามขั้นตอนเขียนคำตอบแบบเรียกซ้ำที่ถูกต้องสำหรับแฟกทอเรียล การยกกำลัง และผลรวมหลักตัวเลข โดยไม่ต้องติดตามทุกการเรียก คุณปฏิบัติ Coding Interview Prep ด้วยโค้ดที่ใช้งานได้จริงที่คุณเรียกใช้โดยตรงในเบราว์เซอร์ และติวเตอร์ AI ตลอด 24/7 ตอบคำถามของคุณขณะที่คุณไปผ่านบทเรียน
คุณต้องมีประสบการณ์ก่อนที่จะเริ่มเรียน Coding Interview Prep หรือไม่
ไม่จำเป็นต้องมีประสบการณ์มาก่อน Coding Interview Prep บน CoddyKit ออกแบบมาสำหรับผู้เริ่มต้นไปจนถึงผู้เรียนขั้นสูง คุณสามารถเริ่มต้นที่นี่หรือเริ่มจากตัวแรกและเรียนด้วยความเร็วของคุณเอง นี่คือบทเรียนที่ 1 จากทั้งหมด 4 บทเรียน
บทเรียน “กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง” ใช้เวลานานแค่ไหน
บทเรียน CoddyKit ส่วนใหญ่ใช้เวลาประมาณ 5–10 นาที แต่ละบทเรียนจึงสั้นและเป็นแบบโต้ตอบ คุณสามารถก้าวหน้าอย่างต่อเนื่องและกลับมาเรียนต่อจากตรงที่เพิ่งหยุดบนเว็บและแอปได้เลย
ฉันเขียนและรันโค้ดในบทเรียน Coding Interview Prep นี้ได้ไหม
ได้ บทเรียน Coding Interview Prep ทุกบทมีตัวแก้ไขโค้ดในตัว คุณจึงเขียนและรันโค้ดจริงได้เลยในเบราว์เซอร์ และได้รับข้อเสนอแนะจาก AI ในทันที — ไม่ต้องติดตั้งในเครื่องของคุณ
บทเรียนทั้งหมดในหลักสูตรนี้
- กรอบการเรียกซ้ำ: กรณีฐาน ความเชื่อมั่น การสร้าง
- การแสดงภาพสแตกการเรียก
- การแลกเปลี่ยนระหว่างแบบเรียกซ้ำกับแบบวนซ้ำ
- การจดจำผลลัพธ์: แคชผลลัพธ์จากการเรียกซ้ำ