Recursion (การเรียกซ้ำ)
Recursion ช่วยแบ่งและแก้ปัญหา แต่ละ recursive call สปินออฟ recursive calls อื่นๆ จุดศูนย์กลางของ recursive function มี 2 กรณี: base cases (บอกให้ recursion หยุด) และ recursive cases (เรียกฟังก์ชันตัวเอง) ปัญหาแบบง่ายที่ใช้ recursive solution โดยธรรมชาติคือการคำนวณ factorial อัลกอริทึม factorial แบบ recursive มี 2 กรณี: base case เมื่อ n=0 และ recursive case เมื่อ n>0
Backtracking (การย้อนกลับ)
Backtracking เป็นอัลกอริทึมทั่วไปสำหรับหาคำตอบปัญหาคำนวณ บางอย่าง สร้างตัวเลือกเพิ่มเติมทีละขั้น และปฏิเสธการประมวลผลต่อหากนำไปสู่คำตอบที่เป็นไปไม่ได้ Backtracking อนุญาตให้ยกเลิกตัวเลือกก่อนหน้าหากพบว่าผิดพลาด
ตัวอย่าง Factorial
def factorial(n):
# base case
if n == 0:
return 1
# calculation และ recursive call
f = n * factorial(n - 1)
print(f)
return f
factorial(4)
โค้ดพิมพ์ 1, 2, 4, 24 การคำนวณ factorial 4 ต้องการ 4 recursive calls บวก initial call
