หมายเหตุ: เดิมโพสต์นี้ไว้ในบล็อกของฉันที่ https://therobinkim.com/blog/recognizing-a-pattern-in-my-recursive-functions การอัปเดตใดๆ จะปรากฏที่นั่นและไม่ใช่ที่นี่
Shawn Drost จาก Hack Reactor สอนให้ฉันเขียนฟังก์ชันแบบเรียกซ้ำด้วยคำสั่ง if-else:
function recursion() {
if(baseCase) {
// do something
} else {
// get me 1 step closer to the base case
}
}
ขณะที่ฉันกำลังทบทวนเนื้อหาหลักสูตรบางส่วนจาก Hack Reactor และตะลุยงาน "codewars" ฉันเริ่มรับรู้รูปแบบทั่วไปในโค้ดของฉันเมื่อต้องรับมือกับปัญหาการเรียงสับเปลี่ยนที่สร้างขึ้นตามคำแนะนำของ Shawn
นี่คือโค้ดบางส่วนที่ฉันจะเขียนหากต้องค้นหาการเรียงสับเปลี่ยนที่แตกต่างกันทั้งหมดของสตริงที่เรียกว่า problem
function findAllAnswers(problem) {
var partialAnswer = "";
var allAnswers = [];
findAnswers(problem);
return allAnswers;
function findAnswer(problem) {
if(problem.length === 0) {
allAnswers.push(partialAnswer);
return;
}
else {
// add the first bit of 'problem' to partialAnswer
partialAnswer.push(problem[0]);
// explore all branches that include this first bit
findAnswer(problem.slice(1));
// lets remove what we added just before the recursive call
partialAnswer = partialAnswer.substring(0, partialAnswer.length - 1);
}
}
}
ฉันใช้แนวทางนี้เพื่อแก้ปัญหา N-Queens แสดงรายการความเป็นไปได้ทั้งหมดของการจับคู่แบบเป่ายิ้งฉุบ และค้นหาการเรียงสับเปลี่ยนคำทั้งหมดที่คุณสามารถพิมพ์ลงในแป้นตัวเลขของโทรศัพท์มือถือ T-9
ส่วนประกอบสำคัญที่โดดเด่นสำหรับฉันคือ:
- ฉันมีตัวแปร
partialAnswers
เพียงตัวเดียวที่ฉันจัดการจนกว่าจะตรงตามเกณฑ์ในการเป็นคำตอบที่สมบูรณ์ จากนั้นฉันก็ผลักโซลูชันเดียวไปที่อาร์เรย์allAnswers
ของฉัน - ฉันสำรวจทุกสาขาของความเป็นไปได้แรก จากนั้นย้อนรอยทีละขั้นจนกว่าฉันจะกลับสู่สภาพเดิม เมื่อถึงจุดนั้นฉันก็เริ่มสำรวจทุกสาขาเพื่อหาความเป็นไปได้ต่อไป
- รหัสของฉันส่วนใหญ่แล้วจะ "เรียบง่ายและสะอาดตา" ฉันต้องกังวลเกี่ยวกับพารามิเตอร์/อาร์กิวเมนต์เพียงตัวเดียวในปัญหาง่ายๆ นี้ (แนวทางที่ยังไม่ประณีตก่อนหน้านี้ของฉันจะต้องมีอาร์กิวเมนต์สองข้อ:
remainingProblem
และanswerSoFar
ซึ่งอาจทำให้เป็นระเบียบเล็กน้อย)
เวทมนตร์ที่เกิดขึ้นในคำสั่ง else
เป็นสิ่งที่ฉันอาจเคยพยายามดิ้นรนเพื่อให้ได้มาก่อนหน้านี้ แต่ตอนนี้รู้สึกเหมือนเป็นการเล่นของเด็ก (นั่นเป็นสิ่งที่ดีใช่ไหม?)
ต่อไปเหรอ? บางทีการเรียกซ้ำหาง