Xem mã nguồn của Đệ quy (tin học)

[[Tập tin:SierpinskiTriangle.PNG|nhỏ|phải|300x300|[[Tam giác Sierpinski]]]]
{{Mẫu hình lập trình}}
'''Đệ 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 ==
Trong [[toán học]] và [[khoa học máy tính]], các tính chất (hoặc cấu trúc) được gọi là đệ quy nếu trong đó một lớp các đối tượng hoặc phương pháp được xác định bằng việc xác định một số rất ít các trường hợp hoặc phương pháp đơn giản (thông thường chỉ một) và sau đó xác định quy tắc đưa các trường hợp phức tạp về các trường hợp đơn giả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 ==
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 ==
{{Chính|Giải thuât đệ quy}} 
Có một phương pháp chung để giải các bài toán là chia bài toán thành các bài toán con đơn giả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 để 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ổ điển của đệ quy là hàm [[giai thừa]] cho bằng [[giả mã]] trong [[ngôn ngữ lập trình C|C]] hoặc [[C++]] sau đây:

<syntaxhighlight lang="c">
int factorial(n) 
 {
   if (n <= 1)
     return 1;
   else
     return n * factorial(n-1);
 }
</syntaxhighlight>

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

<syntaxhighlight lang="c">
 procedure ProcessTree(node)
 {
   ProcessNode(node);    // thực hiện một thuật toán riêng với nút đầu
   for each child_node of node do ProcessTree(child_node);
 }
</syntaxhighlight>

Để 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ất cả các nút con của nút vừa gọi (nghĩa là các 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:
<syntaxhighlight lang="c">
  struct node
  {
    child_nodes: list<node>;
...
  }

  struct tree
   {
     root: node;
...
    }
</syntaxhighlight>

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 ==
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 quá trình thực hiện nó có phần phải gọi đến chính nó.

=== Cấu trúc chính ===
Một chương trình con đệ quy căn 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 <math>n!</math>) (Đoạn mã sau được viết bằng [[ngôn ngữ Pascal]])

<syntaxhighlight lang="pascal">
  function factorial(n: Word): Longint;
  begin
    if n = 0 then
      exit(1)
    else
      exit(n*(factorial(n-1)));
  end;
  
</syntaxhighlight>

=== Quy trình thực hiện ===
Trong ví dụ trên, quy trình thực hiện như sau:

* Khi có lệnh gọi hàm, chẳng hạn:
<syntaxhighlight lang="pascal"> n:= factorial(3);</syntaxhighlight>

* thì máy sẽ ghi nhớ là:
<syntaxhighlight lang="pascal"> factorial(3):= 3 * factorial(2);</syntaxhighlight> và đi tính gt(2)

* kế tiếp máy lại ghi nhớ:
<syntaxhighlight lang="pascal"> factorial(2):= 2 * factorial(1);</syntaxhighlight> và đi tính gt(1)

* Theo định nghĩa của hàm thì:
<syntaxhighlight lang="pascal"> factorial(1):= 1; </syntaxhighlight>

* Máy sẽ quay ngược lại:
<syntaxhighlight lang="pascal"> factorial(2):= 2 * 1;</syntaxhighlight> cho kết quả là 2

* Tiếp tục:
<syntaxhighlight lang="pascal"> factorial(3):= 3 * 2;</syntaxhighlight> 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 dùng để [[duyệt cây]] theo chiều sâu.

<syntaxhighlight lang="c++">
type B(...);
type A(...)
{
....
    B(...);
...
}
type B(...)
{
....
    A(...);
...
}
</syntaxhighlight>

== Xem thêm ==
* [[Thuật toán quay lui]]
* [[Quy nạp toán học]]
* [[Tháp Hà Nội]]

==Tham khảo==
{{tham khảo}}

[[Thể loại:Thuật toán]]
[[Thể loại:Logic toán]]
[[Thể loại:Lý thuyết tính toán]]
[[Thể loại:Cấu trúc dữ liệu]]
[[Thể loại:Khoa học máy tính lý thuyết]]
[[Thể loại:Chương trình con]]