บทช่วยสอนเชิงลึกเกี่ยวกับ Recursion ใน Java อธิบายว่า Recursion คืออะไรพร้อมตัวอย่าง ประเภท และแนวคิดที่เกี่ยวข้อง นอกจากนี้ยังครอบคลุม Recursion Vs Iteration:
จากบทเรียนก่อนหน้านี้ของเราใน Java เราได้เห็นแนวทางการวนซ้ำที่เราประกาศการวนซ้ำแล้วสำรวจผ่านโครงสร้างข้อมูลในลักษณะวนซ้ำโดยรับองค์ประกอบหนึ่งที่ หนึ่งครั้ง
เรายังได้เห็นโฟลว์แบบมีเงื่อนไขซึ่งอีกครั้งเราเก็บตัวแปรลูปหนึ่งตัวและทำซ้ำโค้ดหนึ่งชิ้นจนกว่าตัวแปรลูปจะตรงตามเงื่อนไข เมื่อพูดถึงการเรียกใช้ฟังก์ชัน เราได้สำรวจวิธีการวนซ้ำสำหรับการเรียกใช้ฟังก์ชันด้วยเช่นกัน
ในบทช่วยสอนนี้ เราจะหารือเกี่ยวกับแนวทางที่แตกต่างในการเขียนโปรแกรม เช่น แนวทางแบบเรียกซ้ำ
การเรียกซ้ำใน Java คืออะไร
การวนซ้ำเป็นกระบวนการที่ฟังก์ชันหรือเมธอดเรียกตัวเองซ้ำแล้วซ้ำอีก ฟังก์ชันนี้ที่ถูกเรียกใช้ซ้ำแล้วซ้ำอีกไม่ว่าจะทางตรงหรือทางอ้อมเรียกว่า "ฟังก์ชันวนซ้ำ"
เราจะดูตัวอย่างต่างๆ เพื่อทำความเข้าใจการวนซ้ำ ทีนี้มาดูไวยากรณ์ของการเรียกซ้ำกัน
ไวยากรณ์การเรียกซ้ำ
เมธอดใดๆ ที่ใช้การเรียกซ้ำมีสองส่วนพื้นฐาน:
- การเรียกใช้เมธอดซึ่งสามารถเรียกตัวเองได้ เช่น การเรียกซ้ำ
- เงื่อนไขเบื้องต้นที่จะหยุดการเรียกซ้ำ
โปรดทราบว่าเงื่อนไขเบื้องต้นจำเป็นสำหรับวิธีการเรียกซ้ำใดๆ เนื่องจากหากเราไม่ ทำลายrecursion จากนั้นมันจะทำงานต่อไปอย่างไม่มีที่สิ้นสุดและส่งผลให้เกิด stack overflow
ไวยากรณ์ทั่วไปของการเรียกซ้ำมีดังนี้:
methodName (T parameters…) { if (precondition == true) //precondition or base condition { return result; } return methodName (T parameters…); //recursive call } โปรดทราบว่าเงื่อนไขเบื้องต้นยังเรียกว่า สภาพฐาน เราจะหารือเพิ่มเติมเกี่ยวกับเงื่อนไขพื้นฐานในส่วนถัดไป
ทำความเข้าใจเกี่ยวกับ Recursion ใน Java
ในส่วนนี้ เราจะพยายามทำความเข้าใจกระบวนการ Recursion และดูว่าเกิดขึ้นได้อย่างไร เราจะเรียนรู้เกี่ยวกับเงื่อนไขพื้นฐาน สแต็กโอเวอร์โฟลว์ และดูว่าปัญหาเฉพาะสามารถแก้ไขด้วยการเรียกซ้ำและรายละเอียดอื่นๆ ได้อย่างไร
เงื่อนไขพื้นฐานการเรียกซ้ำ
ขณะเขียนโปรแกรมเรียกซ้ำ เราควร ขั้นแรกให้แก้ปัญหาสำหรับกรณีฐาน จากนั้นเราจะแสดงปัญหาที่ใหญ่กว่าในแง่ของปัญหาที่เล็กกว่า
ตามตัวอย่าง เราสามารถใช้ปัญหาคลาสสิกในการคำนวณแฟกทอเรียลของจำนวน ให้ n เป็นจำนวน เราต้องหาแฟกทอเรียลของ n ซึ่งเขียนแทนด้วย n!
ตอนนี้ เรามาปรับใช้โปรแกรมเพื่อคำนวณแฟกทอเรียล n (n!) โดยใช้การเรียกซ้ำ
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); } }ผลลัพธ์
ในโปรแกรมนี้ เราจะเห็นว่าเงื่อนไข (n=1) เป็นเงื่อนไขฐาน และเมื่อถึงเงื่อนไขนี้ ฟังก์ชันจะคืนค่า 1 ส่วนอื่นของฟังก์ชันคือการเรียกซ้ำ แต่ทุกครั้งที่เรียกใช้ recursive method n จะลดลง 1
ดังนั้นเราจึงสรุปได้ว่าในที่สุดค่าของ n จะกลายเป็น 1 หรือน้อยกว่า 1 และ ณ จุดนี้เมธอดจะคืนค่า 1 เงื่อนไขฐานนี้จะถึงและฟังก์ชันจะหยุด โปรดทราบว่าค่าของ n สามารถเป็นอะไรก็ได้ตราบใดที่เป็นไปตามเงื่อนไขพื้นฐาน
การแก้ปัญหาโดยใช้การเรียกซ้ำ
แนวคิดพื้นฐานเบื้องหลังการใช้การเรียกซ้ำคือการแสดงปัญหาที่ใหญ่กว่าในแง่ของ ปัญหาที่เล็กลง นอกจากนี้ เราจำเป็นต้องเพิ่มเงื่อนไขพื้นฐานอย่างน้อยหนึ่งเงื่อนไขเพื่อให้เราสามารถออกจากการเรียกซ้ำได้
สิ่งนี้แสดงให้เห็นแล้วในตัวอย่างแฟกทอเรียลด้านบน ในโปรแกรมนี้ เราแสดงค่า n แฟกทอเรียล (n!) ในแง่ของค่าที่น้อยกว่าและมีเงื่อนไขพื้นฐาน (n =1) ดังนั้นเมื่อ n ถึง 1 เราสามารถออกจากวิธีการเรียกซ้ำได้
Stack Overflow Error In Recursion
เราทราบดีว่าเมื่อมีการเรียกใช้เมธอดหรือฟังก์ชันใดๆ สถานะของฟังก์ชันจะถูกเก็บไว้ในสแต็กและถูกเรียกคืนเมื่อฟังก์ชันส่งคืน สแต็กใช้สำหรับวิธีการเรียกซ้ำเช่นกัน
แต่ในกรณีของการเรียกซ้ำ ปัญหาอาจเกิดขึ้นหากเราไม่กำหนดเงื่อนไขพื้นฐานหรือเมื่อเงื่อนไขพื้นฐานไม่ถึงหรือดำเนินการอย่างใด หากสถานการณ์นี้เกิดขึ้น อาจเกิด stack overflow ได้
ลองพิจารณาตัวอย่างด้านล่างของสัญลักษณ์แฟกทอเรียล
เรากำหนดเงื่อนไขฐานผิด 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); } }ดังนั้นเมื่อ n > 100 เมธอดจะคืนค่า 1 แต่การเรียกซ้ำจะไม่หยุด ค่าของ n จะลดลงไปเรื่อยๆไม่มีเงื่อนไขอื่นใดที่จะหยุดมันได้ สิ่งนี้จะดำเนินต่อไปจนกว่าสแต็กล้น
อีกกรณีหนึ่งคือเมื่อค่าของ n 100. ในกรณีนี้ เมธอดจะไม่เรียกใช้เงื่อนไขพื้นฐานและส่งผลให้เกิดสแต็กโอเวอร์โฟลว์
ตัวอย่างการเรียกซ้ำใน Java
ในส่วนนี้ เราจะใช้ตัวอย่างต่อไปนี้โดยใช้ การเรียกซ้ำ
#1) Fibonacci Series โดยใช้ Recursion
ชุด Fibonacci กำหนดโดย
1,1,2,3,5,8,13,21, 34,55,…
ลำดับข้างต้นแสดงว่าองค์ประกอบปัจจุบันคือผลรวมของสององค์ประกอบก่อนหน้า นอกจากนี้ องค์ประกอบแรกในอนุกรมฟีโบนัชชีคือ 1
ดังนั้นโดยทั่วไป ถ้า n เป็นจำนวนปัจจุบัน ก็จะกำหนดโดยผลรวมของ (n-1) และ (n-2) เนื่องจากองค์ประกอบปัจจุบันแสดงอยู่ในเงื่อนไขขององค์ประกอบก่อนหน้า เราจึงสามารถแสดงปัญหานี้ได้โดยใช้การเรียกซ้ำ
โปรแกรมที่จะใช้ชุดฟีโบนัชชีมีดังต่อไปนี้:
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) + " "); } } } เอาต์พุต
#2) ตรวจสอบว่าตัวเลขเป็นพาลินโดรมหรือไม่โดยใช้การวนซ้ำ
พาลินโดรมคือลำดับที่เท่ากันเมื่อเรา อ่านจากซ้ายไปขวาหรือขวาไปซ้าย
จากเลข 121 เราจะเห็นว่าเมื่อเราอ่านจากซ้ายไปขวาและขวาไปซ้าย มันจะเท่ากัน ดังนั้น เลข 121 จึงเป็นพาลินโดรม
ลองมาอีกเลขหนึ่ง 1242 เมื่อเราอ่านจากซ้ายไปขวา จะเป็น 1242 และเมื่ออ่านจากขวาไปซ้าย จะอ่านว่า 2421 ดังนั้น นี่ไม่ใช่พาลินโดรม
เราใช้โปรแกรม palindrome โดยการกลับค่าหลักของตัวเลขและเปรียบเทียบจำนวนที่กำหนดกับการแทนค่าแบบย้อนกลับซ้ำๆ
โปรแกรมด้านล่างใช้โปรแกรมเพื่อตรวจสอบ palindrome
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."); } } }0 เอาต์พุต 
#3) Reverse String Recursion Java
กำหนดสตริง “Hello” เราต้องย้อนกลับเพื่อให้ สตริงผลลัพธ์คือ “olleH”
ทำได้โดยใช้การเรียกซ้ำ เริ่มจากอักขระตัวสุดท้ายในสตริง เราจะพิมพ์ซ้ำอักขระแต่ละตัวจนกว่าอักขระทั้งหมดในสตริงจะหมด
โปรแกรมด้านล่างใช้การเรียกซ้ำเพื่อย้อนกลับสตริงที่กำหนด
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); } } เอาต์พุต
#4) Binary Search Java Recursion
อัลกอริทึมการค้นหาแบบไบนารีเป็นอัลกอริทึมที่มีชื่อเสียงสำหรับการค้นหา ในอัลกอริทึมนี้ เมื่อกำหนดอาร์เรย์ที่เรียงลำดับขององค์ประกอบ n เราจะค้นหาอาร์เรย์นี้เพื่อหาองค์ประกอบหลักที่กำหนด ในตอนแรก เราแบ่งอาร์เรย์ออกเป็นสองซีกโดยหาองค์ประกอบตรงกลางของอาร์เรย์
จากนั้นขึ้นอยู่กับว่าคีย์ตรงกลางที่เราจำกัดการค้นหาของเราในครึ่งแรกหรือครึ่งหลังของอาร์เรย์ ด้วยวิธีนี้ กระบวนการเดิมซ้ำจนกว่าจะพบตำแหน่งขององค์ประกอบหลัก
เราจะใช้อัลกอริทึมนี้โดยใช้การเรียกซ้ำที่นี่
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); } } เอาต์พุต
#5) หาค่าต่ำสุดในอาร์เรย์โดยใช้การวนซ้ำ
การใช้การเรียกซ้ำทำให้เราสามารถหาค่าต่ำสุดในอาร์เรย์ได้ด้วย
เดอะโปรแกรม Java เพื่อค้นหาค่าต่ำสุดในอาร์เรย์แสดงไว้ด้านล่าง
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"); } }เอาต์พุต
นี่คือบางส่วนของ ตัวอย่างของการเรียกซ้ำ นอกเหนือจากตัวอย่างเหล่านี้ ปัญหาอื่นๆ มากมายในซอฟต์แวร์สามารถนำไปใช้ได้โดยใช้เทคนิคการเรียกซ้ำ
ประเภทการเรียกซ้ำ
การเรียกซ้ำมี 2 ประเภทโดยอิงจากเวลาที่เรียกใช้ recursive method
ได้แก่:
#1) Tail Recursion
เมื่อการเรียก recursive method เป็นคำสั่งสุดท้าย ดำเนินการภายในวิธีการเรียกซ้ำ เรียกว่า "Tail Recursion"
ในการเรียกซ้ำส่วนท้าย คำสั่งเรียกซ้ำมักจะถูกดำเนินการพร้อมกับคำสั่งส่งคืนของวิธีการ
The ไวยากรณ์ทั่วไปสำหรับการเรียกซ้ำส่วนท้ายมีดังต่อไปนี้:
methodName ( T parameters…){ { if (base_condition == true) { return result; } return methodName (T parameters …) //tail recursion } #2) Head Recursion
Head recursion เป็นวิธีเรียกซ้ำใดๆ ที่ไม่ใช่การเรียกซ้ำส่วนท้าย ดังนั้นแม้แต่การเรียกซ้ำทั่วไปก็ยังเป็นการเรียกซ้ำล่วงหน้า
ไวยากรณ์ของการเรียกซ้ำส่วนหัวมีดังนี้:
methodName (T parameters…){ if (some_condition == true) { return methodName (T parameters…); } return result; } การเรียกซ้ำ Vs การวนซ้ำใน Java
| การเรียกซ้ำ | การวนซ้ำ |
|---|---|
| การเรียกซ้ำเป็นกระบวนการที่เมธอดเรียกตัวเองซ้ำๆ จนกว่าจะตรงตามเงื่อนไขพื้นฐาน | การวนซ้ำคือ กระบวนการที่ชิ้นส่วนของโค้ดถูกเรียกใช้ซ้ำๆ ในจำนวนครั้งที่จำกัดหรือจนกว่าจะตรงตามเงื่อนไข |
| เป็นแอปพลิเคชันสำหรับฟังก์ชันต่างๆ | ใช้งานได้ สำหรับลูป |
| ทำงานได้ดีสำหรับขนาดโค้ดที่เล็กลง | ทำงานได้ดีสำหรับขนาดโค้ดที่ใหญ่ขึ้น |
| ใช้หน่วยความจำมากขึ้นเนื่องจากการเรียกซ้ำแต่ละครั้งถูกพุชไปยังสแต็ก | หน่วยความจำน้อยกว่า ถูกใช้ |
| แก้ไขจุดบกพร่องและบำรุงรักษาได้ยาก | แก้ไขจุดบกพร่องและบำรุงรักษาได้ง่ายกว่า |
| ส่งผลให้สแต็กโอเวอร์โฟลว์หากฐาน ไม่ได้ระบุหรือไม่ถึงเงื่อนไข | อาจดำเนินการไม่จำกัดแต่สุดท้ายจะหยุดการดำเนินการโดยมีข้อผิดพลาดของหน่วยความจำใดๆ |
| ความซับซ้อนของเวลาสูงมาก | ความซับซ้อนของเวลาค่อนข้างต่ำ |
คำถามที่พบบ่อย
Q #1) การเรียกซ้ำทำงานใน Java อย่างไร
คำตอบ: ในการเรียกซ้ำ ฟังก์ชันเรียกซ้ำจะเรียกตัวเองซ้ำๆ จนกว่าจะเป็นไปตามเงื่อนไขพื้นฐาน หน่วยความจำสำหรับฟังก์ชันที่เรียกใช้จะถูกผลักไปยังสแต็กที่ด้านบนสุดของหน่วยความจำสำหรับฟังก์ชันที่เรียก สำหรับการเรียกใช้ฟังก์ชันแต่ละครั้ง จะมีการสร้างสำเนาของตัวแปรโลคัลแยกต่างหาก
Q #2) ทำไมจึงใช้ Recursion?
คำตอบ: การเรียกซ้ำใช้เพื่อแก้ปัญหาเหล่านั้นที่สามารถแบ่งออกเป็นปัญหาเล็ก ๆ และปัญหาทั้งหมดสามารถแสดงในรูปของปัญหาที่เล็กกว่าได้
การเรียกซ้ำยังใช้กับปัญหาที่มากเกินไป ซับซ้อนที่จะแก้ไขโดยใช้วิธีการวนซ้ำ นอกจากปัญหาที่ไม่เกี่ยวกับความซับซ้อนของเวลาแล้ว ให้ใช้การเรียกซ้ำ
คำถาม #3) ประโยชน์ของRecursion?
Answer:
ประโยชน์ของ Recursion ได้แก่:
- Recursion ลดการโทรซ้ำซ้อน ของฟังก์ชัน
- การวนซ้ำช่วยให้เราแก้ปัญหาได้ง่ายเมื่อเทียบกับวิธีวนซ้ำ
ถาม #4) อันไหนดีกว่ากัน – การวนซ้ำหรือวนซ้ำ2
คำตอบ: การเรียกซ้ำจะทำการเรียกซ้ำๆ จนกว่าจะถึงฟังก์ชันฐาน ดังนั้นจึงมีโอเวอร์เฮดของหน่วยความจำเนื่องจากหน่วยความจำสำหรับการเรียกใช้ฟังก์ชันแต่ละครั้งถูกผลักไปที่สแต็ก
การวนซ้ำในทางกลับกันไม่มีโอเวอร์เฮดของหน่วยความจำมากนัก การดำเนินการเรียกซ้ำจะช้ากว่าวิธีการวนซ้ำ การวนซ้ำจะลดขนาดของโค้ดในขณะที่วิธีการวนซ้ำทำให้โค้ดมีขนาดใหญ่ขึ้น
คำถาม #5) ข้อดีของการเรียกซ้ำซ้อนซ้ำคืออะไร
คำตอบ:
- การวนซ้ำทำให้รหัสชัดเจนขึ้นและสั้นลง
- การวนซ้ำดีกว่าวิธีการวนซ้ำสำหรับปัญหาต่างๆ เช่น หอคอยฮานอย ต้นไม้ การข้ามผ่าน ฯลฯ
- เนื่องจากการเรียกใช้ฟังก์ชันทุกครั้งมีการพุชหน่วยความจำไปยังสแต็ก การเรียกซ้ำจะใช้หน่วยความจำมากกว่า
- ประสิทธิภาพการเรียกซ้ำจะช้ากว่าวิธีการวนซ้ำ
สรุป
การเรียกซ้ำเป็นแนวคิดที่สำคัญมากในซอฟต์แวร์ โดยไม่คำนึงถึงภาษาการเขียนโปรแกรม การวนซ้ำส่วนใหญ่จะใช้ในการแก้ปัญหาโครงสร้างข้อมูล เช่น หอคอยของฮานอย การข้ามผ่านต้นไม้ รายการที่เชื่อมโยง ฯลฯ แม้ว่าจะใช้หน่วยความจำมากกว่าการเรียกซ้ำทำให้โค้ดง่ายขึ้นและชัดเจนขึ้น
เราได้สำรวจทั้งหมดเกี่ยวกับการเรียกซ้ำในบทช่วยสอนนี้ เรายังได้นำตัวอย่างการเขียนโปรแกรมจำนวนมากมาใช้เพื่อความเข้าใจที่ดีขึ้นของแนวคิด