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

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

แอบอัพเดท

โทษทีที่ยังไม่ได้เอารูปตอนไปยุโรปมาลงให้ จะเอามาให้ดูจริง ๆ แหละ แต่รอก่อนนะ ตอนนี้ขอแอบกลับไปเขียนเรื่องบ้า ๆ ต่อก่อน

ฟันคุด

ไปผ่าฟันคุดมาเมื่อวันศุกร์ที่แล้วหนะ . . . ผ่าข้างล่างสอง ถอนข้างบนสอง

ก่อนหน้านี้ มีคนขู่ไว้เพียบเลย - -'' พอทำเอง มันก็ไม่ได้น่ากลัวขนาดนั้นซะหน่อย

พอเจอหมอ หมอเค้าก็คุยก่อนนะ เค้าบอกว่า ฟันมันเอียงมาก (ประมาณ 70 องศา จากที่เห็นในฟิล์ม) เอียงเหมือนจะไปดันซี่ข้าง ๆ ด้วย ถ้าจะเอาออก จะต้องทำให้มันเป็นชิ้นเล็กชิ้นน้อยก่อน วิธีทำก็คือ ค่อย ๆ กรอเนื้อฟันออก จนมันบางลง ก็ออกแรกบีบให้มันแตก ... ฟังดูน่ากลัวมะ

พอถึงเวลาจริง ที่เจ็บที่สุดก็เห็นจะเป็นเข็มฉีดยาชานี่แหละ (มันก็ไม่ได้เจ็บมากหรอก บริจาคเลือดยังเจ็บกว่าอีก)

เริ่มแรก เค้าฉีดยาชาเสร็จแล้วก็รอแป๊บนึง แล้วก็เอาคีมมางัดแงะดึงฟันข้างบนออก เดี๋ยวเดียวเสร็จเลย รู้สึกว่าอะไร ๆ มันก็เร็วกว่าที่คิดนะ

แต่อีกสองซี่ที่ต้องทำให้เป็นชิ้น ๆ เนี่ย ใช้เวลานานกว่าที่คิดแฮะ

ช่วงที่รู้สึกเสียว ๆ ก็มีนะ ช่วงแรกคือ ตอนที่หมอกำลังขัดเนื้อฟันข้างขวาออกเนี่ย เค้าออกแรงเยอะมาก จนรู้สึกว่ามันตึงที่ข้างนอกเลย

อีกช่วงนึงก็ ... จริง ๆ ไม่ได้รู้สึกเจ็บหรือเสียวฟันอะนะ เป็นความเสียวทางความคิดหนะ คือประมาณว่า ผู้ช่วยหมอเค้าไม่ใส่แว่นแล้วมองเห็นไหมไม่ชัด (สีมันคล้าย ๆ น้ำลาย) หมอก็ต่อว่า ว่าถ้ามองไม่ชัด คราวหน้าต้องใส่แว่นมานะ ไม่งั้นไม่ต้องมาช่วย - -'' เสียวมั้ยหละ

แล้วหลังจากนั้นแป๊บเดียว หมอก็บอกอีกว่า ไหมเนี่ย ผู้ช่วยดึงไม่แน่น ... แล้วหมอก็ทำอะไรอีกก็ดูไม่รู้เรื่อง อาจจะเอาออก เย็บใหม่ก็ได้ (ยังไงตอนนี้ก็ดูไม่ออกแล้ว)

พอทำเสร็จ ก็ไม่รู้สึกเจ็บเลยนะ แต่มันเมื่อยนิด ๆ เพราะต้องกัดสำลีไว้ตั้งหลายชั่วโมง แล้วก็ต้องคอยเอาน้ำแข็งประคบด้วย

วันแรกหลังจากทำ ก็ไม่เจ็บนะ แค่รำคาญว่าเวลากินอะไร เศษมันจะติด ๆ แล้วเอาออกไม่ได้ แล้วก็เจ็บนิดหน่อยเวลากลืน เพราะว่ามีแผลที่ลิ้นนิดนึง

วันที่สองก็ รู้สึกเหมือนวันแรก ... ไม่ค่อยรู้สึกว่ามันจะดีขึ้นแฮะ - -''

วันที่สามเนี่ย เริ่มรู้สึกดีขึ้นละ แต่ก็ยังกินอะไรที่ต้องเคี้ยวไม่ได้หนะ ยังกินแต่ไข่ตุ๋น มันฝรั่งบด แล้วก็โจ๊ก

วันนี้วันที่สี่แล้ว ... ทำไมมันรู้สึกเจ็บ ๆ อะ T_T ... ความเจ็บมันมีการหน่วงเวลาด้วยแฮะ ...