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

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

โครงสร้างทั่วไปของฟังก์ชันแบบเรียกซ้ำมีลักษณะดังนี้:

(define (function-name args)
  (if (base-condition)
    base-result
    (recursive-call)))

• เงื่อนไขพื้นฐาน: หยุดการเรียกซ้ำ
• ผลลัพธ์พื้นฐาน: ค่าที่ส่งคืนเมื่อตรงตามเงื่อนไขฐาน
• การเรียกซ้ำ: การเรียกใช้ฟังก์ชันด้วยอาร์กิวเมนต์ที่แก้ไข ซึ่งย้ายการคำนวณให้ใกล้กับกรณีพื้นฐานมากขึ้น

ตัวอย่าง: ผลรวมของตัวเลข (1 ถึง n)

ฟังก์ชันเรียกซ้ำอย่างง่ายในการคำนวณผลรวมของตัวเลขตั้งแต่ 1 ถึง n:

(define (sum-to-n n)
  (if (= n 0)                  ; กรณีฐาน: หยุดเมื่อ n เป็น 0
    0                          ; ผลลัพธ์ฐาน: ผลรวมเป็น 0
    (+ n (sum-to-n (- n 1))))) ; เรียกซ้ำ: รวม n ปัจจุบันกับผลลัพธ์ของปัญหาย่อยที่เล็กกว่า

วิธีการทำงาน: การพังทลายและการประกอบกลับคืน

ผlรวมต่อ: “done”

ติดตามทีละขั้นตอนของ sum-to-n 3

1. การเรียกครั้งแรก: sum-to-n 0 2* 1* 0* 3* → (+ 3 (sum-to-n 2))

2. การเรียกครั้งที่สอง: sum-to-n 0 2* 1* 0* 2* → (+ 2 (sum-to-n 1))

3. การเรียกครั้งที่สาม: sum-to-n 0 2* 1* 0* 1* → (+ 1 (sum-to-n 0))

4. กรณีฐาน: sum-to-n 0 2* 1* 0* 0* → 0

การประกอบผลลัพธ์สุดท้ายอีกครั้ง

เมื่อแก้ไขกรณีที่ง่ายที่สุดแล้ว การคำนวณแต่ละชั้นจะเสร็จสมบูรณ์:

1. sum-to-n 0 ให้ 0
2. sum-to-n 1 กลายเป็น (+ 1 0) = 1
3. sum-to-n 2 กลายเป็น (+ 2 1) = 3
4. sum-to-n 3 กลายเป็น (+ 3 3) = 6

ตัวอย่าง: การพิมพ์แต่ละองค์ประกอบของรายการ

ต่อไปนี้เป็นฟังก์ชันแบบเรียกซ้ำอย่างง่ายในการพิมพ์ทุกองค์ประกอบในรายการ:

(define (print-elements lst)
  (if (null? lst)
    (lumi-message "done")
    (begin
      (lumi-message (number->string (car lst))) ; พิมพ์องค์ประกอบแรก
      (print-elements (cdr lst)))))             ; ประมวลผลส่วนที่เหลือของรายการ

• กรณีฐาน: หากรายการว่างเปล่า (null? lst) ให้หยุดการเรียกซ้ำ
• กรณีเรียกซ้ำ: พิมพ์องค์ประกอบแรก (car lst) จากนั้นเรียกใช้ฟังก์ชันในส่วนที่เหลือของรายการ (cdr lst)

ตัวอย่างการใช้งาน

(print-elements (list 1 2 3))

เอาท์พุท:

• “1”
• “2”
• “3”

ผลลัพธ์: “done”

มันทำงานอย่างไร

1. ฟังก์ชันดึงข้อมูลองค์ประกอบแรกของรายการโดยใช้ car และประมวลผล
2. จากนั้นจะเรียกตัวเองพร้อมกับรายการที่เหลือ (cdr)
3. กระบวนการนี้จะทำซ้ำจนกว่ารายการจะว่างเปล่า (null? lst)

สรุป

• การเรียกซ้ำแบบง่ายประกอบด้วย:
  1. กรณีพื้นฐาน: หยุดการเรียกซ้ำ
  2. กรณีแบบเรียกซ้ำ: ลดปัญหาไปยังกรณีพื้นฐาน
• การเรียกซ้ำแต่ละครั้งจะทำให้การคำนวณดำเนินไปจนเสร็จสิ้น
• เมื่อถึงกรณีฐานแล้ว ผลลัพธ์จะถูกรวมเข้าด้วยกันเมื่อการเรียกซ้ำเสร็จสมบูรณ์

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