Recursion Trong C++

Recursion

Đệ quy là kỹ thuật tự thực hiện một lời 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 với nó.

Recursion Example

Việc cộng hai số với nhau rất dễ thực hiện, nhưng thêm một dãy số thì phức tạp hơn. Trong ví dụ sau, đệ quy được sử dụng để cộng một dải số với nhau bằng cách chia nhỏ nó thành tác vụ đơn giản là cộng hai số:

Example

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;
}

Giải thích ví dụ

Khi hàm sum () được gọi, nó sẽ 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 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(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 nên rất 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 của bộ xử lý. Tuy nhiên, khi được viết chính xác thì đệ quy có thể là một cách tiếp cận lập trình rất hiệu quả và thanh lịch về mặt toán học.