Dart Đệ quy là phương thức mà một hàm gọi chính nó như một chương trình con của nó. Nó được sử dụng để giải quyết vấn đề phức tạp bằng cách chia nó thành một phần nhỏ. Một hàm được gọi chính nó lặp đi lặp lại hoặc đệ quy, thì quá trình này được gọi là đệ quy.
Các trình lặp có thể là một lựa chọn để giải quyết vấn đề, nhưng đệ quy được khuyến nghị cho các lập trình viên để giải quyết các vấn đề phức tạp vì nó là một cách tiếp cận hiệu quả của kỹ thuật giải quyết vấn đề. Nó đòi hỏi ít thời gian và mã hơn để đánh giá cùng một nhiệm vụ phức tạp.
Các bài viết liên quan:
Đệ quy thực hiện nhiều cuộc gọi đến cùng một hàm; tuy nhiên, cần có một case cơ sở để kết thúc đệ quy.
Đệ quy sử dụng kỹ thuật chia và chinh phục để giải quyết một nhiệm vụ tính toán toán học phức tạp. Nó chia nhiệm vụ lớn thành nhiều phần nhỏ.
Đệ quy không được khuyến khích để giải quyết tất cả các dạng vấn đề. Tuy nhiên, tốt nhất là cho một số câu hỏi như tìm kiếm, sắp xếp, Inorder / Preorder / Postorder, Tree Traversal và DFS of Graph các thuật toán. Nhưng, trong khi sử dụng đệ quy, nó phải được thực hiện cẩn thận; nếu không, nó biến thành vòng lặp vô hạn.
Xem thêm Đệ quy trong c++
Điều kiện cơ sở trong đệ quy là gì?
void main() {
int num = 5;
int giaiThua(int num) {
if (num <= 1) {
// case cơ sở
return 1;
} else {
return num * giaiThua(num - 1);
}
}
print(giaiThua(5));
}Trong ví dụ trên, case cơ sở được định nghĩa là n <= 1 và giá trị lớn hơn của một số có thể được giải quyết bằng cách thay đổi thành một số nhỏ hơn cho đến khi case cơ sở được khớp.
Lưu ý – case cơ sở hoặc điều kiện kết thúc hợp lệ được yêu cầu trong hàm đệ quy; nếu không, nó sẽ biến thành một vòng lặp vô hạn.
Hàm đệ quy Dart
Các hàm đệ quy khá giống với các hàm khác, nhưng điểm khác biệt là nó gọi chính nó một cách đệ quy. Một hàm đệ quy lặp lại nhiều lần cho đến khi nó trả về kết quả cuối cùng. Nó cho phép các lập trình viên giải quyết các vấn đề phức tạp với mã tối thiểu.
Đệ quy hoạt động như thế nào?
Hãy hiểu khái niệm đệ quy của ví dụ về giai thừa của một số cho trước. Trong ví dụ sau, chúng ta sẽ đánh giá giai thừa của n số. Đó là một loạt các phép nhân như sau.
Giai thừa của n (n!) = N * (n- 1 ) * (n- 2 ) …….. 1
Đặc điểm của hàm đệ quy
Các đặc điểm của hàm đệ quy được đưa ra dưới đây.
- Một hàm đệ quy là một dạng hàm duy nhất trong đó hàm gọi chính nó.
- Một case cơ sở hợp lệ được yêu cầu để kết thúc hàm đệ quy.
- Nó chậm hơn so với việc lặp lại vì tổng chi phí của ngăn xếp.
Hãy xem cú pháp đệ quy:
Cú pháp:
void recurse () {
//các câu lệnh)
recurse ();
//các câu lệnh);
}
void main () {
//các câu lệnh)
recurse ();
//các câu lệnh)
} Hãy hiểu ví dụ sau.
Ví dụ 1
int factorial(int num) {
// case cơ sở của đệ quy.
if (num <= 1) {
// case cơ sở
return 1;
} else {
return num * factorial(num - 1); // hàm gọi chính nó.
}
}
void main() {
var num = 5;
// Lưu trữ kết quả cuộc gọi hàm trong biến fact.
var fact = factorial(num);
print("Giai thừa của 5 là: ${fact}");
}Giải trình:
Trong ví dụ trên, factorial () là một hàm đệ quy như chính nó gọi. Khi chúng ta gọi hàm factorial () bằng cách truyền giá trị nguyên 5, nó sẽ gọi một cách đệ quy chính nó bằng cách giảm số.
Hàm factorial () sẽ được gọi mọi lúc cho đến khi nó khớp với điều kiện cơ sở hoặc bằng một. Nó nhân số với factorial của số. Hãy xem xét lời giải thích sau đây về cuộc gọi đệ quy.
- factorial ( 5 ) # hàm gọi đầu tiên với 5
- 5 * factorial ( 4 ) # hàm gọi thứ 2 với 4
- 5 * 4 * factorial ( 3 ) # hàm gọi thứ 3 với 3
- 5 * 4 * 3 * factorial ( 2 ) # hàm gọi thứ 4 với 2
- 5 * 4 * 3 * 2 * 1 # return từ hàm gọi thứ hai
- 120 # return từ hàm gọi đầu tiên
Đệ quy kết thúc khi số lượng giảm xuống 1, và đó là điều kiện cơ bản của đệ quy.
Một hàm đệ quy phải có một điều kiện cơ sở để tránh lệnh gọi vô hạn.
Nhược điểm của Đệ quy
- Các cuộc gọi đệ quy tiêu tốn rất nhiều bộ nhớ; đó là lý do tại sao chúng không hiệu quả.
- Các hàm đệ quy rất khó gỡ lỗi.
- Đôi khi, thật khó để tuân theo logic đằng sau đệ quy.
