Recursion ใน Java: การทำงานและตัวอย่าง

ในการเขียนโปรแกรม Recursion (การเรียกซ้ำ) หมายถึงกระบวนการที่ฟังก์ชันเรียกตัวเองโดยตรงหรือโดยอ้อม ใช้แก้ปัญหาหลายอย่างในวิทยาการคอมพิวเตอร์

Java รองรับการสร้าง recursive methods (เมธอดที่เรียกตัวเอง) บทช่วยสอนนี้อธิบาย recursion ทำงานอย่างไร และสร้าง recursive function ใน Java ยังไง จบแล้วคุณจะเขียน recursive methods ได้อย่างมืออาชีพ

เมธอดใน Java

เมธอด (หรือฟังก์ชัน) คือบล็อกโค้ดทำหน้าที่เฉพาะ เช่น คำนวณผลรวมอาร์เรย์ หรือพิมพ์เนื้อหาอาร์เรย์

ไวยากรณ์เมธอด:

modifier static returnType methodName (Parameters) { 
    // Method body 
}

ตัวอย่างเมธอดพิมพ์ "It's Wednesday!...":

class Main { 
    public static void printItsWednesday() { 
        System.out.println("It's Wednesday! We're half-way through the week!"); 
    } 
    public static void main(String[] args) { 
        printItsWednesday(); 
    } 
}

เรียก printItsWednesday() -> พิมพ์ข้อความออกมา

Java Recursion

Recursive methods = เมธอดที่ถูกเรียกใน main ก่อน แล้วเรียกตัวเองภายในเมธอด ไวยากรณ์:

static void executeMethod() { 
    // Code here 
    executeMethod(); // recursive call 
    // Code here 
} 
public static void main(String[] args) { 
    executeMethod(); // normal call 
}

รันโปรแกรม -> executeMethod() ถูกเรียกใน main -> รันโค้ดในเมธอด ซึ่งรวมถึงการเรียก executeMethod() อีกครั้ง -> เข้าลูป

โปรแกรมทำซ้ำ executeMethod() จนกว่าจะมีเงื่อนไขหยุด ถ้าไม่มีเงื่อนไขหยุด -> infinite recursion (เรียกซ้ำไม่มีที่สิ้นสุด)

ทำไมใช้ Recursion?

1. ลด time complexity ในบางกรณี
2. ทำให้อัลกอริทึมบางอย่างอ่านง่ายและดูแลรักษาง่ายกว่า

ตัวอย่างโปรแกรมที่มักเขียนแบบ recursion:

• คำนวณลำดับฟีโบนัชชี (Fibonacci)
• กลับสตริง (Reverse string)
• คำนวณแฟกทอเรียล (Factorial)
• คำนวณความสูง Binary Tree

ข้อควรระวัง: Recursion อาจช้ากว่าเมธอดทั่วไป เพราะสร้าง storage location ใหม่สำหรับตัวแปรทุกครั้งที่ recursive call

ตัวอย่าง Recursion ใน Java

1. กลับสตริงด้วย Recursion

โปรแกรมสำหรับครูมัธยมต้น กลับสตริงเกรดนักเรียน ตัวแรก = เกรดแรก ตัวสุดท้าย = เกรดล่าสุด ต้องการกลับให้เกรดล่าสุดอยู่หน้าสุด

public class ReverseGrades { 
    public static String reverse(String grades) { 
        if (grades.isEmpty()) 
            return grades; 
        return reverse(grades.substring(1)) + grades.charAt(0); 
    } 
    public static void main(String[] args) { 
        String grades = "CBCBAABACAABA"; 
        String reverse_grades = reverse(grades); 
        System.out.println("This student's grades for the year are: " + reverse_grades); 
    } 
}

ผลลัพธ์: This student's grades for the year are: ABAACABAABCBC

อธิบาย: ฟังก์ชัน reverse() recursive ตรวจสอบ grades ว่างไหม ว่าง -> return grades (หยุด recursion) ไม่ว่าง -> เรียก reverse() อีกครั้งกับ substring(1) (ตัดตัวแรกออก) แล้วต่อ charAt(0) (ตัวแรก) ไปด้านขวา ทำซ้ำจนหมดสตริง

2. คำนวณแฟกทอเรียลด้วย Recursion

แฟกทอเรียล (Factorial) = ผลคูณจำนวนเต็มบวกทั้งหมด <= ตัวเลขนั้น เช่น 5! = 5×4×3×2×1 = 120 เหมาะกับ recursion เพราะมีการคำนวณซ้ำ

โปรแกรมคำนวณ 7! :

class Main { 
    static int calculateFactorial(int number) { 
        if (number != 0) 
            return number * calculateFactorial(number-1); 
        else 
            return 1; 
    } 
    public static void main(String[] args) { 
        int num = 7; 
        int answer = calculateFactorial(num); 
        System.out.println("The factorial of 7 is: " + answer); 
    } 
}

ผลลัพธ์: The factorial of 7 is: 5040

อธิบาย: calculateFactorial() คูณ number กับผลลัพธ์ calculateFactorial(number-1) ทำซ้ำจน number == 0 -> return 1 ส่งค่ากลับ main คำนวณ 7×6×5×4×3×2×1 = 5040

สรุป

Recursion = แนวคิดที่เมธอดเรียกตัวเอง เหมาะกับงานที่ทำซ้ำและใช้ผลลัพธ์รอบก่อน คำนวณรอบปัจจุบัน บทช่วยสอนนี้อธิบายพื้นฐาน recursion ใน Java และสร้าง recursive methods พร้อม 2 ตัวอย่าง: กลับสตริง และ คำนวณแฟกทอเรียล ตอนนี้คุณพร้อมทำงานกับ recursive methods ใน Java อย่างมืออาชีพแล้ว!