1. Một số ví dụ về Đệ quy

a) Đối tượng Đệ quy trong cuộc sống

Bộ búp bê Matryoshka truyền thống của Nga gồm nhiều con có kích thước giảm dần, con nhỏ hơn được đặt bên trong con lớn hơn một cách lần lượt. Số lượng búp bê của bộ bằng 1 cộng với số lượng búp bê có trong búp bê lớn nhất.

Hiệu ứng hình ảnh vô cực là ví dụ giúp liên tưởng rõ ràng đến đệ quy (hình bên trái). Khi soi vào hai tấm gương song song, bạn sẽ thấy hình ảnh phản chiếu của mình, đồng thời cũng nhìn thấy hình ảnh phản chiếu của tấm gương kia phía sau bạn. Trong hình ảnh phản chiếu đó, bạn thấy một hình ảnh phản chiếu nhỏ hơn của mình, và trong đó tiếp tục là những hình ảnh phản chiếu nhỏ hơn nữa... Cứ thế, quá trình này lặp đi lặp lại, những hình ảnh phản chiếu ngày càng trải dài về phía xa và nhỏ hơn. Hiện tượng này khác biệt với hiện tượng phản chiếu trong không gian 2 chiều (hình bên phải).

b) Đệ quy trong Toán học

Dãy số Fibonacci là dãy vô hạn các số tự nhiên bắt đầu bằng 0 và 1, sau đó các số tiếp theo sẽ bằng tổng của 2 số liền trước nó.

Công thức sinh dãy đến giá trị n:

F(n) = F(n−1) + F(n− 2) nếu n > 2; F(0) = 0; F(1) = 1

Nếu cứ gọi đến hàm F(n) mà không có điểm dừng sẽ xảy ra tính vô hạn nên ta phải bổ sung trường hợp đặc biệt được tính toán sẵn là hàm F(0) = 0; F(1) = 1.

2. Khái niệm Đệ quy

⚡Định nghĩa đệ quy của một đối tượng là sự mô tả cách xây dựng đối tượng từ các phiên bản nhỏ hơn của chính đối tượng đó.

Như vậy, định nghĩa đệ quy của một đối tượng bao gồm hai phần sau:

• Phần cơ sở: phần định nghĩa đối tượng khi nó đã ở kích thước nhỏ nhất (không thể hoặc không cần thiết chia nhỏ hơn nữa).
• Phần đệ quy: phần chứa quy tắc để xây dựng đối tượng mới từ một đối tượng hoặc một số đối tượng cùng dạng có kích thước nhỏ hơn.