การเรียกซ้ำใน Ruby คืออะไร
ฟังก์ชันแบบเรียกซ้ำคือฟังก์ชันที่เรียกตัวเองไปเรื่อยๆ จนกว่าจะถึงเป้าหมายสุดท้าย (เรียกอีกอย่างว่า ตัวพิมพ์พื้นฐาน ). หลังจากการเรียกใช้ฟังก์ชันแต่ละครั้ง คุณจะมีความคืบหน้าต่อกรณีพื้นฐานนี้ ซึ่งจะช่วยลดปริมาณงานที่เหลือที่ต้องทำ
เมื่อถึงกรณีฐาน การเรียกซ้ำจะสิ้นสุดลง และฟังก์ชันจะเริ่มกลับมา
การเรียกซ้ำทับทิม
ตัวอย่างคลาสสิกในการเริ่มเรียนรู้เกี่ยวกับการเรียกซ้ำคือการคำนวณจำนวนแฟกทอเรียล
มาดูกันว่าเราจะทำสิ่งนี้ใน Ruby ได้อย่างไรโดยใช้ทั้งการวนซ้ำและการเรียกซ้ำ!
ในการคำนวณแฟกทอเรียลของตัวเลข เราต้องคูณตัวเลขทั้งหมดจาก 1 เป็นจำนวนเป้าหมายของเรา ตัวอย่างเช่น แฟกทอเรียลของ 5 คือ:1 * 2 * 3 * 4 * 5 = 120 .
มาดูกันว่าเราจะทำสิ่งนี้ได้อย่างไรโดยใช้ Ruby และการเรียกซ้ำ
ตัวอย่าง :
def iterative_factorial(n) (1..n).inject(:*)enddef recursive_factorial(n) # Base case return 1 if n <=1 # Recursive call n * recursive_factorial(n-1)end>
ในตัวอย่างนี้ ฉันแสดงให้คุณเห็นสองวิธีในการคำนวณจำนวนแฟกทอเรียล วิธีแก้ปัญหาแบบวนซ้ำและแบบเรียกซ้ำ
ในการแก้ปัญหาแบบเรียกซ้ำ เรามีความคืบหน้าโดยการลดจำนวนที่เรากำลังทำงานด้วย (n-1) เมื่อ (n <=1) ไม่มีการเรียกซ้ำอีกต่อไป และนี่คือสิ่งที่เกิดขึ้น:
return 1 # recursive_factorial(1)return 2 * 1 # recursive_factorial(2)return 3 * 2 # recursive_factorial(3)return 4 * 6 # recursive_factorial(4)return 5 * 24 # recursive_factorial(5)
ในฐานะนักพัฒนา Ruby เราใช้วิธีแก้ปัญหาแบบวนซ้ำเป็นส่วนใหญ่ และนั่นก็เยี่ยมมาก แต่ฉันคิดว่ามันยังคงคุ้มค่าที่จะรู้ว่าการเรียกซ้ำทำงานอย่างไร
คราวนี้มาดูตัวอย่างคลาสสิกอื่นๆ กัน:ตัวเลขฟีโบนักชี
ลำดับฟีโบนักชี
Leonardo Fibonacci ค้นพบลำดับนี้เมื่อศึกษาวิธีจำลองการเติบโตของประชากรกระต่ายภายใต้สภาวะที่เหมาะสม
ลำดับคำนวณโดยการบวกตัวเลขสองตัวที่มาก่อนตัวปัจจุบัน
ตัวอย่าง :
1, 1, 2, 3, 5, 8, 13, 21
ในการคำนวณใน Ruby คุณสามารถใช้ฟังก์ชันแบบเรียกซ้ำ:
def fib(n) return n if n <2 fib(n-1) + fib(n-2)end
คุณสามารถใช้ฟังก์ชันนี้และช่วงเพื่อคำนวณตัวเลขฟีโบนักชี 20 ตัวแรกได้อย่างง่ายดาย
(1..20).each { |n| ใส่ fib(n) } แต่มีปัญหา :
หน้าที่ของคุณกำลังทำงานพิเศษมากมายที่ไม่จำเป็น เพื่อแสดงให้เห็นสิ่งนี้ ให้ดูที่ภาพต่อไปนี้
ในภาพเราจะเห็นว่า fib(3) ถูกคำนวณห้าครั้ง สิ่งนี้ทำให้ฟังก์ชันของคุณช้าลงมากหากคุณพยายามคำนวณลำดับฟีโบนักชีที่ยาวขึ้น
การแก้ไขปัญหา? ท่องจำ
การท่องจำ:การนำงานที่เราทำไปแล้วกลับมาใช้ใหม่
คงจะดีไม่น้อยถ้าคุณสามารถนำงานที่คุณได้ทำไปแล้วในขั้นตอนก่อนหน้ากลับมาใช้ใหม่ได้
เราทำได้โดยใช้การท่องจำ .
เพื่อบันทึกผลการคำนวณที่มีราคาแพงของเรา เราใช้แคช ในกรณีนี้อาร์เรย์จะทำ
ตัวอย่าง :
@cache =[0,1]def fib(n) return @cache[n] if @cache[n] @cache[n] =fib(n-1) + fib(n-2)end ก่อน>ขั้นแรก เราตรวจสอบเพื่อดูว่าผลลัพธ์อยู่ในแคชแล้วหรือยัง หากอยู่ในแคชแล้วส่งคืน มิฉะนั้น เราจะทำการคำนวณและบันทึกผลลัพธ์
การดำเนินการนี้จะเร็วขึ้นมาก และสามารถคำนวณตัวเลขฟีโบนักชีที่ใหญ่กว่าได้มาก
ขีดจำกัดของการเรียกซ้ำ
ตามที่ผู้อ่านกรุณาชี้ให้เห็น โซลูชันแบบเรียกซ้ำอาจล้มเหลวด้วย
SystemStackError: stack level too deepด้วยตัวเลขอินพุตขนาดใหญ่ (ประมาณ 7500 จำนวนที่แน่นอนขึ้นอยู่กับระบบของคุณ)หากคุณต้องการคำนวณจำนวนที่มากกว่านั้น คุณจะต้องใช้วิธีวนซ้ำ
ตัวอย่าง :
memo =[](0..n).each do |i| บันทึก[i] =ฉัน <2 ? ผม :บันทึก[i-1] + บันทึก[i-2]สิ้นสุดบทสรุป
การเรียกซ้ำนั้นยอดเยี่ยม แต่บางครั้งมันก็เข้าใจยาก ตอนนี้ถึงตาคุณแล้ว การฝึกฝนทำให้เชี่ยวชาญ!
โปรดแชร์โพสต์นี้หากคุณชอบและสมัครรับจดหมายข่าวของฉัน 🙂
