Đệ quy

Hãy nhìn vào tấm hình sau

Phía bên trong bức ảnh chứa một phiên bản của chính nó, và bên trong phiên bản đó, tiếp tục chứa một phiên bản nữa của chính nó. Điều này được lặp đi lặp lại, cho chúng ta một khái niệm trực quan về đệ quy.

Ví dụ toán học về đệ quy

Cho hàm f(n) được định nghĩa như sau:

f(n)=1+2+3+...+n

Đồng nghĩa với: 

f(n−1)=1+2+3+...+n−1

⇒f(n)=n+f(n−1)

Tất nhiên ta có thể tính biểu thức trên bằng công thức toán học f(n)=n×(n+1)2, nhưng tạm thời ta không xét nó ở đây.

Qua chứng minh trên ta rút ra được 1 điều: để tính f(n), ta có thể tính từ f(n−1). Vậy làm sao để tính f(n−1)? Tương tự, ta có thể tính nó từ f(n−2), và rồi ta sẽ tính f(n−2) từ f(n−3), ...

Bên trong bài toán  trên chứa một phiên bản nhỏ hơn của chính nó, trong tin học, khái niệm này gọi là đệ quy.

Tuy nhiên, nếu chỉ tìm đáp án từ biểu thức f(n)=f(n−1)+n, các biểu thức trên có thể lặp lại vô hạn, vì thế chúng ta phải thêm điều kiện sau vào bài toán:

Giá trị khởi đầu của biểu thức là f(0)=0, với n<0, bài toán không có lời giải.

Tới lúc này, vòng lặp vô hạn đã có điểm dừng, nghĩa là với 1 số nguyên dương cho trước, dù bạn có lặp đi lặp lại bao nhiêu lần thì một lúc nào đó các bước tính cũng dừng lại mà thôi.

Đây chính là định nghĩa về đệ quy, hay nói tổng quát:

Đệ quy là một hành động được định nghĩa bằng chính nó.

...Hoặc đó là cách mọi người vẫn hay viết. Mình sẽ viết lại nó như sau:

Đệ quy là một chuỗi các hành động y hệt nhau được lặp đi lặp lại và có điểm dừng. Nếu không có điểm dừng, bài toán trở thành một vòng lặp vô tận.

Code đệ quy cho bài toán trên

Đoạn code sau minh họa cho một vòng lặp vô tận:

#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
	return n + f(n - 1);
}
int main()
{
	int n;
	cin >> n;
	int answer = f(n);
        cout << answer << '\n';
}

Vòng lặp trên sẽ chạy tới vô tận. Ta cần thêm điểm dừng cho nó.

Code đệ quy đầy đủ:

#include <bits/stdc++.h>
using namespace std;
int f(int n)
{
	if (n == 0) return 0;
	return n + f(n - 1);
}
int main()
{
	int n;
	cin >> n;
	int answer = f(n);
        cout << answer << '\n';
}

Ưu điểm: 

• Là thuật toán cơ bản nhất trong các loại thuật toán, ai cũng dùng được.
• Gọn, dễ nhìn, dễ hiểu.
• Là phần lõi cơ bản của nhiều thuật toán khác.

Nhược điểm: tốn bộ nhớ, khó debug, chạy lâu vl. Học thì học thế thôi chứ nếu dùng được thuật toán khác thì bạn nên dùng nó. Bài toán trên chạy đến 10,100,1000,10000 còn được chứ chạy tới 109 thì đời nào mới xong, cứ sử dụng công thức f(n)=n×(n+1)2 là tính được ngay lập tức, đỡ mất công chờ đợi.

Một vài ví dụ về đệ quy

Tính số Fibonacci thứ n bằng đệ quy:

#include <bits/stdc++.h>
using namespace std;
int fibonacci(int n)
{
	if (n == 1) return 1;
	if (n == 2) return 1;
	return fibonacci(n - 1) + fibonacci(n - 2);
}
int main()
{
	int n;
	cin >> n;
	int answer = fibonacci(n);
        cout << answer << '\n';
}

Tìm số ước của một số bằng đệ quy:

#include <bits/stdc++.h>
using namespace std;
int divisors(int n, int i)
{
	if (i == 1) return 1;
	if (n % i == 0) return 1 + divisors(n, i - 1);
	else return divisors(n, i - 1);
}
int main()
{
	int n;
	cin >> n;
	int answer = divisors(n, n);
	cout << answer << '\n';
}

Tổng kết: đệ quy là một trong những thuật toán cơ bản nhất của lập trình nói chung. Nó rất dễ đọc, tuy nhiên hạn chế của nó cũng rất nhiều, khi không cần thiết bạn nên tránh đệ quy và thay vào đó là sử dụng những thuật toán khác.