เชี่ยวชาญ Ruby Recursion และ Memoization: คู่มือปฏิบัติ

Recursion ใน Ruby คืออะไร? Recursive functions คือฟังก์ชันที่เรียกตัวเองซ้ำจนถึง end goal (base case) หลังแต่ละ function call ก้าวหน้าสู่ base case ลดงานที่เหลือ

ถึง base case recursion จบ และ functions เริ่ม return

Ruby Recursion

ตัวอย่างคลาสสิกเริ่มต้น recursion: คำนวณ factorial number

ดูวิธีคำนวณ factorial ด้วย Ruby ใช้ iteration และ recursion!

Factorial ของเลข = คูณเลขทั้งหมด 1 ถึง target number เช่น factorial of 5: 1 * 2 * 3 * 4 * 5 = 120

ลองทำด้วย Ruby และ recursion:

ตัวอย่าง:

def iterative_factorial(n)
  (1..n).inject(:*)
end
def recursive_factorial(n)
  # Base case
  return 1 if n <= 1
  # Recursive call
  n * recursive_factorial(n-1)
end

แสดง 2 วิธีคำนวณ factorial iterative และ recursive ใน recursive solution ก้าวหน้าด้วยการลดเลข (n-1) ถึง (n <= 1) ไม่มี recursive calls อีกแล้ว และนี่คือสิ่งที่เกิดขึ้น:

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 developers เลือก iterative solution มากกว่า และดี แต่รู้ recursion ยังคุ้มค่า

มาดูอีกตัวอย่างคลาสสิก: Fibonacci numbers

The Fibonacci Sequence

Leonardo Fibonacci ค้นพบ sequence นี้ตอนสืบสวน model การเติบโตของกระต่ายภายใต้เงื่อนไข ideal

Sequence คำนวณโดยบวก 2 เลขก่อนหน้า

ตัวอย่าง: 1, 1, 2, 3, 5, 8, 13, 21

คำนวณใน Ruby ด้วย recursive function:

def fib(n)
  return n if n < 2
  fib(n-1) + fib(n-2)
end

ใช้ function นี้กับ range คำนวณ 20 Fibonacci numbers แรกได้ง่าย:

(1..20).each { |n| puts fib(n) }

แต่มีปัญหา: Function ทำ extra work มากเกินไป ดูรูป:

เห็นว่า fib(3) คำนวณ 5 ครั้ง! ทำให้ function ช้ามากตอนคำนวณ sequence ยาว วิธีแก้? Memoization

Memoization: ใช้ซ้ำงานที่ทำแล้ว

ดีนะถ้า reuse งานที่ทำในขั้นตอนก่อนหน้าได้ ใช้ memoization เก็บ expensive calculation results ใน cache ในที่นี้ array พอ

ตัวอย่าง:

@cache = [0,1]
def fib(n)
  return @cache[n] if @cache[n]
  @cache[n] = fib(n-1) + fib(n-2)
end

เช็กก่อนว่าผลลัพธ์อยู่ใน cache แล้วไหม ถ้าอยู่ return ทันที ไม่อยู่ คำนวณและ save ไว้ จะเร็วกว่ามาก และคำนวณ Fibonacci numbers ใหญ่ได้

The Limits of Recursion

ตาม reader ชี้ให้เห็น recursive solution fail ด้วย SystemStackError: stack level too deep กับ input ใหญ่ (ประมาณ 7500 ขึ้นอยู่กับระบบ) ถ้าต้องคำนวณใหญ่กว่านี้ ต้องใช้ iterative solution

ตัวอย่าง:

memo = []
(0..n).each do |i|
  memo[i] = i < 2 ? i : memo[i-1] + memo[i-2]
end

สรุป

Recursion เก๋แต่อาจยากต่อการเข้าใจ ตอนนี้ถึงคุณฝึกฝน practice makes mastery!

แชร์โพสต์ถ้าชอบ และสมัครรับ newsletter 🙂