Nếu thấy khó hiểu với khái niệm đệ quy, hãy liên tưởng đến búp bê Matryoshka
Trong bài dịch này ta hãy cùng tìm hiểu về các đặc điểm của đệ quy và học cách sử dụng đệ quy để giải quyết vấn đề với ngôn ngữ lập trình Java.
Bạn đang đọc: Khái niệm đệ quy trong lập trình
Tóm Tắt
1. Hiểu đơn giản đệ quy là gì?
Trước tiên ta cần hiểu phương pháp trước, trong lập trình, phương pháp là tập hợp những lệnh với tham số truyền vào để máy tính thao tác lệnh theo ý muốn của người viết, đệ quy xảy ra khi người viết những phương pháp tự gọi ( hoạc định nghĩa lại ) chính nó .Xem ví dụ đơn thuần sau nhé. Đề bài : Tính lũy tiến từ 0 đến n .
public int sum(
int n
) {
if (n >= 1) {
return sum(n - 1) + n;
}
return n;
}
Giải thích :
- Bạn truyền một tham số n vào phương thức sum(), lệnh trong phương thức sum sẽ trả về tham số n bạn truyền vào khi chạy hết chương trình “return n”.
- Để đến được bước đó, chương trình sẽ chạy qua các lệnh điều kiện “if(n>=1)” để định nghĩa lại phương thức sum một lần nữa “sum(n-1) + n”, phương thức mới sẽ khiến giá trị n sẽ thay đổi theo từng vòng của điều kiện cho đến khi không còn thỏa mãn điều kiện được cho.
- Khi chương trình “return n” thì n chính là giá trị đã được tính ở phương thức ta đặt điều kiện bên trên.
Như vậy, hai yếu tố cần để triển khai một phương pháp đệ quy là :
- Có điều kiện dừng: Xác định quy luật của phương thức và tìm giá trị cụ thể khi thỏa mãn một điều kiện nhất định, ở bước này vẫn chưa có phương thức đệ quy nào được gọi.
- Phương thức đệ quy: Phương thức đệ quy sẽ gọi lại chính nó cho đến khi nó trả về điều kiện dừng ở bước 1.
Tưởng tượng, mỗi lần bạn sử dụng đệ quy, chương trình chạy một vòng và bộ nhớ Stack sẽ được chồng thêm một lớp tài liệu, thực trạng tiêu tốn lãng phí bộ nhớ rất dễ xảy ra nếu bạn không nghiên cứu và phân tích kỹ những vòng chạy đệ quy để có giám sát hài hòa và hợp lý. Vấn đề trên hoàn toàn có thể xử lý bằng cách “ tối ưu hóa đòn kích bẩy đệ quy đuôi ” .
Viết code bất cẩn, sẽ có n số khung đệ quy ghi đè lên bộ nhớ Stack
2. Đệ quy đuôi và đệ quy đầu
Vậy câu hỏi đặt ra là đệ quy đuôi khác với đệ quy đầu ở đâu. Chúng ta gọi là đệ quy đuôi khi phương pháp đệ quy được đặt ở cuối, sau khi chương trình chạy qua điều kiện kèm theo dừng. Còn lại thì ta gọi đó là đệ quy đầu. Ví dụ, phương pháp ở phần 2 là đệ quy đầu, giờ hãy cùng liên tục đổi khác một chút ít và ta có phương pháp đệ quy đuôi tính lũy tiến từ currentSum đến n :
public int tailSum(int currentSum, int n)
{
if (n <= 1) {
return currentSum + n;
}
return tailSum(currentSum + n, n - 1)
;
}
Như vậy với phương pháp đệ quy đuôi, phương pháp đệ quy sẽ được chương trình ưu tiên giải quyết và xử lý dứt điểm. Chương trình sẽ không phải chạy nhiều vòng giải quyết và xử lý điều kiện kèm theo như phương pháp đệ quy đầu, nên theo logic, rủi ro tiềm ẩn tràn bộ nhớ Stack sẽ được giảm thiểu .
3. So sánh giữa đệ quy và vòng lặp
Ưu điểm lớn nhất của phép đệ quy là tiếp cận giải quyết và xử lý yếu tố bằng những đoạn code sạch, ngăn nắp, dễ đọc, dễ hiểu. Nhược điểm rõ ràng là rủi ro tiềm ẩn cao tràn bộ nhớ Stack như đã lý giải ở trên .Cùng xử lý một bài toán nhưng một giải pháp khác để thay thế sửa chữa đệ quy là sử dụng vòng lặp .Đề bài giống với bài toán tính lũy tiến n ở trên, ta có cách xử lý với vòng lặp như sau :
public int iterativeSum(int n) {
int sum = 0;
if(n < 0) {
return 0;
}
for(int i=0; i<=n; i++) {
sum += i;
}
return sum;
}
Dù vòng lặp có một ưu điểm là chỉ có một vòng duy nhất được gọi ra và ta sẽ không phải lo nghĩ gì về vấn đề tràn bộ nhớ Stack. Nhưng vòng lặp cũng có một nhược điểm so với đệ quy là code xử lý sẽ viết dài và phức tạp hơn.
Xem thêm: Sau require là To V hay Ving?
4. Các ví dụ mở rộng của đệ quy
Sức mạnh thật sự của đệ quy là thay vì bạn phải phong cách thiết kế những thuật toán dài dòng với vòng lặp, đệ quy được cho phép ta vận dụng những tư duy toán học trực tiếp vào thuật toán một cách thuận tiện .Đề bài : Nhập giá trị n và tìm đơn vị chức năng của 10 n
| Lũy thừa | 100 | 101 | 102 | 103 | … | 10n-1 | 10n |
| Đơn vị | 1 | 10 | 100 | 1000 | … | … | … |
Để xử lý bài toán, ta thực thi những bước sau :
- Trước tiên phân tích quy luật của bài toán, để tính giá trị của 10n ta sẽ phải tính giá trị của 10n-1 * 10 trước.
- Nhưng để được giá trị của 10n-1 thì ta sẽ phải tính đơn vị 10(n-1)-1 trước.
- Cứ vậy ta xác định được số hai số cuối sẽ là 101 = 10 và 100 = 1. Đây chính là “điều kiện dừng”, khi đã xác định được điều kiện dừng, thì việc còn lại chỉ là thiết kế phương trình đệ quy phù hợp.
- Từ phân tích trên, ta sẽ đưa ra 2 trường hợp với n = 0 và n>0 (đây sẽ là trường hợp ta sử dụng đệ quy).
public int powerOf10
(int n)
{
if (n == 0) {
return 1;
}
return powerOf10(n- 1) * 10;
}
5. Dãy Fibonacci và đệ quy
Dãy Fibonacci là dãy vô hạn những số tự nhiên khởi đầu bằng hai thành phần 0 và 1, dãy được thiết lập theo quy tắc mỗi thành phần luôn bằng tổng hai thành phần trước nó, ta có dãy Fibonacci sau : 0 1 1 2 3 5 8 13 21 34 55 …
| Dãy số Fibonacci | 0 | 1 | 1 | 2 | 3 | 5 | 8 | … | … |
| Số thứ tự | 1 | 2 | 3 | 4 | 5 | 6 | 7 | … | n |
Tìm số Fibonacci tương ứng với số thứ tự n, để sử dụng đệ quy tìm được số Fibonacci tương ứng, ta sẽ cần xác lập quy luật và điều kiện kèm theo dừng trước của dãy số Fibonacci .
- Quy luật, ta nhận thấy số n sẽ là tổng của 2 chữ số đứng sau nó là (n-2) + (n-1).
- Và ta biết chắc chắn rằng n1 = 0 và n2= 1 là điều kiện dừng của dãy số.
- Như vậy, ta sẽ chia làm 2 trường hợp và thực hiện phương thức đệ quy như sau:
public int fibonacci(int n) {
if (n <= 1) {
return n;
}
return fibonacci(n-1) + fibonacci(n-2);
}
6. Biểu diễn số thập phân dưới dạng nhị phân với đệ quy
Thử đặt ra đề bài với trường hợp khi ta muốn chuyển 1 số ít từ dạng thập phân n sang dạng nhị phân, tựa như như những bước trên ta thực thi :
- Xác định được quy luật của chuyển đổi từ số thập phân sang nhị phân là chia số n cho 2, giữ lại phần dư (0 hoạc là 1), tiếp tục lấy thương chia tiếp cho 2 cho đến khi trở về trường hợp 1 chia cho 2 (0 dư 1).
- Xác định điều kiện dừng của quy luật là khi số n = 0, ta có 0 chia 2 vẫn là 0 và n = 1, 1 chia cho 2 bằng 0 dư 1.
- Như vậy ta chia ra làm 2 trường hợp và thực hiện phép đệ quy như sau:
public String toBinary(int n)
{
if (n <= 1 ) {
return String.
valueOf(n)
;
}
return toBinary(n / 2)
+ String.
valueOf(
n
% 2);
}
7. Kết luận
Đệ quy là một khái niệm cơ bản trong lập trình và đầy hiệu suất cao trong tư duy xử lý yếu tố. Rất nhiều bài toán sau khi được nghiên cứu và phân tích hoàn toàn có thể được xử lý bằng đệ quy và đồng thời nhiều bài toán khác nếu tiếp cận với đệ quy sẽ tiết kiệm chi phí được rất nhiều đoạn code dài dòng .Thường xuyên rèn luyện xử lý yếu tố với đệ quy sẽ trợ giúp là rất hữu dụng cho tư duy thuật toán của những lập trình viên mới vào nghề, khi mà họ nên học chiêu thức tiếp cận và giải quyết và xử lý yếu tố một cách logic và ngăn nắp nhất hoàn toàn có thể .
Lập trình Web Java FullStack cho người mới mở màn
Source: https://final-blade.com
Category : Kiến thức Internet
