Hàm đệ quy
Bài học 8 trên 17 trong khóa học Hàm trong C của Coddy.
Hàm đệ quy là hàm liên tục gọi chính nó.
Một ví dụ nổi tiếng về hàm này là khi ta cần tính giai thừa của một số.
Công thức là n!=1×2×…×n.
Để tính giai thừa của một số, ta cần nhân tất cả các số từ 1 đến n.
Ví dụ:
4!=1×2×3×4=24Ta có thể định nghĩa một hàm đệ quy như sau:
int fact(int n) {
if (n == 1) {
return 1;
}
return n * fact(n - 1);
}Hãy tưởng tượng bạn có một cầu thang. Để bắt đầu leo lên, bạn đứng ở tầng trệt (bậc 0). Trong hàm đệ quy, điểm bắt đầu này được gọi là trường hợp cơ sở. Đây là nơi hàm ngừng gọi chính nó và trả về một giá trị.
Trong ví dụ về giai thừa, trường hợp cơ sở xảy ra khi nnn (số cần tính) bằng 1. Giai thừa của 1 đơn giản là 1, nên hàm trả về 1 mà không cần tính thêm.
Đầu tiên, ta kiểm tra xem số đó có bằng một hay không:
if (n == 1) {
return 1;
}Lời gọi đệ quy:
Với mọi số lớn hơn 1, hàm dựa vào những phiên bản nhỏ hơn của chính nó. Hàm gọi chính nó với n−1 (lùi xuống một bậc thang). Đây là lời gọi đệ quy:
return n * fact(n - 1);Hãy hình dung việc này giống như leo cầu thang. Để lên bậc 5, trước tiên bạn cần lên bậc 4, rồi đến bậc 3 và cứ tiếp tục như vậy. Mỗi lời gọi đệ quy giống như bước xuống một bậc.
Thử thách
DễĐịnh nghĩa hàm đệ quy:
- Viết một hàm (function) có tên countdown nhận tham số số nguyên n.
- Bên trong hàm này, in ra giá trị hiện tại của n.
- Nếu n lớn hơn 0, hãy gọi đệ quy countdown với n - 1.
- Nếu n bằng 0 hoặc nhỏ hơn, in ra "Blastoff!".
Ví dụ: Nếu số đó là 3, đầu ra sẽ như sau:
3
2
1
Blastoff!
Tự làm thử
#include <stdio.h>
// Định nghĩa hàm countdown
int main() {
int start = 5;
// Gọi hàm
return 0;
}Tất cả bài học trong Hàm trong C
Tự luyện tập: Trình biên dịch C online