Cấu trúc dữ liệu - Khái niệm cơ bản về đệ quy

Một số ngôn ngữ lập trình máy tính cho phép một mô-đun hoặc hàm gọi chính nó. Kỹ thuật này được gọi là đệ quy. Trong đệ quy, một hàmα gọi chính nó trực tiếp hoặc gọi một hàm β đến lượt nó gọi hàm gốc α. Chức năngα được gọi là hàm đệ quy.

Example - một hàm gọi chính nó.

int function(int value) {
   if(value < 1)
      return;
   function(value - 1);

   printf("%d ",value);   
}

Example - một hàm gọi một hàm khác mà lần lượt nó sẽ gọi lại.

int function1(int value1) {
   if(value1 < 1)
      return;
   function2(value1 - 1);
   printf("%d ",value1);   
}
int function2(int value2) {
   function1(value2);
}

Tính chất

Một hàm đệ quy có thể đi vô hạn giống như một vòng lặp. Để tránh chạy vô hạn hàm đệ quy, có hai thuộc tính mà một hàm đệ quy phải có:

Base criteria - Phải có ít nhất một tiêu chí hoặc điều kiện cơ sở, sao cho khi điều kiện này được đáp ứng, hàm ngừng gọi chính nó một cách đệ quy.
Progressive approach - Các cuộc gọi đệ quy phải tiến triển theo cách mà mỗi khi một cuộc gọi đệ quy được thực hiện, nó lại gần với tiêu chí cơ sở hơn.

Thực hiện

Nhiều ngôn ngữ lập trình thực hiện đệ quy bằng cách stacks. Nói chung, bất cứ khi nào một hàm (caller) gọi một hàm khác (callee) hoặc chính nó là callee, hàm người gọi chuyển quyền kiểm soát thực thi đến callee. Quá trình chuyển này cũng có thể liên quan đến một số dữ liệu được chuyển từ người gọi đến người gọi.

Điều này ngụ ý rằng, hàm người gọi phải tạm dừng việc thực thi của nó và tiếp tục lại sau khi điều khiển thực thi trả về từ hàm callee. Ở đây, hàm người gọi cần phải bắt đầu chính xác từ thời điểm thực thi mà nó tự đặt nó ở trạng thái chờ. Nó cũng cần các giá trị dữ liệu chính xác giống như nó đã hoạt động. Với mục đích này, một bản ghi kích hoạt (hoặc khung ngăn xếp) được tạo cho hàm người gọi.

Bản ghi kích hoạt này lưu giữ thông tin về các biến cục bộ, tham số chính thức, địa chỉ trả về và tất cả thông tin được chuyển đến hàm người gọi.

Phân tích đệ quy

Người ta có thể tranh luận tại sao phải sử dụng đệ quy, vì cùng một nhiệm vụ có thể được thực hiện với phép lặp. Lý do đầu tiên là, đệ quy làm cho một chương trình dễ đọc hơn và vì các hệ thống CPU nâng cao mới nhất, đệ quy hiệu quả hơn so với lặp lại.

Thời gian phức tạp

Trong trường hợp lặp lại, chúng tôi lấy số lần lặp để đếm độ phức tạp về thời gian. Tương tự như vậy, trong trường hợp đệ quy, giả sử mọi thứ là không đổi, chúng tôi cố gắng tìm ra số lần một lệnh gọi đệ quy được thực hiện. Một lệnh gọi hàm là Ο (1), do đó (n) số lần lệnh gọi đệ quy được thực hiện làm cho hàm đệ quy Ο (n).

Không gian phức tạp

Độ phức tạp của không gian được tính là lượng không gian bổ sung cần thiết để mô-đun thực thi. Trong trường hợp lặp lại, trình biên dịch hầu như không yêu cầu thêm dung lượng. Trình biên dịch tiếp tục cập nhật giá trị của các biến được sử dụng trong các lần lặp. Nhưng trong trường hợp đệ quy, hệ thống cần lưu trữ hồ sơ kích hoạt mỗi khi thực hiện cuộc gọi đệ quy. Do đó, có thể coi rằng độ phức tạp không gian của hàm đệ quy có thể cao hơn so với hàm có lặp.