Một thủ tục hoặc hàm có thể chứa lời gọi đến một thủ tục khác bên trong nó. Bao gồm, chương trình con có thể gọi chính nó. Trong trường hợp này, máy tính không quan tâm. Anh ấy cũng như mọi khi, nhất quán thực hiện các mệnh lệnh mà anh ấy đã gặp từ trên xuống dưới.
Nếu bạn nhớ toán học, thì ở đó bạn có thể gặp nguyên lý quy nạp toán học. Nó như sau:
Một mệnh đề nào đó đúng với mọi n tự nhiên nếu
1. nó hợp lệ cho n = 1 và
2. từ tính hợp lệ của mệnh đề đối với bất kỳ n = k tự nhiên tùy ý nào, suy ra nó đúng với n = k+1.
Trong lập trình, kỹ thuật này được gọi là đệ quy
Đệ quy là một cách xác định một tập hợp các đối tượng theo chính tập hợp đó, dựa trên các trường hợp cơ sở đơn giản đã cho.
Đệ quy cũng sẽ được gọi là thủ tục (hàm) gọi chính nó trực tiếp hoặc thông qua các thủ tục và hàm khác
Một ví dụ về thủ tục đệ quy:
thủ tục Rec(a: integer);
bắt đầu
nếu một > 0 sau đó
Rec(a - 1);
viết(a);
kết thúc;
Về mặt sơ đồ, công việc của đệ quy có thể được biểu diễn bằng một sơ đồ
Thủ tục Rec() được thực thi với tham số 3. Sau đó, bên trong thủ tục có tham số 3, thủ tục có tham số 2 được gọi, v.v., cho đến khi thủ tục có tham số 0 được gọi. tham số 0 được gọi, cuộc gọi đệ quy đã có sẽ không xảy ra và thủ tục với tham số 0 sẽ in số 0 và kết thúc. Sau đó, điều khiển được chuyển trở lại quy trình với tham số 1, nó cũng hoàn thành công việc của mình bằng cách in số 1, v.v. trước thủ tục có tham số 3.
Tất cả các thủ tục được gọi được lưu trữ trong bộ nhớ cho đến khi chúng hoàn thành công việc của mình. Số lượng các thủ tục đồng thời được gọi là độ sâu đệ quy.