Java Recursion

Java Recursion

การเรียกซ้ำเป็นเทคนิคในการเรียกฟังก์ชันเอง เทคนิคนี้เป็นวิธีการแยกปัญหาที่ซับซ้อนออกเป็นปัญหาง่าย ๆ ซึ่งแก้ไขได้ง่ายกว่า

การเรียกซ้ำอาจเข้าใจยากสักหน่อย วิธีที่ดีที่สุดในการค้นหาวิธีการทำงานคือการทดลองกับมัน

ตัวอย่างการเรียกซ้ำ

การบวกตัวเลขสองตัวเข้าด้วยกันนั้นทำได้ง่าย แต่การเพิ่มช่วงของตัวเลขนั้นซับซ้อนกว่า ในตัวอย่างต่อไปนี้ การเรียกซ้ำจะใช้เพื่อเพิ่มช่วงของตัวเลขเข้าด้วยกัน โดยแยกย่อยเป็นงานง่าย ๆ ในการเพิ่มตัวเลขสองตัว:

public class Main {
  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
  public static int sum(int k) {
    if (k > 0) {
      return k + sum(k - 1);
    } else {
      return 0;
    }
  }
}

ตัวอย่างที่อธิบาย

เมื่อsum()เรียกใช้ฟังก์ชัน จะเพิ่มพารามิเตอร์kลงในผลรวมของตัวเลขทั้งหมดที่น้อยกว่าkและส่งกลับผลลัพธ์ เมื่อ k กลายเป็น 0 ฟังก์ชันจะคืนค่า 0 เมื่อรัน โปรแกรมจะทำตามขั้นตอนเหล่านี้:

เนื่องจากฟังก์ชันไม่เรียกตัวเองเมื่อkเป็น 0 โปรแกรมจึงหยุดอยู่ที่นั่นและส่งคืนผลลัพธ์

สภาพการหยุดชะงัก

เช่นเดียวกับที่ลูปสามารถพบปัญหาของการวนซ้ำแบบอนันต์ ฟังก์ชันแบบเรียกซ้ำสามารถพบปัญหาการเรียกซ้ำแบบอนันต์ได้ การเรียกซ้ำแบบไม่มีที่สิ้นสุดคือเมื่อฟังก์ชันไม่เคยหยุดเรียกตัวเอง ทุกฟังก์ชันแบบเรียกซ้ำควรมีเงื่อนไขหยุด ซึ่งเป็นเงื่อนไขที่ฟังก์ชันหยุดเรียกตัวเอง ในตัวอย่างก่อนหน้านี้ เงื่อนไขการหยุดคือเมื่อพารามิเตอร์kกลายเป็น 0

การดูตัวอย่างต่างๆ ที่หลากหลายเพื่อให้เข้าใจแนวคิดดีขึ้นจะเป็นประโยชน์ ในตัวอย่างนี้ ฟังก์ชันจะเพิ่มช่วงของตัวเลขระหว่างจุดเริ่มต้นและจุดสิ้นสุด เงื่อนไขการหยุดทำงานแบบเรียกซ้ำนี้คือเมื่อendไม่เกินstart :

public class Main {
  public static void main(String[] args) {
    int result = sum(5, 10);
    System.out.println(result);
  }
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end;
    }
  }
}