Recursion: base case and recursive case
This page needs a recent browser (with SharedArrayBuffer support). Please update Chrome, Edge, Firefox or Safari to the latest version. · Trang này cần trình duyệt gần đây (hỗ trợ SharedArrayBuffer). Vui lòng cập nhật Chrome, Edge, Firefox hoặc Safari lên phiên bản mới nhất.
English
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.
Tiếng Việt
Một hàm gọi chính nó
- Đệ quy là khi một hàm gọi chính nó để giải quyết một phiên bản nhỏ hơn của cùng một vấn đề.
- Nó cần hai phần: một trường hợp cơ sở để dừng lại, và một trường hợp đệ quy thu nhỏ vấn đề.
- Nếu không có trường hợp cơ sở, nó sẽ tự gọi mãi mãi và gây lỗi.
English
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.
Tiếng Việt
Trường hợp cơ sở
- Trường hợp cơ sở là vấn đề nhỏ nhất bạn có thể trả lời trực tiếp, không còn gọi nào nữa.
- Với giai thừa,
0!và1!đều bằng1— đó chính là trường hợp cơ sở. - Luôn xử lý trường hợp cơ sở trước, để quá trình đệ quy có nơi dừng lại.
English
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.
Tiếng Việt
Trường hợp đệ quy
- Trường hợp đệ quy giải quyết vấn đề bằng cách sử dụng kết quả của một vấn đề nhỏ hơn.
n! = n × (n - 1)!, do đófactorial(n)trả vền * factorial(n - 1).- Mỗi lần gọi phải tiến gần hơn về phía trường hợp cơ sở, nếu không nó sẽ không bao giờ dừng.
#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;
}
English
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.
Tiếng Việt
Quy hồi qua mảng
- Bạn có thể đệ quy dọc theo mảng bằng cách truyền một chỉ số tăng dần sau mỗi lần gọi.
- Trường hợp cơ sở là "chỉ số đã đạt đến cuối" (trả về
0cho tổng). - Trường hợp đệ quy là
a[i] + sum(a, i + 1, n)— phần tử này cộng với tổng của phần còn lại.
English
Common mistakes
- Recursion needs a base case, or the call stack overflows.
- Each call must move closer to the base case.
Tiếng Việt
Lỗi thường gặp
- Đệ quy cần một trường hợp cơ sở, nếu không ngăn stack sẽ bị tràn.
- Mỗi lần gọi phải tiến gần hơn đến trường hợp cơ sở.
English
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.
Tiếng Việt
Bây giờ bạn thử
- Viết trường hợp cơ sở trước, sau đó viết trường hợp đệ quy gọi chính nó với đầu vào nhỏ hơn.
- Giữ các giá trị thử nghiệm nhỏ để các con số nằm gọn trong một
int. - Không viết một
main— trình kiểm tra sẽ cung cấp cho bạn một cái.
Explore · Khám phá
Recursion returns up
Calls split to a base case, then values return up.
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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.
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.
Click Run to see the output here. · Nhấn Chạy để xem kết quả ở đây.