Recursion: base case and recursive case · Recursion: Base case และ Recursive case
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · หน้านี้ต้องใช้เบราว์เซอร์ล่าสุด (รองรับ SharedArrayBuffer) กรุณาอัปเดต Chrome, Edge, Firefox หรือ Safari เป็นเวอร์ชันล่าสุด
English
A method that calls itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
ไทย
A Method that Calls Itself
- Recursion is when a method calls itself to solve a smaller piece of the same problem.
- On the AP CSA exam you mostly trace recursion (follow the calls by hand). Writing small recursive methods helps you trace well.
- Every recursive method needs two parts: a base case and a recursive case.
English
Base case and recursive case
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
ไทย
กรณีฐานและกรณีรีเคอร์ชัน
- Base case: the simplest input, where you return an answer without calling yourself. This stops the recursion.
- Recursive case: you call the same method with a smaller input, then build the answer.
- Without a base case, the method calls forever and crashes (a stack overflow).
English
Example: factorial
factorial(n)meansn * (n-1) * ... * 1. For examplefactorial(4) = 24.- Base case:
factorial(1)is1. - Recursive case:
factorial(n)isn * factorial(n - 1).
ไทย
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
}
}
English
How the calls unwind
- Each call waits for the smaller call to finish. Then it multiplies and returns.
- Trace
factorial(3). Calls go down, then answers come back up.
ไทย
การเรียกใช้ถูกยกเลิกอย่างไร
- แต่ละการเรียก รอ ให้การเรียกที่เล็กกว่าเสร็จสิ้น จากนั้นจึงคูณและส่งค่ากลับ
- ติดตาม
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
English
Example: sum to n
sumTo(n)adds1 + 2 + ... + n. For examplesumTo(4) = 10.- Base case:
sumTo(0)is0(nothing to add). - Recursive case:
sumTo(n)isn + sumTo(n - 1).
ไทย
ตัวอย่าง: ผลรวมถึง 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
}
}
English
Recursion over an array
- We can also recurse with an index that moves toward the end.
- Base case: when the index is past the last spot, return
0. - Recursive case: add
a[i]to the sum of the rest,arraySum(a, i + 1).
ไทย
การเรียกซ้ำบนอาร์เรย์
- เราสามารถเรียกซ้ำด้วย ดัชนี ที่เคลื่อนที่เข้าหาส่วนท้ายได้
- กรณีฐาน: เมื่อดัชนีอยู่ เกินจุดสุดท้าย ให้ส่ง
0 - กรณีแบบซ้ำ: บวก
a[i]เข้ากับผลรวมของส่วนที่เหลือarraySum(a, i + 1)
English
- To sum the whole array you start at index
0:arraySum(a, 0). - Each call handles one value and trusts the next call for the rest.
ไทย
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) - แต่ละการเรียกจัดการกับ หนึ่ง ค่า และเชื่อใจว่าการเรียกถัดไปจะจัดการส่วนที่เหลือ
English
Common mistakes
- Recursion needs a base case, or it throws StackOverflowError.
- Each call must move closer to the base case.
ไทย
ข้อผิดพลาดที่พบบ่อย
- การเรียกซ้ำต้องการกรณีฐาน มิฉะนั้นจะเกิด StackOverflowError
- Each call must move closer to the base case.
English
Now you try
- Each task gives you a method skeleton with a TODO. Write the base case and the recursive case.
- A hidden Harness calls your method with several values and checks the result.
- Press Run to compile, then Check answer.
ไทย
ลองดูเลย
- แต่ละงานให้คุณมีโครงร่างเมทოდพร้อม TODO เขียนกรณีฐาน และ กรณีแบบซ้ำ
- Harness ที่ซ่อนอยู่จะเรียกเมทอดของคุณด้วยค่าต่างๆ หลายตัวและตรวจสอบผลลัพธ์
- กด Run เพื่อคอมไพล์ แล้วกด Check answer
Explore · สำรวจ
Recursion: base + recursive case · Recursion: Base + Recursive case
Calls split until a base case, then answers return up. · Calls แบ่งออกจนกว่าจะมี base case, แล้วคำตอบจะย้อนกลับขึ้น.
Complete factorial(int n) so it returns n * (n-1) * ... * 1 using recursion. Use a base case for n <= 1. The checker tests several values. · เติม factorial(int n) ให้สมบูรณ์เพื่อให้กลับคืน n * (n-1) * ... * 1 โดยใช้ recursion. ใช้ base case สำหรับ n <= 1. ตัวตรวจสอบทดสอบหลายค่า.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete sumTo(int n) so it returns 1 + 2 + ... + n using recursion. Use a base case for n <= 0. The checker tests several values. · เติม sumTo(int n) ให้สมบูรณ์เพื่อให้กลับคืน 1 + 2 + ... + n โดยใช้ recursion. ใช้ base case สำหรับ n <= 0. ตัวตรวจสอบทดสอบหลายค่า.
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete arraySum(int[] a, int i) so it returns the sum of a[i] to the end, using recursion. Base case: when i is past the last spot, return 0. The checker tests several arrays. · เติม arraySum(int[] a, int i) เพื่อให้กลับค่าผลรวมของ a[i] ไปจนถึงจุดสุดท้าย โดยใช้วิธีเรียกซ้ำ (recursion) กรณีฐาน: เมื่อ i เกินตำแหน่งสุดท้าย ให้กลับค่า 0 ตัวตรวจสอบจะทดสอบกับอาร์เรย์หลายชุด
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่