Đệ quy là một khái niệm cơ bản trong ngôn ngữ lập trình. Trong tư duy giải quyết vấn đề nó mang lại hiệu quả rất lớn. Đệ quy đã giúp giải được rất nhiều bài toán khó. Cùng tìm hiểu thuật toán này và tính độ phức tạp của thuật toán đệ quy trong một bài toán ví dụ dưới đây nhé.
Tóm Tắt
Định nghĩa đệ quy là gì ?
Trước tiên chúng ta cùng đi tìm hiểu khái niệm về đệ quy. Nếu một đối tượng được mô tả thông qua định nghĩa của chính nó thì ta gọi đó là đệ quy. Các đối tượng này sẽ được định nghĩa một cách quy nạp từ những khái niệm đơn giản và gần giống với nó. Để dễ hiểu bạn có thể liên tưởng đến con búp bê Matryoshka truyền thống của Nga. Trông đơn giản vậy nhưng nó là một khái niệm khá căn bản trong bất kỳ ngôn ngữ lập trình nào. Đó chính là khái niệm về “đệ quy”.
Các ví dụ về đệ quy
Ví dụ đầu tiên về đệ quy.
Như ta đã biết số 0 được coi là một số tự nhiên. Nếu k là một số tự nhiên khác thì k + 1 cũng được cho là một số tự nhiên. Từ đó ta sẽ có là: 1 + 2 = 3, 3 + 1 = 4 cũng được coi là một số tự nhiên. Cứ như vậy cộng thêm một, số tự nhiên sau sẽ lớn hơn số tự nhiên khác. Vậy nên, chính số tự nhiên cũng đã mang trong mình bản chất đệ quy.
Ví dụ thứ hai về đệ quy
Hãy cùng định nghĩa giai thừa của n (n!). Ta có:
· Ta có 0!=1khi n=0
· Ta có n!=(n-1)! x n khi n>0
Từ đó ta có kết luận : 1! = 0! x 1, 2! = 1! x 2,… Vì thế, chính giai thừa cũng là một khái niệm mang tính đệ quy.
Bài toán đệ quy như thế nào?
Câu trả lời rất đơn giản: Bài toán đệ quy là những bài toán mang bản chất đệ quy. Những bài toán này sẽ được phân tách ra các bài toán nhỏ hơn. Những bài toán nhỏ này có mang tính chất đơn giản hơn nhưng vẫn cùng dạng thức với bài toán ban đầu. Những bài mới này lại tiếp tục phân tách cho tới khi bài toán cuối cùng nhỏ nhất, không thể phân tách được nữa và suy ra ngay kết quả. Cách phân tách như vậy ngôn ngữ chuyên ngành gọi là “divide and conquer”, dịch ra tiếng Việt có nghĩa là “chia để trị”. Đây chính là một dạng của đệ quy.
Hàm đệ quy trong lập trình là gì?
Nếu bên trong thân của một hàm có một lời gọi đến chính nó thì hàm đó được gọi là hàm đệ quy. Nghe có vẻ vô lý vì một hàm nếu gọi nó mãi mãi thì nó sẽ sinh ra một vòng lặp vô tận, không giới hạn. Tuy nhiên, trên thực tế, luôn có một “điểm neo” trong một hàm đệ quy. Một vài người gọi đây là điều kiện đừng. Khi đạt tới điểm neo này, hàm đệ quy sẽ không gọi chính nó nữa.
Khi hàm đệ quy được gọi, nó sẽ được truyền cho một tham số. Tham số này là kích thước của bài toàn gốc ban đầu. Sau mỗi lần giải hàm đó, tham số sẽ nhỏ dần nhỏ dần. Điều này cũng có nghĩa là bài toán đã đơn giản và nhỏ hơn rồi. Tới khi tham số đạt tới giá trị cực tiểu tại chính điểm neo, hàm đệ quy sẽ hoàn thành và chấm dứt tại đây.
Trong ngôn ngữ lập trình, để giải quyết một bài toán bằng đệ quy thì bài toán phải có khả năng phân tách thành những bài toán cùng dạng và đơn giản hơn bài toán gốc.
Tính độ phức tạp cho các hàm đệ quy (ký hiệu là Big O) dưới đây:
int recursiveFun1(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun1(n-1);
}
int recursiveFun2(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun2(n-5);
}
int recursiveFun3(int n)
{
if (n <= 0)
return 1;
else
return 1 + recursiveFun3(n/5);
}
void recursiveFun4(int n, int m, int o)
{
if (n <= 0)
{
printf(“%d, %d\n”,m, o);
}
else
{
recursiveFun4(n-1, m+1, o);
recursiveFun4(n-1, m, o+1);
}
}
int recursiveFun5(int n)
{
for (i = 0; i < n; i += 2) {
// do something
}
if (n <= 0)
return 1;
else
return 1 + recursiveFun5(n-5);
Gợi ý cách giải:
Theo ký hiệu Big O thì độ phức tạp thời gian cho mỗi hàm theo thứ tự số như sau:
– Hàm thứ nhất đang được gọi đệ quy n khi đến trường hợp cơ sở. Chính vì vậy O(n) của nó thường sẽ được gọi là tuyến tính.
– Hàm thứ hai ta sẽ gọi là n-5 cho mỗi lần. Do đó trước khi gọi hàm chúng tôi trừ năm từ n. Tuy nhiên n-5 cũng là O(n). Trên thực tế chúng được gọi là thứ tự của n/5 lần. Tương tự O(n/5) = O(n).
– Ở hàm thứ 3, ta xác định hàm này là log (n) cơ sở 5. Lý do là vì mỗi lần chúng ta chia cho 5 trước khi gọi hàm nên O(log(n)) (cơ sở 5). Đây thường được gọi là logarit. Do đó hầu hết các phân tích độ phức tạp và ký hiệu Big O thường sử dụng cơ sở 2.
– Trong hàm thứ tư, đó chính làO(2^n) hoặc hàm mũ. Trừ khi nó được đệ quy n lần thì mỗi hàm gọi chính nó hai lần
– Chuyển sang hàm cuối cùng: vòng lặp for mất n/2 vì chúng ta tăng thêm 2 và đệ quy mất n-5. Cũng vì vòng lặp for được gọi đệ quy nên độ phức tạp thời gian nằm trong (n-5) * (n/2) = (2n-10) * n = 2n ^ 2- 10n. Hành vi tiệm cận trên cũng như việc cân nhắc trường hợp xấu nhất hoặc giới hạn trên mà O lớn đang cố gắng. Ở đây ta chỉ nên quan tâm về thuật ngữ lớn nhất. Do đó O(n^2).
Qua bài viết trên của tôi, hy vọng các bạn cũng đã hiểu được khái niệm cơ bản của đệ quy, hàm đệ quy cũng như các tính độ phức tạp của thuật toán đệ quy. Hẹn gặp các bạn vào các bài viết tiếp theo.
