Recursion
หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
ฟังก์ชันที่เรียกตัวเอง
- รีเคอร์ชัน คือเมื่อฟังก์ชัน เรียก ตัวมันเอง
- Each call should work on a smaller version of the problem
- ทำอย่างถูกต้อง ปัญหาจะหดจนแก้ได้ง่าย
กรณีฐานและกรณีรีเคอร์ชัน
- The base case is the simplest case — it stops the recursion.
- กรณีรีเคอร์ชัน เรียกฟังก์ชันอีกครั้งบนอินพุตที่เล็กลง
- หากไม่มีกรณีพื้นฐาน ฟังก์ชันจะไม่หยุด (เกิดข้อผิดพลาด)
English
def countdown(n):
if n == 0:
print("Go!")
return
print(n)
countdown(n - 1)
countdown(3)
A worked example: factorial
- ตัวคูณ
n!มีค่าเท่ากับn × (n-1) × ... × 1 - ในรูปแบบรีเคอร์ชัน:
n! = n × (n-1)!, และกรณีฐานคือ0! = 1 - Each call multiplies
nby the factorial of one less.
English
def factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
print(factorial(4))
คอมพิวเตอร์รันอย่างไร
- แต่ละการเรียกจะถูกหยุดไว้บน Stack of Call ระหว่างรอการเรียกภายใน
- เมื่อกรณีฐานคืนค่า การเรียกที่ถูกหยุดจะเสร็จสิ้นทีละตัว
- การเรียกมากเกินไปทำให้ Stack Overload — Python จะยกขึ้น
RecursionError
In Cambridge pseudocode
- ฟังก์ชันรีเคอร์ชันตั้งชื่อกรณีฐานและกรณีรีเคอร์ชันอย่างชัดเจน
FUNCTION Factorial(n : INTEGER) RETURNS INTEGER
IF n = 0 THEN
RETURN 1 // base case
ELSE
RETURN n * Factorial(n - 1) // recursive case
ENDIF
ENDFUNCTION
ข้อผิดพลาดที่พบบ่อย
- Every recursion needs a base case, or it overflows the call stack.
- Each call must move closer to the base case.
ลองดูเลย
- Give each function a base case and a recursive case.
- กด Check answer เพื่อทดสอบโค้ดของคุณ
สำรวจ
Recursion กลับมาจากรากใบ (leaves)
แต่ละ call แยกย่อยเป็น call เล็กกว่า; คำตอบ ส่งกลับมา จากกรณีฐาน (base cases)
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน recursive sum_to(n) ที่ return 1 + 2 + ... + n. กรณีฐานคือ sum_to(0) ซึ่งเท่ากับ 0
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน recursive power(base, exp) ที่ return base ยกกำลัง exp กรณีฐานคือ exp == 0 ซึ่งให้ผลเป็น 1
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เขียน recursive count_up(n) ที่ return list [1, 2, ..., n]. กรณีฐานคือ count_up(0) ซึ่งเป็น list ว่าง []
คลิก Run เพื่อดูผลลัพธ์ที่นี่