Programming: Stack and Recursion

ไม่ยอมเขียนมาซะนาน ขอกลับมาทำบ้างซักครั้งละกัน ... คิดถึงจัง ความรู้สึกนี้ :D

คราวนี้จะพูดถึงเรื่องการเขียนโปรแกรมซักหน่อยนะ คาดว่าจะเป็นประโยชน์กับ programmer รุ่นเด็ก ๆ บ้างนะ

Stack and Recursion

หลาย ๆ คนคงรู้อยู่แล้วว่าทั้งสองอย่างนี้มันคืออะไร และมันเกี่ยวกันยังไง ... ใครไม่รู้อ่านต่อละกัน :P

Stack

• กลุ่มข้อมูลคล้าย ๆ หลอด CD ที่ใช้เสียบแผ่นหลาย ๆ แผ่นเข้าด้วยกัน
• คุณสมบัติก็คือ จะใส่เพิ่มหรือจะหยิบออก จะต้องทำจากข้างบน

Recursion

• การทำซ้ำ ๆ ที่เกิดจากการฟังก์ชันที่เรียกกันเป็นวง เช่น f เรียก g แล้ว g เรียก h แล้ว h เรียก f ไปเรื่อย ๆ
• สิ่งที่จำเป็นในการเขียนโปรแกรมแบบ Recursive ก็คือ จะต้องมีเงื่อนไขการหยุด

แล้วสองอย่างนี้ มันเกี่ยวข้องกันยังไงหละ?

จริง ๆ อยากให้ไปอ่านเรื่องที่ทำ Virtual Machine จัง แต่มันคงจะยาวไปเนอะ ... สรุปเลยละกัน :P ง่าย ๆ ก็คือ ... ทุกครั้งที่เรียกฟังก์ชัน เราต้องเพิ่มข้อมูลบางอย่างใน Stack ของ CPU แล้วพอฟังก์ชันทำงานเสร็จ เราก็จะเอาของพวกนั้นออก

แปลว่า ... ที่เราสามารถเขียนโปรแกรมแบบ recursive ได้เนี่ย ก็เพราะว่า CPU มันมี Stack อยู่

และก็แปลว่า ... เราสามารถสร้าง Stack ขึ้นเอง แล้วก็ไม่ต้องไปรบกวน Stack ของ CPU ได้เหมือนกัน

ลองดูตัวอย่างเลยละกัน สมมติว่าเรามีฟังก์ชันที่เขียนแบบ recursive ตัวนึง

 function f(x)
 begin
  if x <= 0 then return 0;
  else return 2x - 1 + f(x - 1);
 end

ถ้าเรามี Stack เราจะเขียนแบบไม่ recursive ได้เป็น

 function f(x)
 begin
  push x onto Stack;
  push "not done" onto Stack;
  while Stack is not empty
  do
   assign op ← Top of Stack;
   Remove Top of Stack;
   assign x ← Top of Stack;
   Remove Top of Stack;
   if op = "not done" then
   begin
    push x onto Stack;
    push "done" onto Stack;
    if x <= 0 then do nothing;
    else
    begin
     push x - 1 onto Stack;
     push "not done" onto Stack;
    end
   end
   else if op = "done" then
   begin
    if x <= 0 then assign ReturnValue ← 0;
    else assign ReturnValue ← 2x - 1 + ReturnValue;
   end
  end while
  return ReturnValue;
 end

จะเห็นว่า มันยาวขึ้นมาก -_-'' จริง ๆ จะทำให้สั้นกว่านี้ก็ได้อีกเยอะหนะนะ แต่นี่เป็นตัวอย่างการแปลงแบบตรงไปตรงมา ฟังก์ชันอะไรเราก็แปลงแบบนี้ได้