Đệ quy (tin học) – Wikipedia tiếng Việt

Đệ quy (tiếng Anh: recursion) là phương pháp dùng trong các chương trình máy tính trong đó có một hàm tự gọi chính nó.

Khái niệm hình thức về đệ quy[sửa|sửa mã nguồn]

Trong toán học và khoa học máy tính, những đặc thù ( hoặc cấu trúc ) được gọi là đệ quy nếu trong đó một lớp những đối tượng người dùng hoặc giải pháp được xác lập bằng việc xác lập 1 số ít rất ít những trường hợp hoặc giải pháp đơn thuần ( thường thì chỉ một ) và sau đó xác lập quy tắc đưa những trường hợp phức tạp về những trường hợp đơn thuần .Chẳng hạn, định nghĩa sau là định nghĩa đệ quy của tổ tiên :

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

Các định nghĩa kiểu như vậy cũng thường thấy trong toán học (chính là quy nạp toán học)

Định nghĩa theo đệ quy[sửa|sửa mã nguồn]

Một khái niệm X được định nghĩa theo đệ quy nếu trong định nghĩa X có sử dụng ngay 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 khoa học máy tính[sửa|sửa mã nguồn]

Có một giải pháp chung để giải những bài toán là chia bài toán thành những bài toán con đơn thuần hơn cùng loại. Phương pháp này được gọi là Thuật toán chia để trị. Chính nó là chìa khóa để phong cách thiết kế nhiều giải thuật quan trọng, là cơ sở của quy hoạch động .Một ví dụ cổ xưa của đệ quy là hàm giai thừa cho bằng giả mã trong C hoặc C + + sau đây :

intfactorial(n)
{
if(n< =1)
return1;
else
returnn*factorial(n- 1) ;
}

Một ví dụ khác của giải thuật đệ quy là thủ tục duyệt ( nghĩa là triển khai một việc làm nào đó với chúng ) toàn bộ những nút của một cấu trúc tài liệu cây :

procedureProcessTree(node)
{
ProcessNode(node) ;/ / triển khai một thuật toán riêng với nút đầu
foreachchild_nodeofnodedoProcessTree(child_node) ;
}

Để duyệt một cây, gọi thủ tục này với nút gốc của cây như một tham biến khởi tạo. Tiếp theo, thủ tục gọi đệ quy đến chính nó cho tổng thể những nút con của nút vừa gọi ( nghĩa là những cây con của cây vừa gọi ), cho đên khi gặp trường hợp cơ bản nghĩa là nút không có con ( thường gọi là " lá " ) .Chính cấu trúc cây cũng được định nghĩa bằng đệ quy như sau :

struct node
{
child_nodes:list;
...
}

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 của nút ấy. Mỗi nút con lại có danh sách các nút con của nó (và như vậy, nó là gốc của một cây con). Lá với danh sách rỗng các nút con là trường hợp cơ sở của nút.

Chương trình con đệ quy[sửa|sửa mã nguồn]

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

Cấu trúc chính[sửa|sửa mã nguồn]

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

• Phần cơ sở: chứa các tác động của hàm hoặc thủ tục với một số giá trị cụ thể ban đầu của tham số.
• Phần đệ quy: định nghĩa tác động cần được thực hiện cho giá trị hiện thời của các tham số bằng các tác động đã được định nghĩa trước đây với kích thước 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
!

{\displaystyle n!}

) (Đoạn mã sau được viết bằng ngôn ngữ Pascal)

Xem thêm: trồng trong tiếng Tiếng Anh - Tiếng Việt-Tiếng Anh | Glosbe 
  function gt(n: Word): Longint;
  begin
    if n = 1 then
      gt: = 1
    else
      gt: = n * gt(n - 1);
  end;

Quy trình triển khai[sửa|sửa mã nguồn]

Trong ví dụ trên, tiến trình triển khai như sau :

• Khi có lệnh gọi hàm, chẳng hạn:

 n: = gt(3);

• thì máy sẽ ghi nhớ là:

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

và đi tính gt ( 2 )

• kế tiếp máy lại ghi nhớ:

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

và đi tính gt ( 1 )

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

 gt(1): = 1;

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

 gt(2): = 2 * 1;

cho hiệu quả là 2

• Tiếp tục:

 gt(3): = 3 * 2;

cho hiệu 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ỗ[sửa|sửa mã nguồn]

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 dùng để duyệt cây theo chiều sâu .

typeB( ... ) ;
typeA( ... )
{
....
B( ... ) ;
...
}
typeB( ... )
{
....
A( ... ) ;
...
Xem thêm: Chữ S Là Gì Trong Tiếng Anh, So Và S/O Là Viết Tắt Của Từ Gì

}

Source: https://helienthong.edu.vn
Category: Tiếng anh