Recursion: Base case และ Recursive case
A Method that Calls Itself
- Recursion คือเมื่อ method เรียกตัวเอง เพื่อแก้ปัญหาส่วนย่อยของปัญหาเดียวกัน
- ในการสอบ AP CSA คุณต้อง Trace recursion เป็นส่วนใหญ่ (ติดตามการเรียกด้วยมือ) การเขียน recursive methods เล็กๆ ช่วยในการ Trace ได้ดี
- ทุก method แบบ recursive ต้องมีสองส่วน: base case และ recursive case
กรณีฐานและกรณีรีเคอร์ชัน
- Base case: ข้อมูลที่ง่ายที่สุด ซึ่งคุณตอบได้ โดยไม่ต้อง เรียกตัวเอง สิ่งนี้จะหยุด recursion
- Recursive case: คุณเรียก method เดิมด้วยข้อมูลที่ เล็กลง จากนั้นสร้างคำตอบ
- หากไม่มี base case, method จะเรียกตัวเองซ้ำๆตลอดจนพัง (a stack overflow)
Example: Factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - กรณีแบบซ้ำ:
factorial(n)คือn * factorial(n - 1)
public class Recursion {
public static int factorial(int n) {
if (n <= 1) { // base case
return 1;
}
return n * factorial(n - 1); // recursive case
}
}
การเรียกใช้ถูกยกเลิกอย่างไร
- แต่ละการเรียก รอ ให้การเรียกที่เล็กกว่าเสร็จสิ้น จากนั้นจึงคูณและส่งค่ากลับ
- ติดตาม
factorial(3)การเรียกจะ ลด ลง แล้วคำตอบจะ ส่ง กลับขึ้น
factorial(3) = 3 * factorial(2) <- waits
factorial(2) = 2 * factorial(1) <- waits
factorial(1) = 1 <- base case, returns 1
factorial(2) = 2 * 1 = 2 <- returns 2
factorial(3) = 3 * 2 = 6 <- returns 6
ตัวอย่าง: ผลรวมถึง n
sumTo(n)เพิ่ม1 + 2 + ... + n. ตัวอย่างเช่นsumTo(4) = 10.- กรณีฐาน:
sumTo(0)คือ0(ไม่มีอะไรให้บวก) - กรณีแบบซ้ำ:
sumTo(n)คือn + sumTo(n - 1)
public class Recursion {
public static int sumTo(int n) {
if (n <= 0) { // base case
return 0;
}
return n + sumTo(n - 1); // recursive case
}
}
การเรียกซ้ำบนอาร์เรย์
- เราสามารถเรียกซ้ำด้วย ดัชนี ที่เคลื่อนที่เข้าหาส่วนท้ายได้
- กรณีฐาน: เมื่อดัชนีอยู่ เกินจุดสุดท้าย ให้ส่ง
0 - กรณีแบบซ้ำ: บวก
a[i]เข้ากับผลรวมของส่วนที่เหลือarraySum(a, i + 1)
public class Recursion {
public static int arraySum(int[] a, int i) {
if (i >= a.length) { // base case: past the end
return 0;
}
return a[i] + arraySum(a, i + 1);
}
}
- เพื่อคำนวณผลรวมของอาร์เรย์ทั้งหมด ให้เริ่มจากดัชนี
0:arraySum(a, 0) - แต่ละการเรียกจัดการกับ หนึ่ง ค่า และเชื่อใจว่าการเรียกถัดไปจะจัดการส่วนที่เหลือ
ข้อผิดพลาดที่พบบ่อย
- การเรียกซ้ำต้องการกรณีฐาน มิฉะนั้นจะเกิด StackOverflowError
- แต่ละ call ต้องมุ่งหน้าเข้าใกล้ base case มากขึ้นเรื่อยๆ
ลองดูเลย
- แต่ละงานให้คุณมีโครงร่างเมทოდพร้อม TODO เขียนกรณีฐาน และ กรณีแบบซ้ำ
- Harness ที่ซ่อนอยู่จะเรียกเมทอดของคุณด้วยค่าต่างๆ หลายตัวและตรวจสอบผลลัพธ์
- ใช้ Check answer เพื่อ compile โค้ดของคุณพร้อมทดสอบด้วย test ที่กำหนดและดูผลลัพธ์ รักษาโครงสร้าง class และ method ตามที่แสดงในไฟล์เริ่มต้น
Recursion: Base + Recursive case
Calls แบ่งออกจนกว่าจะมี base case, แล้วคำตอบจะย้อนกลับขึ้น.
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม factorial(int n) ให้สมบูรณ์เพื่อให้กลับคืน n * (n-1) * ... * 1 โดยใช้ recursion. ใช้ base case สำหรับ n <= 1. ตัวตรวจสอบทดสอบหลายค่า.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม sumTo(int n) ให้สมบูรณ์เพื่อให้กลับคืน 1 + 2 + ... + n โดยใช้ recursion. ใช้ base case สำหรับ n <= 0. ตัวตรวจสอบทดสอบหลายค่า.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
เติม arraySum(int[] a, int i) เพื่อให้กลับค่าผลรวมของ a[i] ไปจนถึงจุดสุดท้าย โดยใช้วิธีเรียกซ้ำ (recursion) กรณีฐาน: เมื่อ i เกินตำแหน่งสุดท้าย ให้กลับค่า 0 ตัวตรวจสอบจะทดสอบกับอาร์เรย์หลายชุด
คลิก Run เพื่อดูผลลัพธ์ที่นี่