Recursion: base case and recursive case
ฟังก์ชันที่เรียกตัวเอง
- Recursion คือเมื่อฟังก์ชันเรียก ตัวเอง เพื่อแก้ปัญหารุ่นย่อยๆ ของปัญหาเดียวกัน
- ต้องมีสองส่วน: Base case ที่หยุดการทำงาน และ Recursive case ที่ลดขนาดปัญหา
- หากไม่มีกรณีฐาน มันจะเรียกตัวเองตลอดกาลจนระบบล้มเหลว
Base case
- Base case คือปัญหาขนาดเล็กที่สุดที่คุณตอบได้โดยตรงโดยไม่ต้องเรียกอีก
- สำหรับ Factorial,
0!และ1!ทั้งคู่คือ1— นั่นคือ Base case - จัดการ Base case ก่อนเสมอ เพื่อให้ Recursion มีจุดหยุด
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 ตามอาร์เรย์โดยการส่ง Index ที่เคลื่อนไปข้างหน้าในแต่ละ Call
- Base case คือ "index ถึงปลายแล้ว" (คืน
0สำหรับผลรวม) - Recursive case คือ
a[i] + sum(a, i + 1, n)— รายการนี้บวกกับผลรวมของส่วนที่เหลือ
ข้อผิดพลาดที่พบบ่อย
- Recursion ต้องการ Base case, มิฉะนั้น Call stack จะล้น (Overflow)
- แต่ละ call ต้องมุ่งหน้าเข้าใกล้ base case มากขึ้นเรื่อยๆ
ลองดูเลย
- เขียน Base case ก่อน แล้วจึงเขียน Recursive case ที่เรียกตัวเองด้วยอินพุตที่เล็กลง
- รักษาค่าทดสอบให้อยู่ในระดับเล็กเพื่อไม่ให้ตัวเลขเกินขอบเขตของ
int - อย่า เขียน
main— ตัวตรวจสอบจะจัดเตรียมให้
Recursion returns up
Calls split to a base case, then values return up.
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Complete int factorial(int n) using recursion: return 1 for n <= 1 (the base case), otherwise n * factorial(n - 1). Do ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
Complete int power(int base, int exp) using recursion (assume exp >= 0): base to the power 0 เป็น 1, otherwise base * power(base, exp - 1). Do ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่
ความยาก 4/5 · 280 เหรียญ + บอนัสน้อยๆ เมื่อทำสำเร็จครั้งแรกในวันนี้
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 ผลตอบแทน 0. Do ไม่ใช่ write a main.
คลิก Run เพื่อดูผลลัพธ์ที่นี่