POPMOBILECOMPUTER: มกราคม 2010

บันทึุกข้อความ จาก http://www.comscience.net/index.php?topic=714.0 ขอบคุณ smallfox.exe สำหรับความรู้นี้

มีคำถามจากนักศึกษาคนหนึ่งถามว่า "เราจะคิดโปรแกรมที่มีการทำงานแบบ Recursive ได้อย่างไร?"

อันนี้ เป็นคำตอบที่ตอบยากมาก ผมก็เลยตอบไปว่ามันขึ้นอยู่กับประสบการณ์ในการเขียนโปรแกรม ซึ่งมันก็เป็นคำตอบที่ถูก(ตามความเห็นของผม) แต่ก็ยังไม่ครอบคลุม แล้วมีคำตอบที่ดีกว่านี้หรือเปล่า?

หลังจากที่ผมลองไปหาข้อมูลมาก็ ได้คำตอบต่าง ๆ กันมากมาย แต่ข้อมูลที่ได้รับล้วนแล้วแต่ขึ้นต้นด้วยคำว่า “มันเป็นคำตอบที่ยาก” เพราะว่ามันไม่ได้มีหลักอะไรไว้ตายตัวอย่าง 1+1=2 มันจึงค่อนข้างเป็นคำตอบที่ตอบยาก และต้องใช้ประสบการณ์ในการโปรแกรม

ลอง มาดูความเห็นแรกกันก่อนดีกว่า

จาก Aj. Pichaya

การคิด Recursive Algorithm เป็นกลไกการวิธีการทำงานในเชิงคณิตศาสตร์ ซึ่งหากเรามองในทฤษฎีตรงนั้นออก เราก็จะสามารถเขียน Recursive Algorithm ได้

เช่น F(x)! = F(x)*F(x-1)!

ถ้าเราเห็นสมการใน ลักษณะอย่างนี้ เราก็จะสามารถสร้าง Recursive programming ได้อย่างไม่ยาก (ถ้าเขียน Recursive programming ได้) แต่ปัญหาคือ เราจะคิดสมการนี้ได้อย่างไรล่ะ? จริง ๆ แล้ว ถ้าจะเจาะลึกกันไปจริง ๆ คงต้องไปถามนักคณิตศาสตร์ที่แก้ปัญหาเช่นนี้ แต่ถ้าเป็นปัญหาที่ไม่ยากเกินไป อย่างเช่น Factorial, Fibonacci, Palindrome ก็คิดว่า นักศึกษาคงจะสามารถคิดออกด้วยตัวเอง และในวิชานี้ก็ไม่ได้เน้นในจุดที่ให้สามารถคิด Recrusive Algorithm ที่ซับซ้อนมากเกิน แต่จะเน้นเกี่ยวกับการเข้าใจโครงสร้างภาษา C การใช้ Pointer ที่ซับซ้อนขึ้น เข้าใจ Data structure ในระดับที่พอจะนำไปเขียนเพื่อใช้งานจริง ๆ ได้

แต่ถ้าเป็นการ Recursive ที่ซับซ้อน อย่างเช่นการเดินหมากรุกทุกตัวทั้งตาราง หรืออะไรทำนองนี้คงจะต้องศึกษาเจาะลึกลงไปตรงนั้น เกี่ยวกับการสร้าง สมการคณิตศาสตร์ ในการแก้ปัญหาเหล่านี้ ซึ่งไม่ได้คิดกันได้วันหรือ 2 วัน แต่เกิดจากการผ่านการวิเคราะห์มาเป็นเวลานาน และหาทฤษฎีเข้ามาช่วยในการแก้ปัญหาต่าง ๆ ก่อนที่จะสรุปออกมาเป็นกฎ

จาก Aj. RobertZ

It entirely depends upon the needs of the algorithm. Sometimes it is,

sometimes it isn't. In this example it is appalling, but if you want to

calculate fibonnaci (spelling??) numbers, it is a natural.

How you can create recursive ALGORITHM?

There's no easy answer to that - it entirely depends upon what is

being done - some things just naturally break down so that a recursive

solution works, others don't. Attempting to force one or the other

is almost always wrong (sometimes naturally recursive algorithms are

forced to be loops to make it more (memory mostly, but time as well)

efficient). Forcing an iterative algorithm to be recursive never

makes sense.

What is naturally break down?

Things like parsers for grammars (parts of compilers) etc, just tend

to naturally be recursive. Its lots easier to parse an aritmetic

expression using recursive functions than using iterative ones (though

it is possible that way as well - I think there's a theorem somewhere

that says that everything done recursively can be done iteratively).

But any problem solving exercise involves breaking the problem into

smaller pieces, and solving each of those, and then combining the

results.

Sometimes when that happens, we get problem P broken down into pieces

A B and C, all of which are unrelated - then we just have a bunch of

different problems to solve.

Or sometimes we may find that the result is that to handle P, we need

to do X, over and over again, until something or other happens - then

you have an iterative solution - a loop.

Or sometimes, we find that the result is that to solve P, what we

need to do fist is solve a different version of P (or perhaps when

we're looking to solve A (above) we find that a part of that is

to solve P again - usually for simpler input conditions). Then we

get recursion.

Translate (ปัจจุบันนี้ พบว่า นักศึกษาที่เพิ่งเข้าภาคคอมพบว่าเป็นโรคขี้เกียจอ่านภาษาอังกฤษก็เลยแปลให้ ไม่เช่นนั้นจะไม่อ่านกัน)

การที่ใช้ Recursive Algorithm นั้น มันขึ้นอยู่กับว่าโปรแกรมที่เราจะสร้างขึ้นมาจำเป็นต้องใช้มันหรือเปล่า? บางทีอาจจะจำเป็น บางทีอาจจะไม่จำเป็น ตัวอย่างเช่น ถ้าเราเขียนโปรแกรมวนลูปธรรมดา รู้จุดสิ้นสุดที่แน่นอน เราก็ไม่จำเป็น แต่ถ้าเป็นการหาค่า Fibonacci number มันเป็นธรรมชาติ เอ๋ ไอคำว่า natural เนี่ย หมายถึงอะไร? [จะอธิบายอีกครั้ง ข้างล่าง]

แล้วจะ สร้าง Recursive Algorithm ได้อย่างไร?

มันไม่ง่ายที่จำตอบคำถาม นั้น มันขึ้นอยู่กับว่าเราต้องการจะทำอะไร?

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

การแตกการทำงานแบบ naturally? เงื่อนไขในการหยุดการทำงานแบบ naturally เป็นแบบใด?

มันคล้ายกับเป็นส่วนของไวยากรณ์ (เป็นส่วนการแปลภาษาของคอมไพล์เลอร์) เป็นต้น ซึ่งเงื่อนไขในลักษณะนี้เป็น recursive เราสามารถใช้ Recusive function เรียกตัวเองในการแก้ปัญหาในการแปลงพวก Aritmetic expression ได้ง่ายกว่าการใช้การวนลูปแบบ iterative มาก หรือไม่ว่าจะเป็น การแก้ปัญหาพวก Fibonacci หรือ Palindrome ถ้าเราเขียนแบบใช้ Loop style เราจะพบว่าการแก้ปัญหาโดยการใช้ Recursive programming จะแก้ปัญหาได้ง่ายกว่า

ซึ่งทฤษฎีเกี่ยวกับ "ทุก ๆ สิ่งที่สามารถเขียนเป็น Recursive จะสามารถแปลงให้เป็น Iterative ได้" น่าจะมีอธิบายไว้ที่ไหนสักแห่ง อาจจะลองไปหาข้อมูลทาง web site ดู

หลักการแก้ปัญหาเกี่ยวกับการคิด Recursive algorithm เราจะใช้วิธีคิดดังนี้

แตกปัญหาออกเป็นส่วนย่อย ๆ แล้วแก้ปัญหาแต่ละส่วน ๆ ไป จากนั้นก็รวมเข้าด้วยกันเป็นผลลัพธ์สุดท้าย

บางครั้งเมื่อมีปัญหาเกิดขึ้น (P) เราจะแยกปัญหาใหญ่ ๆ (P) ออกเป็นส่วนย่อย ๆ คือ A B และ C ซึ่งไม่ได้มีความสัมพันธ์กัน ต่อมาเราก็ทำการแก้ปัญหาต่าง ๆ( A B และ C)

หรือบางครั้ง เราพบว่าวิธีการในการแก้ปัญหาคือเราจะต้องจัดการทำ X ไปเรื่อย ๆ จนกว่าจะเกิดอะไรขึ้น แล้วเราก็หยุด แสดงว่าเราใช้ iterative ในการแก้ปัญหา

หรือบางครั้งเราพบว่าวิธีการในการแก้ปัญหาคือเราจะต้องแก้ปัญหา P ในแบบต่าง ๆ (หรือบางทีต้องแก้ปัญหา A ก่อน) แล้วเราพบว่าการแก้ไขปัญหา A นั้นเป็นส่วนที่ช่วยแก้ปัญหา P อีกครั้ง โดยมีเงื่อนไขในการ input แบบง่าย ๆ นั่นแสดงว่าเราใช้การ Recursion ในการแก้ปัญหา

การเขียนใน โปรแกรมในลักษณะ Loop style และ Recursive style

ก่อนที่จะอ่านวิธีการเขียนในโปรแกรมในลักษณะ Loop style และ Recursive style ผมจะขอชี้แจงไว้ก่อนเลยว่า การเขียนโปรแกรมแบบ iterative แล้วมาแปลงเป็น recursive ไม่ได้ make sense!! (ไม่ใช่สิ่งที่ถูกต้อง) การทำ function ที่เป็น recursive จะใช้หน่วยความจำมากกว่า iterative ดังนั้นถ้าเราสามารถเขียนในลักษณะของ iterative ได้จะดีกว่า recursive

แต่ บางครั้งเราพบว่า Algorithm บางอย่าง ถ้าเราจะต้องเปลี่ยนจาก recursive มาเป็นเขียนโปรแกรมแบบวนลูปตรวจสอบ จะทำได้ยากกว่ามาก เช่นในส่วนการแปลภาษาของ compiler หรือการเดิน หมากรุก เป็นต้น แต่ที่ทำไว้ดูตรงนี้เพื่อที่จะให้เข้าใจการทำงานของ Recursive function มากขึ้น และพอจะมีแนวคิดในการสร้าง Algorithm แบบ Recursive

เรา พบว่าถ้าเป็นลูป 1 ชั้น และภายในไม่ได้มีการทำงานที่ซับซ้อนเราสามารถเขียนแทนกันได้ดังนี้

// 1 loop style

int function(int a,int b){

for(index=0;index<5;index++)

printf("index = %d\n",index);

index = a;

return index;

}

//recursive style

int function(int a,int b,int index){

if(index<5 ) {

printf("index = %d\n",index);

return function(a,b,index+1);

}

index = a;

return index;

}

ถ้ามีการทำงาน 2 ลูป เราสามารถเขียนแทนกันได้ดังนี้

// 2 for loop style

int function(int a,int b){

int index,j;

for(j=0;j<5;j++){

for( index=0;index<5;index++) {

printf("index = %d\n",index);

}

}

index=a;

return index;

}

// recursive style.....

// Use index, and j as counter

int function(int a,int b,int index,int j){

printf("index = %d\n",index);

if (++index < 5)

function(a,b,index,j);

else if (++j < 5)

function(a,b,0,j);

return index;

}

จะ เห็นว่าตัว index ที่ใช้ในการทำลูปจะต้องส่งเป็น parameter ให้กับ function recursive เสมอ ๆ

ตัวอย่างในการแปลงจะไม่ถูกต้องในทุกกรณี เช่นถ้าเปลี่ยนจากคำสั่ง printf("index = %d\n",index); เป็นคำสั่งอื่นที่มีผลเกี่ยวข้องกับตัวแปรที่เป็นผลลัพธ์สุดท้าย ก็อาจจะทำให้ผลลัพธ์ของ function มีค่าที่แตกต่างกันไป ซึ่งจุดนี้เองที่ทำให้การยากในการคิด Recursive programming
Logged
เรื่อ

POPMOBILECOMPUTER

วันเสาร์ที่ 30 มกราคม พ.ศ. 2553

ติดตั้ง Apache2, PHP5 & MySQL5 with Yum on CentOS

ติดตั้ง phpmyadmin ใน Centos 5.4

DNS tot และ tt&t

วันจันทร์ที่ 25 มกราคม พ.ศ. 2553

การทำงานแบบ Recursive

วันเสาร์ที่ 16 มกราคม พ.ศ. 2553

แก้ปัญหา หา modem nokia ไม่เจอ

ปัญหา wordpad ใน windows 11 หาย แก้ไขแบบนี้

ค้นหาบล็อกนี้