Cộng đồng chia sẻ tri thức Lib24.vn

Cấu trúc dữ liệu - Cơ bản đệ quy

Gửi bởi: Võ Thị Hường 13 tháng 2 2020 lúc 14:22:48


Mục lục
* * * * *

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

Ví dụ - một hàm gọi chính nó.

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

   printf("%d ",value);   
}

Ví dụ - một hàm gọi một hàm khác lần lượt gọi lại hàm đó.

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

Tính chất

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

  1. Tiêu chí cơ sở - 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 sẽ tự gọi đệ quy.
  2. Cách tiếp cận lũy tiến - Các cuộc gọi đệ quy nên tiến triển theo cách mà mỗi lần thực hiện cuộc gọi đệ quy, nó sẽ tiến gần hơn đến các tiêu chí cơ bản.

Thực hiện

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

Điều này ngụ ý, chức năng người gọi phải tạm dừng thực thi và tiếp tục lại sau khi điều khiển thực thi trả về từ chức năng callee. Ở đây, hàm người gọi cần bắt đầu chính xác từ điểm thực thi nơi nó tự giữ. Nó cũng cần các giá trị dữ liệu chính xác giống như nó đang làm việc. 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 chức năng người gọi.

Cấu trúc dữ liệu - Cơ bản đệ quy

Bản ghi kích hoạt này 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 truyền cho 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 chương trình dễ đọc hơn và do các hệ thống CPU được cải tiến mới nhất, đệ quy hiệu quả hơn so với các lần lặp.

Độ phức tạp thời gian

Trong trường hợp lặp lại, chúng tôi lấy số lần lặp để tính độ phức tạp 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 cuộc gọi đệ quy được thực hiện. Một cuộc gọi được thực hiện cho một hàm là Ο (1), do đó (n) số lần một cuộc 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 không gian được tính là lượng không gian thêm cần thiết cho mộ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 cần thêm dung lượng. Trình biên dịch tiếp tục cập nhật các 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 đó, nó được coi là độ phức tạp không gian của hàm đệ quy có thể cao hơn hàm của phép lặp.


Được cập nhật: 25 tháng 3 lúc 17:08:12 | Lượt xem: 490

Các bài học liên quan