Hướng dẫn chuyên sâu về Đệ quy trong Java này giải thích Đệ quy là gì với các ví dụ, kiểu và khái niệm liên quan. Nó cũng đề cập đến Đệ quy và Lặp lại:
Từ các hướng dẫn trước của chúng tôi về Java, chúng ta đã thấy cách tiếp cận lặp trong đó chúng ta khai báo một vòng lặp và sau đó duyệt qua cấu trúc dữ liệu theo cách lặp bằng cách lấy một phần tử tại một lần.
Chúng ta cũng đã thấy quy trình có điều kiện trong đó một lần nữa chúng ta giữ một biến vòng lặp và lặp lại một đoạn mã cho đến khi biến vòng lặp đáp ứng điều kiện. Đối với các lệnh gọi hàm, chúng tôi cũng khám phá cách tiếp cận lặp cho các lệnh gọi hàm.
Trong hướng dẫn này, chúng ta sẽ thảo luận về một cách tiếp cận lập trình khác, tức là cách tiếp cận Đệ quy.
Đệ quy trong Java là gì?
Đệ quy là một quá trình trong đó một hàm hoặc một phương thức tự gọi đi gọi lại chính nó. Hàm được gọi đi gọi lại trực tiếp hoặc gián tiếp này được gọi là “hàm đệ quy”.
Chúng ta sẽ xem các ví dụ khác nhau để hiểu về đệ quy. Bây giờ hãy xem cú pháp của đệ quy.
Cú pháp của đệ quy
Bất kỳ phương thức nào thực hiện Đệ quy đều có hai phần cơ bản:
- Lệnh gọi phương thức có thể gọi chính nó tức là đệ quy
- Điều kiện tiên quyết sẽ dừng đệ quy.
Lưu ý rằng điều kiện tiên quyết là cần thiết cho bất kỳ phương thức đệ quy nào, nếu chúng ta không phá vỡthì nó sẽ tiếp tục chạy vô hạn và dẫn đến tràn ngăn xếp.
Cú pháp chung của đệ quy như sau:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } Lưu ý rằng điều kiện tiên quyết cũng được gọi điều kiện cơ sở. Chúng ta sẽ thảo luận thêm về điều kiện cơ sở trong phần tiếp theo.
Hiểu về đệ quy trong Java
Trong phần này, chúng ta sẽ cố gắng hiểu quá trình đệ quy và xem nó diễn ra như thế nào. Chúng ta sẽ tìm hiểu về điều kiện cơ sở, tràn ngăn xếp và xem cách giải quyết một vấn đề cụ thể bằng đệ quy và các chi tiết khác.
Điều kiện cơ sở của đệ quy
Trong khi viết chương trình đệ quy, chúng ta nên đầu tiên cung cấp giải pháp cho trường hợp cơ sở. Sau đó, chúng ta biểu thị bài toán lớn hơn dưới dạng các bài toán nhỏ hơn.
Như một ví dụ, chúng ta có thể lấy một bài toán cổ điển là tính giai thừa của một số. Cho một số n, chúng ta phải tìm một giai thừa của n được ký hiệu là n!
Bây giờ hãy thực hiện chương trình để tính giai thừa n (n!) bằng cách sử dụng đệ quy.
public class Main{ static int fact(int n) { if (n == 1) // base condition return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Kết quả
Trong chương trình này ta thấy điều kiện (n=1) là điều kiện cơ sở và khi đạt đến điều kiện này thì hàm trả về 1 .Phần khác của hàm là lời gọi đệ quy. Nhưng mỗi khi phương thức đệ quy được gọi, n bị giảm đi 1.
Vì vậy, chúng ta có thể kết luận rằng cuối cùng giá trị của n sẽ trở thành 1 hoặc nhỏ hơn 1 và lúc nàyđiểm, phương thức sẽ trả về giá trị 1. Điều kiện cơ bản này sẽ được đáp ứng và chức năng sẽ dừng lại. Lưu ý rằng giá trị của n có thể là bất kỳ giá trị nào miễn là nó thỏa mãn điều kiện cơ bản.
Giải quyết vấn đề bằng đệ quy
Ý tưởng cơ bản đằng sau việc sử dụng đệ quy là diễn đạt vấn đề lớn hơn dưới dạng những vấn đề nhỏ hơn. Ngoài ra, chúng ta cần thêm một hoặc nhiều điều kiện cơ sở để có thể thoát khỏi đệ quy.
Điều này đã được chứng minh trong ví dụ giai thừa ở trên. Trong chương trình này, chúng ta biểu diễn giai thừa n (n!) dưới dạng các giá trị nhỏ hơn và có một điều kiện cơ sở (n =1) để khi n đạt đến 1, chúng ta có thể thoát khỏi phương thức đệ quy.
Lỗi tràn ngăn xếp trong đệ quy
Chúng tôi biết rằng khi bất kỳ phương thức hoặc hàm nào được gọi, trạng thái của hàm được lưu trữ trên ngăn xếp và được truy xuất khi hàm trả về. Ngăn xếp cũng được sử dụng cho phương thức đệ quy.
Nhưng trong trường hợp đệ quy, sự cố có thể xảy ra nếu chúng ta không xác định điều kiện cơ sở hoặc khi điều kiện cơ bản không đạt được hoặc không được thực thi. Nếu tình huống này xảy ra thì có thể phát sinh lỗi tràn ngăn xếp.
Hãy xem xét ví dụ dưới đây về ký hiệu giai thừa.
Ở đây chúng ta đã đưa ra điều kiện cơ sở sai, n==100.
public class Main { static int fact(int n) { if (n == 100) // base condition resulting in stack overflow return 1; else return n*fact(n-1); } public static void main(String[] args) { int result = fact(10); System.out.println("10! = " + result); } }Vì vậy, khi n > 100 phương thức sẽ trả về 1 nhưng đệ quy sẽ không dừng lại. Giá trị của n sẽ tiếp tục giảm vô thời hạn khi cókhông có điều kiện nào khác để ngăn chặn nó. Điều này sẽ tiếp tục cho đến khi tràn ngăn xếp.
Một trường hợp khác sẽ xảy ra khi giá trị của n 100. Trong trường hợp này, phương thức cũng sẽ không bao giờ thực thi điều kiện cơ sở và dẫn đến tràn ngăn xếp.
Ví dụ về đệ quy trong Java
Trong phần này, chúng ta sẽ triển khai các ví dụ sau bằng cách sử dụng đệ quy.
#1) Dãy Fibonacci Sử dụng Đệ quy
Dãy Fibonacci được cho bởi,
1,1,2,3,5,8,13,21, 34,55,…
Dãy trên cho thấy phần tử hiện tại là tổng của hai phần tử trước đó. Ngoài ra, phần tử đầu tiên trong dãy Fibonacci là 1.
Vì vậy, nói chung nếu n là số hiện tại, thì nó bằng tổng của (n-1) và (n-2). Vì phần tử hiện tại được thể hiện dưới dạng các phần tử trước đó, nên chúng ta có thể biểu diễn vấn đề này bằng cách sử dụng đệ quy.
Chương trình triển khai chuỗi Fibonacci được cung cấp bên dưới:
public class Main { //method to calculate fibonacci series static int fibonacci(int n) { if (n = 1) { return n; } return fibonacci(n-1) + fibonacci(n-2); } public static void main(String[] args) { int number = 10; //print first 10 numbers of fibonacci series System.out.println ("Fibonacci Series: First 10 numbers:"); for (int i = 1; i = number; i++) { System.out.print(fibonacci(i) + " "); } } } Đầu ra
#2) Kiểm tra xem một số có phải là một số Palindrome hay không bằng cách sử dụng đệ quy
Một palindrome là một dãy bằng nhau khi chúng ta đọc từ trái sang phải hoặc từ phải sang trái.
Cho số 121, ta thấy khi đọc từ trái sang phải và đọc từ phải sang trái thì bằng nhau. Do đó số 121 là một số đối xứng.
Hãy lấy một số khác, 1242. Khi chúng ta đọc nó từ trái sang phải, nó là 1242 và khi đọc từ phải sang trái, nó đọc là 2421. Vì vậy, đây không phải là một số đối xứng.
Chúng tôitriển khai chương trình bảng màu bằng cách đảo ngược các chữ số của các số và so sánh đệ quy số đã cho với biểu diễn đảo ngược của nó.
Chương trình dưới đây triển khai chương trình kiểm tra bảng màu.
import java.io.*; import java.util.*; public class Main { // check if num contains only one digit public static int oneDigit(int num) { if ((num >= 0) && (num 10)) return 1; else return 0; } //palindrome utility function public static int isPalindrome_util (int num, int revNum) throws Exception { // base condition; return if num=0 if (num == 0) { return revNum; } else { //call utility function recursively revNum = isPalindrome_util(num / 10, revNum); } // Check if first digit of num and revNum are equal if (num % 10 == revNum % 10) { // if yes, revNum will move with num return revNum / 10; } else { // exit throw new Exception(); } } //method to check if a given number is palindrome using palindrome utility function public static int isPalindrome(int num) throws Exception { if (num 0) num = (-num); int revNum = (num); return isPalindrome_util(num, revNum); } public static void main(String args[]) { int n = 1242; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } n = 1221; try { isPalindrome(n); System.out.println("Yes, the given number " + n + " is a palindrome."); } catch (Exception e) { System.out.println("No, the given number " + n + " is not a palindrome."); } } }Đầu ra
#3) Java đệ quy chuỗi đảo ngược
Cho một chuỗi “Xin chào”, chúng ta phải đảo ngược nó để chuỗi kết quả là “olleH”.
Điều này được thực hiện bằng cách sử dụng đệ quy. Bắt đầu từ ký tự cuối cùng trong chuỗi, chúng ta in đệ quy từng ký tự cho đến khi hết tất cả các ký tự trong chuỗi.
Chương trình dưới đây sử dụng đệ quy để đảo ngược một chuỗi đã cho.
class String_Reverse { //recursive method to reverse a given string void reverseString(String str) { //base condition; return if string is null or with 1 or less character if ((str==null)||(str.length() = 1)) System.out.println(str); else { //recursively print each character in the string from the end System.out.print(str.charAt(str.length()-1)); reverseString(str.substring(0,str.length()-1)); } } } class Main{ public static void main(String[] args) { String inputstr = "SoftwareTestingHelp"; System.out.println("The given string: " + inputstr); String_Reverse obj = new String_Reverse(); System.out.print("The reversed string: "); obj.reverseString(inputstr); } } Đầu ra
#4) Đệ quy Java tìm kiếm nhị phân
Thuật toán tìm kiếm nhị phân là một thuật toán tìm kiếm nổi tiếng. Trong thuật toán này, cho trước một mảng n phần tử đã được sắp xếp, chúng ta tìm kiếm phần tử khóa đã cho trong mảng này. Ban đầu, chúng ta chia mảng thành hai nửa bằng cách tìm phần tử ở giữa của mảng.
Sau đó, tùy thuộc vào khóa giữa mà chúng ta giới hạn tìm kiếm ở nửa đầu hoặc nửa sau của mảng. Bằng cách này, quy trình tương tự được lặp lại cho đến khi tìm thấy vị trí của các phần tử chính.
Chúng tôi sẽ triển khai thuật toán này bằng cách sử dụng đệ quy tại đây.
import java.util.*; class Binary_Search { // recursive binary search int binarySearch(int numArray[], int left, int right, int key) { if (right >= left) { //calculate mid of the array int mid = left + (right - left) / 2; // if the key is at mid, return mid if (numArray[mid] == key) return mid; // if key key) return binarySearch(numArray, left, mid - 1, key); // Else recursively search in the right subarray return binarySearch(numArray, mid + 1, right, key); } // no elements in the array, return -1 return -1; } } class Main{ public static void main(String args[]) { Binary_Search ob = new Binary_Search(); //declare and print the array int numArray[] = { 4,6,12,16,22}; System.out.println("The given array : " + Arrays.toString(numArray)); int len = numArray.length; //length of the array int key = 16; //key to be searched int result = ob.binarySearch(numArray, 0, len - 1, key); if (result == -1) System.out.println("Element " + key + " not present"); else System.out.println("Element " + key + " found at index " + result); } } Đầu ra
#5) Tìm giá trị nhỏ nhất trong mảng bằng phương pháp đệ quy
Sử dụng phương pháp đệ quy, chúng ta cũng có thể tìm giá trị nhỏ nhất trong mảng.
CácChương trình Java để tìm giá trị nhỏ nhất trong mảng được cung cấp bên dưới.
import java.util.*; class Main { static int getMin(int numArray[], int i, int n) { //return first element if only one element or minimum of the array elements return (n == 1) ? numArray[i] : Math.min(numArray[i], getMin(numArray,i + 1 , n - 1)); } public static void main(String[] args) { int numArray[] = { 7,32,64,2,10,23 }; System.out.println("Given Array : " + Arrays.toString(numArray)); int n = numArray.length; System.out.print("Minimum element of array: " + getMin(numArray, 0, n) + "\n"); } }Đầu ra
Đây là một số các ví dụ về đệ quy. Ngoài những ví dụ này, rất nhiều vấn đề khác trong phần mềm có thể được thực hiện bằng cách sử dụng các kỹ thuật đệ quy.
Các loại đệ quy
Đệ quy có hai loại dựa trên thời điểm gọi đến phương thức đệ quy.
Đó là:
#1) Đệ quy đuôi
Khi lệnh gọi phương thức đệ quy là câu lệnh cuối cùng được thực thi bên trong phương thức đệ quy, nó được gọi là “Đệ quy đuôi”.
Trong đệ quy đuôi, câu lệnh gọi đệ quy thường được thực thi cùng với câu lệnh trả về của phương thức.
Các cú pháp chung cho đệ quy đuôi được đưa ra dưới đây:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Đệ quy đầu
Đệ quy đầu là bất kỳ cách tiếp cận đệ quy nào không phải là đệ quy đuôi. Vì vậy, ngay cả đệ quy tổng quát cũng là đệ quy trước.
Cú pháp của đệ quy đầu như sau:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } Đệ quy Vs Lặp trong Java
| Đệ quy | Lặp lại |
|---|---|
| Đệ quy là một quá trình trong đó một phương thức tự gọi chính nó nhiều lần cho đến khi đáp ứng một điều kiện cơ sở. | Lặp lại là một quy trình trong đó một đoạn mã được thực thi lặp đi lặp lại trong một số lần hữu hạn hoặc cho đến khi một điều kiện được đáp ứng. |
| Là ứng dụng cho các chức năng. | Có thể áp dụng vòng lặp for. |
| Hoạt động tốt chokích thước mã nhỏ hơn. | Hoạt động tốt với kích thước mã lớn hơn. |
| Sử dụng nhiều bộ nhớ hơn khi mỗi lệnh gọi đệ quy được đẩy vào ngăn xếp | Bộ nhớ tương đối ít hơn được sử dụng. |
| Khó gỡ lỗi và bảo trì | Dễ gỡ lỗi và bảo trì hơn |
| Dẫn đến tràn ngăn xếp nếu cơ sở điều kiện không được chỉ định hoặc không đạt được. | Có thể thực thi vô hạn nhưng cuối cùng sẽ dừng thực thi với bất kỳ lỗi bộ nhớ nào |
| Độ phức tạp về thời gian rất cao. | Độ phức tạp về thời gian tương đối thấp. |
Câu hỏi thường gặp
Hỏi #1) Đệ quy hoạt động như thế nào trong Java?
Trả lời: Trong đệ quy, hàm đệ quy tự gọi chính nó nhiều lần cho đến khi một điều kiện cơ sở được thỏa mãn. Bộ nhớ cho chức năng được gọi được đẩy vào ngăn xếp ở trên cùng của bộ nhớ cho chức năng gọi. Đối với mỗi lệnh gọi hàm, một bản sao riêng biệt của các biến cục bộ được tạo.
Hỏi #2) Tại sao sử dụng Đệ quy?
Trả lời: Đệ quy được sử dụng để giải những bài toán có thể chia nhỏ thành những bài toán nhỏ hơn và toàn bộ bài toán có thể được biểu diễn dưới dạng một bài toán nhỏ hơn.
Đệ quy cũng được sử dụng cho những bài toán quá nhỏ phức tạp được giải quyết bằng cách sử dụng một cách tiếp cận lặp đi lặp lại. Bên cạnh những vấn đề mà độ phức tạp của thời gian không phải là vấn đề, hãy sử dụng đệ quy.
Hỏi #3) Lợi ích củaĐệ quy?
Trả lời:
Lợi ích của Đệ quy bao gồm:
- Đệ quy giảm số lần gọi dư thừa của hàm.
- Đệ quy cho phép chúng ta giải quyết vấn đề dễ dàng khi so sánh với phương pháp lặp.
Hỏi #4) Cái nào tốt hơn – Đệ quy hay Lặp lại?
Trả lời: Đệ quy thực hiện các cuộc gọi lặp đi lặp lại cho đến khi đạt đến hàm cơ sở. Do đó, có một chi phí bộ nhớ khi bộ nhớ cho mỗi lệnh gọi hàm được đẩy vào ngăn xếp.
Mặt khác, phép lặp không có nhiều chi phí bộ nhớ. Thực thi đệ quy chậm hơn so với phương pháp lặp. Đệ quy làm giảm kích thước của mã trong khi cách tiếp cận lặp lại làm cho mã lớn hơn.
Q #5) Ưu điểm của Đệ quy so với Lặp lại là gì?
Trả lời:
- Đệ quy làm cho mã rõ ràng và ngắn hơn.
- Đệ quy tốt hơn cách tiếp cận lặp cho các vấn đề như Tháp Hà Nội, cây truyền tải, v.v.
- Vì mọi lệnh gọi hàm đều có bộ nhớ được đẩy vào ngăn xếp nên Đệ quy sử dụng nhiều bộ nhớ hơn.
- Hiệu suất của đệ quy chậm hơn so với phương pháp lặp.
Kết luận
Đệ quy là một khái niệm rất quan trọng trong phần mềm bất kể ngôn ngữ lập trình. Đệ quy chủ yếu được sử dụng để giải quyết các vấn đề về cấu trúc dữ liệu như tháp Hà Nội, duyệt cây, danh sách được liên kết, v.v. Mặc dù tốn nhiều bộ nhớ hơn,đệ quy làm cho mã đơn giản và rõ ràng hơn.
Chúng ta đã khám phá tất cả về Đệ quy trong hướng dẫn này. Chúng tôi cũng đã triển khai nhiều ví dụ lập trình để hiểu rõ hơn về khái niệm này.