Friday, June 30, 2006

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

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

2 Comments:

At 3/09/2013 11:20 PM, Anonymous Anonymous said...

Greetings from Idaho! I'm bored to tears at work so I decided to browse your site on my iphone during lunch break. I love the knowledge you provide here and can't wait to
take a look when I get home. I'm surprised at how fast your blog loaded on my mobile .. I'm not even using WIFI, just 3G .
. Anyhow, amazing site!

my web page - kirkpatrick Macmillan
Also see my webpage - squash

 
At 5/10/2013 6:53 PM, Anonymous Anonymous said...

My name's Bell from Harbarnsen, Germany and I just wanted to tell you your article is very informative. The quality of your writing is very nice and I can reckon you are an pro on this subject. With your approval, would you allow me to grab your RSS feed to keep updated with new posts? Thanks a ton and please continue the awesome work.

Also visit my web blog; mshsncc.blogspot.com

 

Post a Comment

<< Home