Recursion: base case and recursive case · Recursion: Base case และ Recursive case
A function that calls itself
- Recursion is when a function calls itself to solve a smaller version of the same problem.
- It needs two parts: a base case that stops, and a recursive case that shrinks the problem.
- Without a base case, it would call itself forever and crash.
ฟังก์ชันที่เรียกตัวเอง
- Recursion คือเมื่อฟังก์ชันเรียก ตัวเอง เพื่อแก้ปัญหารุ่นย่อยๆ ของปัญหาเดียวกัน
- ต้องมีสองส่วน: Base case ที่หยุดการทำงาน และ Recursive case ที่ลดขนาดปัญหา
- หากไม่มีกรณีฐาน มันจะเรียกตัวเองตลอดกาลจนระบบล้มเหลว
The base case
- The base case is the smallest problem you can answer directly, with no more calls.
- For factorial,
0!and1!are both1— that is the base case. - Always handle the base case first, so the recursion has somewhere to stop.
Base case
- Base case คือปัญหาขนาดเล็กที่สุดที่คุณตอบได้โดยตรงโดยไม่ต้องเรียกอีก
- สำหรับ Factorial,
0!และ1!ทั้งคู่คือ1— นั่นคือ Base case - จัดการ Base case ก่อนเสมอ เพื่อให้ Recursion มีจุดหยุด
The recursive case
- The recursive case solves the problem using the answer to a smaller one.
n! = n × (n - 1)!, sofactorial(n)returnsn * factorial(n - 1).- Each call must move closer to the base case, or it will never stop.
Recursive case
- Recursive case แก้ไขปัญหาโดยใช้คำตอบจากปัญหาที่ เล็กกว่า
n! = n × (n - 1)!, ดังนั้นfactorial(n)จึงคืนค่าn * factorial(n - 1)- แต่ละ Call ต้องเคลื่อน เข้าใกล้ Base case หรือมันจะไม่เคยหยุด
#include <stdio.h>
int factorial(int n) {
if (n <= 1) return 1; // base case
return n * factorial(n - 1); // recursive case
}
int main(void) {
printf("%d\n", factorial(5)); // 120
return 0;
}
Recursion over an array
- You can recurse along an array by passing an index that moves forward each call.
- The base case is "the index has reached the end" (return
0for a sum). - The recursive case is
a[i] + sum(a, i + 1, n)— this item plus the sum of the rest.
การเรียกซ้ำบนอาร์เรย์
- คุณสามารถทำ Recursion ตามอาร์เรย์โดยการส่ง Index ที่เคลื่อนไปข้างหน้าในแต่ละ Call
- Base case คือ "index ถึงปลายแล้ว" (คืน
0สำหรับผลรวม) - Recursive case คือ
a[i] + sum(a, i + 1, n)— รายการนี้บวกกับผลรวมของส่วนที่เหลือ
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
ข้อผิดพลาดที่พบบ่อย
- Recursion ต้องการ Base case, มิฉะนั้น Call stack จะล้น (Overflow)
- Each call must move closer to the base case.
Now you try
- Write the base case first, then the recursive case that calls itself on a smaller input.
- Keep test values small so the numbers stay inside an
int. - Do not write a
main— the checker provides one.
ลองดูเลย
- เขียน Base case ก่อน แล้วจึงเขียน Recursive case ที่เรียกตัวเองด้วยอินพุตที่เล็กลง
- รักษาค่าทดสอบให้อยู่ในระดับเล็กเพื่อไม่ให้ตัวเลขเกินขอบเขตของ
int - อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Recursion returns up · Recursion ส่งค่ากลับขึ้น
Calls split to a base case, then values return up. · Call แยกเป็น base case แล้วค่าส่งกลับขึ้น
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do not write a main. · เติม int factorial(int n) ด้วย recursion: ส่ง 1 สำหรับ n <= 1 (base case) มิฉะนั้นส่ง n * factorial(n - 1) ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 is 1, otherwise base * power(base, exp - 1). Do not write a main. · เติม int power(int base, int exp) ด้วย recursion (สมมติว่า exp >= 0): base ยกกำลัง 0 คือ 1 มิฉะนั้นส่ง base * power(base, exp - 1) ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่
Complete int array_sum(const int a[], int i, int n) using recursion: it returns the sum of a[i] up to a[n-1]. Base case: i >= n returns 0. Do not write a main. · เติม int array_sum(const int a[], int i, int n) ด้วย recursion: ส่งผลบวกของ a[i] ถึง a[n-1] Base case: i >= n ส่ง 0 ห้าม เขียน main
Click Run to see the output here. · คลิก Run เพื่อดูผลลัพธ์ที่นี่