Đệ quy C++
đệ quy
Đệ quy là kỹ thuật thực hiện lệnh gọi hàm. Kỹ thuật này cung cấp một cách để chia các vấn đề phức tạp thành các vấn đề đơn giản dễ giải quyết hơn.
Đệ quy có thể hơi khó hiểu. Cách tốt nhất để tìm ra cách nó hoạt động là thử nghiệm nó.
Ví dụ đệ quy
Việc cộng hai số với nhau rất dễ thực hiện nhưng việc cộng một dãy số lại phức tạp hơn. Trong ví dụ sau, đệ quy được sử dụng để cộng một dãy số lại với nhau bằng cách chia nó thành nhiệm vụ đơn giản là cộng hai số:
Ví dụ
int sum(int k) {
if (k > 0) {
return k + sum(k - 1);
} else {
return 0;
}
}
int main() {
int result = sum(10);
cout <<
result;
return 0;
} Hãy tự mình thử »Ví dụ giải thích
Khi hàm sum() được gọi, nó thêm tham số k vào tổng của tất cả các số nhỏ hơn k và trả về kết quả. Khi k trở thành 0, hàm chỉ trả về 0. Khi chạy, chương trình thực hiện theo các bước sau:
10 + ( 9 + tổng(8) )
10 + ( 9 + ( 8 + tổng(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + tổng(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0
Vì hàm không tự gọi khi k bằng 0 nên chương trình dừng ở đó và trả về kết quả.
Nhà phát triển phải hết sức cẩn thận với đệ quy vì có thể khá dễ dàng viết một hàm không bao giờ kết thúc hoặc một hàm sử dụng quá nhiều bộ nhớ hoặc sức mạnh bộ xử lý. Tuy nhiên, khi được viết chính xác, đệ quy có thể là một cách tiếp cận lập trình rất hiệu quả và tinh tế về mặt toán học.
