Đệ quy trong tin học

Đệ quy (tiếng Anh: recursion) là kỹ thuật trong lập trình máy tính nơi một hàm tự gọi lại chính nó.

Định nghĩa hình thức về đệ quy

Trong toán học và khoa học máy tính, một đặc tính hoặc cấu trúc được gọi là đệ quy khi nó xác định một lớp đối tượng hoặc phương pháp thông qua một số ít trường hợp đơn giản (thường chỉ một) và sau đó áp dụng quy tắc để chuyển các trường hợp phức tạp về các trường hợp đơn giản.

Ví dụ, sau đây là định nghĩa đệ quy về tổ tiên:

• Bố mẹ của một người là tổ tiên của người đó (trường hợp cơ bản);
• Bố mẹ của tổ tiên một người nào đó cũng là tổ tiên của người đó (bước đệ quy).

Những định nghĩa như vậy thường xuất hiện trong toán học (chính là quy nạp toán học).

Định nghĩa qua đệ quy

Một khái niệm X được định nghĩa qua đệ quy nếu trong định nghĩa đó có sử dụng chính khái niệm X.

• Ví dụ 1: Định nghĩa số tự nhiên:

- 0 là một số tự nhiên.

- n là số tự nhiên nếu n - 1 là số tự nhiên.

Đệ quy trong lĩnh vực khoa học máy tính

Một phương pháp phổ biến để giải quyết các bài toán là chia chúng thành các bài toán con nhỏ hơn cùng loại. Phương pháp này gọi là thuật toán chia để trị, nền tảng của nhiều giải thuật quan trọng và là cơ sở của quy hoạch động.

Một ví dụ kinh điển về đệ quy là hàm tính giai thừa, minh họa bằng giả mã trong C hoặc C++ dưới đây:

int factorial(n) 
 {
   if (n 
  

    
  
  <= 1)
     return 1;
   else
     return n * factorial(n-1);
 }

Một ví dụ khác về thuật toán đệ quy là quy trình duyệt tất cả các nút trong cấu trúc dữ liệu cây:

 procedure ProcessTree(node)
 {
   ProcessNode(node);    // xử lý nút hiện tại
   for each child_node of node do ProcessTree(child_node);
 }

Để duyệt cây, gọi quy trình này với nút gốc của cây. Sau đó, quy trình sẽ đệ quy xử lý tất cả các nút con của nút vừa gọi cho đến khi gặp nút lá (không có con).

Cấu trúc cây cũng được định nghĩa bằng đệ quy như sau:

  struct node
  {
    child_nodes: list<node>;
...
  }

  struct tree
   {
     root: node;
...
    }

Cây được biểu diễn bằng một nút gốc và danh sách các nút con. Mỗi nút con cũng có thể có danh sách nút con của nó, biến nó thành gốc của một cây con. Nút lá là nút không có con, đó là trường hợp cơ bản.

Hàm đệ quy

Trong lập trình, một chương trình con (hàm, thủ tục) được gọi là đệ quy khi trong quá trình thực hiện nó có phần phải gọi lại chính nó.

Cấu trúc chính

Một chương trình con đệ quy cơ bản gồm hai phần chính.

• Phần cơ sở: xử lý các giá trị cụ thể ban đầu của tham số.
• Phần đệ quy: định nghĩa các tác động cần thực hiện cho giá trị hiện tại của tham số bằng cách sử dụng các tác động đã được định nghĩa trước đó với tham số nhỏ hơn.

Ví dụ: Hàm tính giai thừa của một số tự nhiên n (tính $n!$) (Đoạn mã sau được viết bằng ngôn ngữ Pascal)

  function factorial(n: Word): Longint;
  begin
    if n = 0 then
      exit(1)
    else
      exit(n*(factorial(n-1)));
  end;

Quy trình thực hiện

Trong ví dụ này, quy trình tiến hành như sau:

• Khi có lệnh gọi hàm, ví dụ:

 n := factorial(3);

• máy sẽ ghi nhớ như sau:

 factorial(3) := 3 * factorial(2);

và bắt đầu tính gt(2)

• tiếp theo máy ghi nhận:

 factorial(2) := 2 * factorial(1);

và tính gt(1)

• Theo định nghĩa của hàm:

 giaithua(1):= 1;

• Máy sẽ quay ngược lại:

 giaithua(2):= 2 * 1;

cho kết quả là 2

• Tiếp tục:

 giaithua(3):= 3 * 2;

cho kết quả là 6

• Như vậy kết quả cuối cùng trả về là 6. Ta có: 3! = 6

Đệ quy tương hỗ

Nếu có hai chương trình con A1 và A2 gọi nhau ta có đệ quy tương hỗ.

Đệ quy tương hỗ thường được sử dụng để duyệt cây theo đường sâu.

type B(...);
type A(...)
{
....
    B(...);
...
}
type B(...)
{
....
    A(...);
...
}

• Thuật toán đệ quy lùi
• Đệ quy toán học
• Tháp Hà Nội