Google    Youtube      Psv     สพม.11

หน่วยที่7รีเคอร์ซิฟ

รีเคอร์ซิฟ

วัตถุประสงค์เชิงพฤติกรรม (Behavioral Objectives)

หลังจากศึกษาจบบทเรียนนี้แล้ว นักศึกษาจะมีความสามารถดังนี้

(After studying this chapter, you will be able to)

1.       ศึกษา / ปฏิบัติการฟังก์ชันรีเคอร์ซิฟ

2.       แสดงตัวอย่างการใช้ฟังก์ชันรีเคอร์ซิฟ

3.       ยกตัวอย่างรีเคอร์ซิฟโดยอ้อม

4.       ปฏิบัติการการสับเปลี่ยนลำดับ

5.       ลำดับขั้นตอนปฏิบัติการทำงานแบบรีเคอร์ซิฟ

6.       จัดบอร์ดเชิงปฏิบัติการ “รีเคอร์ซิฟ”

7.       สนทนาเชิงปฏิบัติการ “การสับเปลี่ยนลำดับ”

8.       อธิบายคำศัพท์ได้ 10 คำ

ในระหว่างการออกแบบเขียนโปรแกรมแบบบนลงล่าง (Top-down Design) จะมีงานย่อย (Subtask) เพื่อแก้ปัญหาในแต่ละเรื่อง และผู้เขียนโปรแกรมต้องการใช้งานย่อยที่เรียบง่ายและสามารถแก้ไขปัญหาที่มีขนาดใหญ่ได้ จึงมีการใช้งานย่อยในลักษณะที่เรียกตัวเองขึ้นมาทำงานเรียกว่า รีเคอร์ซิฟ (Recursive) เป็นเทคนิคที่ส่วนใหญ่ใช้กับโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้นอย่างเช่น ทรี(Tree) และกราฟ (Graph) เพื่อให้การใช้งานมีความสะดวกและง่าย

ฟังก์ชันรีเคอร์ซิฟ

โดยส่วนใหญ่การเขียนโปรแกรมจะใช้ฟังก์ชันเรียกฟังก์ชันอื่นขึ้นมาทำงาน บางครั้งอาจต้องมีการให้ฟังก์ชันเรียกตัวเองขึ้นมาทำงานเรียกว่าฟังก์ชันรีเคอร์ซิฟ (Recursive Function) ซึ่งใช้ในบางภาษา เช่น ภาษาซี ปาสคาล จาวา ปกติแล้วการเขียนอัลกอริทึมที่มีการทำงานซ้ำแบบเดิมจะใช้ในการวนลูปแบบต่าง ๆ แต่ใช้เป็นฟังก์ชันรีเคอร์ซิฟแทนได้ในลักษณะทำซ้ำอัตโนมัติ บางครั้งจึงเรียกว่า ลูปเสมือน (Virtual Loop)

ลักษณะของฟังก์ชันรีเคอร์ซิฟมีความรวบรัดสั้นกว่าแบบวนลูป โดยพิจารณาจากปัญหาในการคำนวณหาค่าของ xn , ให้ xเป็นเลขทศนิยมและ n เป็นเลขยกกำลังจำนวนเต็มไม่เป็นค่าลบ ครั้งแรกกำหนดให้การทำงานเป็นแบบวนลูป จะเป็นการนำ x มาคูณกัน n ครั้ง หากนำมาใช้คำนวณกับเลขยกกำลังที่เรียงต่อกันทีละค่า เช่น คำนวณหาค่าของ 30 – 35 จะได้เป็นดังต่อไปนี้

30 = 1

31 = 3

32 = 3 * 3 = 9

33 = 3 * 3 * 3 = 27

34 = 3 * 3 * 3 * 3 = 81

35 = = 3 * 3 * 3 * 3 * 3 = 243

จากตัวอย่างจะเห็นว่าการคำนวณหาค่าจากเลขยกกำลังของ 3 สามารถนำค่าจากการคำนวณของเลขยกกำลังก่อนหน้านี้มาใช้ เช่น นำค่าของ 33 =27 มาใช้กับ 34 หรือค่าของ 34 = 81 มาใช้กับ 35 ได้เป็น ดังนี้

34 = 3 * 33 = 3 * 27 = 81

35 = 3 * 34 = 3 * 81 = 243

จากการคำนวณหาค่าจากเลขยกกำลังของ 3 ในลักษณะดังกล่าว สิ่งที่เราต้องทราบก็คือ 30 ซึ่งเท่ากับ 0 และความสัมพันธ์พื้นฐานของเลขยกกำลังนี้ได้เป็น 3n = 3 * 3 n-1 เป็นฟังก์ชันรีเคอร์ซิฟได้โดยมีกฎเกณฑ์ ดังนี้

0 = 1

n = x * x n -1, for x > 0

รูปแบบของฟังก์ชันรีเคอร์ซิฟดังกล่าวจะมีลักษณะที่เรียกว่า Inductive ซึ่งเป็นการตรวจสอบกฎเกณฑ์ที่กำหนดขึ้นมาทางคณิตศาสตร์ แบ่งเป็นสองขั้นตอน คือ กฎเกณฑ์เป็นจริงเมื่อมีการตรวจสอบกับกรณีหรือปัญหาขนาดเล็กและกฎเกณฑ์ที่ใช้กับกรณีหรือปัญหาขนาดเล็กที่เป็นจริงนี้สามารถนำไปขยายใช้กับกรณีหรือปัญหาที่มีขนาดใหญ่ขึ้น เช่น กฎเกณฑ์ที่กำหนดขึ้นเป็นจริงเมื่อ1 < n < kและจะเป็นจริงเช่นกันเมื่อ 1 < n < k + 1โดยทั่วไปฟังก์ชันรีเคอร์ซิฟที่กำหนดให้มีการเรียกตัวเองขึ้นมาทำงานจะประกอบด้วย 2 ส่วน คือ

1. กรณีพื้นฐาน (Base Case) เป็นส่วนที่ค่าของฟังก์ชันสอดคล้องหรือเท่ากับค่าของพารามิเตอร์ที่ส่งมาหรือปัญหาได้ถูกแก้ไขเพียงพอแล้ว ไม่มีการเรียกตัวเองขึ้นมาทำงานอีก

2.เรียกตัวเอง (Recursive Call) เป็นส่วนที่ค่าของฟังก์ชันที่ถูกเรียกนำมาใช้กับค่าของพารามิเตอร์ที่ส่งมาหรือปัญหายังแก้ไขไม่เพียงพอ จะต้องเรียกตัวเองขึ้นมาทำงานต่อไปจนกว่าจะได้เป็นกรณีพื้นฐานจึงจบการทำงาน

จากตัวอย่างเลขยกกำลังที่ผ่านมาแบ่งส่วนที่เป็นกรณีพื้นฐานและส่วนที่เรียกตัวเอง คือ

Base Case:                            x0 = 1

Recursive Call:                   xn = x * xn-1, for x > 0

จากตัวอย่างเลขยกกำลังเมื่อใช้กับฟังก์ชันรีเคอร์ซิฟคำนวณหาค่าของ 35 จะมีดังในรูปที่ 7.1 ในครั้งแรกหาค่าของ 35 จะต้องคำนวณ34 หาค่ามาคูณกับ 3 และหาค่าของ 34 ต้องคำนวณ 33 หาค่ามาคูณกับ 3 เช่นกัน การทำงานจึงเป็นช่วงการเรียกตัวเองขึ้นมาทำงานไปเรื่อยๆ กับการหาค่าของ 32,31, และ 30 ซึ่งเป็นกรณีพื้นฐาน

จากกรณีพื้นฐานจะได้ค่า 30 = 1 ก็เป็นการถอยกลับไปตามทางเดิม (Backtracking) ดังในรูปที่ 7.2 โดยนำค่าที่ได้กลับไปคำนวณกับ 31 เมื่อได้ค่าผลลัพธ์ก็ส่งถอยกลับไปเรื่อย ๆ แบบเดียวกันกับ 32 ,33 ,34 , และครั้งสุดท้ายให้กับ 35 ที่เป็นคำตอบ

รูปแบบการทำงานแบบรีเคอร์ซิฟดังกล่าวนำมาเขียนเป็นฟังก์ชัน Power ได้เป็นตารางที่ 7.1 และลักษณะการทำงานของฟังก์ชันนี้เป็นดังในรูปที่ 7.3 ที่ต้องการหาค่าของ 35 เริ่มต้นด้วย Power (3.0, 5) เรียกตัวเองมาทำงานลงไปเรื่อย ๆ จนถึงส่วนกรณีพื้นฐาน จากนั้นถอยกลับขึ้นมาตามทางเดิม ซึ่งคำตอบที่ได้ คือ 243.0

 

ผลลัพธ์ที่ได้

ลักษณะฟังก์ชันรีเคอร์ซิฟที่ผ่านมา การทำงานในส่วนแรกตัวเองให้ขึ้นมาจะมีการเรียกเพียงครั้งเดียว แต่บางฟังก์ชันอาจต้องมีการเรียกตัวเองขึ้นมาทำงานได้มากกว่าหนึ่งครั้ง เช่น การหาตัวเลขไฟโบแนคซี (Fibonacci Number) คือ 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, … โดยเริ่มต้นเลข 0 กับ 1 จากนั้นเลขถัดไปจะเท่ากับเลขก่อนหน้าสองตัวมาบวกกันเมื่อนำมากำหนดเป็นฟังก์ชันรีเคอร์ซิฟก็จะได้กฎเกณฑ์เป็นดังนี้

f0 = 0

f1 = 1

= f n-1 + f n-2  , for n > 1

จากกฎเกณฑ์ดังกล่าวแบ่งเป็นสองส่วน ส่วนกรณีพื้นฐาน คือ f0 = 0 กับ f1 = 1 ส่วนเรียกตัวเอง คือ f n = fn-1 + fn-2 เขียนเป็นฟังก์ชันรีเคอร์ซิฟ Fib ได้เป็นตารางที่ 7.2

ตารางที่ 7.2 ฟังก์ชันหาค่าตัวเลขไฟโบแนคซี

long fib (int  n ) {if (n < 1)return 0 ;

if (n < 3)

return 1;

return fib (n-1) + fib (n-2);

เมื่อต้องการทราบตัวเลขไฟโบแนคซีในลำดับที่ 4 จะเรียกฟังก์ชันรีเคอร์ซิฟด้วย Fib (4) ลักษณะการทำงานของฟังก์ชันนี้ได้เป็นดังในรูปที่ 7.4

จากรูปที่ 7.4 เป็นฟังก์ชันที่เรียกตัวเองขึ้นมาทำงานและมีพารามิเตอร์ส่งค่ามาในแบบเดียวกันมีลักษณะที่เรียกว่าทรีรีเคอร์ซิฟ (Recursive Tree) เนื่องจากส่วนเรียกตัวเองมีการเรียกตัวเองมาทำงาน 2 ครั้ง ทำให้มีการเรียกตัวเองซ้ำมา 2 ครั้งกับพารามิเตอร์ 0 เรียกซ้ำมา 3 ครั้งกับพารามิเตอร์ 1 และเรียกซ้ำมา 2 ครั้งกับพารามิเตอร์ 1 จะเห็นว่าในช่วงท้ายของการเรียกตัวเองมีการเรียกซ้ำตัวเดิมที่มีพารามิเตอร์เท่ากัน เมื่อนับจำนวนการเรียกตัวเองมาทำงานของ Fib (4) หรือรูปที่ 7.4 จะได้เท่ากับ 9 ครั้งเป็น ดังนี้

จำนวนการเรียกตัวเอง

Fib (4)                   1

Fib (3)                   1

Fib (2)                   2

Fib (1)                   3

Fib (0)                   2

พิจารณากับฟังก์ชันรีเคอร์ซิฟที่เรียกด้วย Fib (5) จะเรียกตัวเองที่พารามิเตอร์ 5 ในครั้งแรก 1 ครั้ง เรียกตัวเองที่พารามิเตอร์ 4 มีจำนวนการเรียก 9 ครั้ง และเรียกตัวเองที่พารามิเตอร์ 3 มีจำนวนการเรียก 5 ครั้ง จำนวนการเรียกตัวเองทั้งหมดจะเท่ากับ 15 แต่ถ้าเริ่มต้นที่ Fib (6) จำนวนการเรียกตัวเองทั้งหมดจะเท่ากับ 25 ซึ่งเป็นการเพิ่มจำนวนอย่างรวดเร็วในลักษณะของเอ็กโปแนนเซีล(Exponential, xn) สร้างเป็นตารางการเพิ่มจำนวนครั้งการเรียกตัวเองตามลำดับค่าดังรูปที่ 7.5

n

Fib (n)

 

n

Fib (n)

0

1

10

177

1

1

11

287

2

3

12

465

3

5

13

753

4

9

14

1,219

5

15

15

1,973

6

25

16

3,193

7

41

17

5,167

8

67

18

8,361

9

109

19

13,529

รูปที่ 7.5 ตารางการเพิ่มจำนวนครั้งการเรียกตัวเอง

                การแก้ปัญหาแบบรีเคอร์ซิฟกับการหาตัวเลขไฟโบแนคซีจึงไม่ใช่วิธีการที่ดีเมื่อค่า n มีค่ามากขึ้น แต่จะใช้วิธีการแบบวนลูปมาใช้แทนจะเหมาะสมกว่า เพียงแต่ต้องมีการเก็บค่าที่ได้จากการคำนวณและปรับปรุงค่าเพื่อนำไปใช้ในครั้งต่อไปในแต่ละรอบของการวนลูป ดังในตารางที่ 7.3 ซึ่งมีตัวแปร f2 เก็บผลรวมไว้และ f0 กับ f1 เก็บค่าลำดับถัดไปเพื่อใช้ในรอบถัดไปของการวนลูป

ตารางที่ 7.3 ฟังก์ชันหาค่าตัวเลขไฟโบแนคซีแบบวนลูป

long fibI (int n){

int i, f0, f1, f2;

if (n < 1)

return 0;

if (n < 3)

return 1;

f0 = 1;

f1 = 1;

for (I = 3; i <= n; i++){

f2 = f1 + f0;

f0 = f1;

f1 = f2;

}

return f2;

}

 

           

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

ตารางที่ 7.4 ฟังก์ชันหาค่าตัวเลขไฟโบแนคซีแบบใช้พื้นที่เพิ่ม

long fibM (int n){

int i;

long F[100];

if(n < 1)

return 0;

if(n < 3)

return 1;

f[1] = 1;

f[2] = 1;

for (i = 3; i <= n; i++)

F[i] = F[i-1] + F[i-2];

Return F[n];

}

   นอกจากนี้การเรียกตัวเองทำงานสองครั้งในส่วนเรียกตัวเองยังนำไปใช้กับปัญหาหอคอยฮานอย (Tower of Hanoi) การจัดเรียงลำดับข้อมูลแบบรวดเร็ว (Quick Sort) ซึ่งแต่ละครั้งที่เรียกตัวเองมาทำงานปัญหาจะถูกแบ่งเล็กลงเหลือเพียงครึ่งเดียว

ตัวอย่างการใช้ฟังก์ชันรีเคอร์ซิฟ

ตัวอย่างที่รู้จักซึ่งเหมาะสมกับการแก้ปัญหาแบบรีเคอร์ซิฟคือปัญหาหอคอยฮานอย (Tower of Hanoi) ซึ่งมีความยุ่งยากหากจะแก้ไขด้วยวิธีการอื่นที่ไม่ใช่รีเคอร์ซิฟ ปัญหาหอคอยฮานอยมีความซับซ้อนในการแก้ไข ดังในรูปที่ 7.6 เพื่อต้องการย้ายแผ่นไม้ทั้งหมดที่มีขนาดไม่เท่ากันจากเสาหลักด้านซ้ายไปที่เสาหลักด้านขวา และในการย้ายแผ่นจะมีกฎเกณฑ์ที่กำหนดไว้ดังนี้

1.       เมื่อมีการย้ายแผ่นไม้ จะต้องนำไปวางในเสาหลักเสาใดเสาหนึ่ง

2.       การย้ายแผ่นไม้จะย้ายได้ครั้งละแผ่น และเป็นแผ่นที่อยู่ข้างบนสุดของเสาหลัก

3.       แผ่นไม้ที่มีขนาดใหญ่กว่าไม่สามารถวางอยู่บนแผ่นไม้ที่มีขนาดเล็กกว่า

ลักษณะปัญหาหอคอยฮานอย

                จากตำนานเล่าว่ามีนักบวชลามะจากวัดแห่งหนึ่งได้มีพิธีกรรมที่เกี่ยวกับปัญหาที่ซับซ้อนซึ่งประกอบด้วยเจดีย์ทองคำ 3 ยอดซึ่งมีลักษณะเป็นเสาหลักเพื่อใช้วางแผ่นจานทองคำจำนวน 64 แผ่นซ้อนทับกัน แต่ละแผ่นมีขนาดเล็กลงไม่เท่ากัน และนักบวชจะต้องย้ายแผ่นจานจากเสาหลักหนึ่งตามกฎเกณฑ์ทั้งสามที่กล่าวมาปัญหาจึงจะสิ้นสุดลง ถ้านักบวชย้ายแต่ละแผ่นจานใช้เวลา 1 วินาทีและเริ่มต้นย้ายเมื่อปีที่ 0 อยากทราบว่าต้องใช้เวลานานเท่าไรจึงจะย้ายแผ่นจานทองคำสำเร็จ

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

ถ้าให้เสาหลักเป็นเสา A, B, C ตามลำดับจากซ้ายไปขวา และมีแผ่นจานหนึ่งแผ่น ก็จะย้ายจากเสา A ไปยังเสา B ปัญหานี้แก้ไขได้เมื่อมีแผ่นจาน n = 1 (เป็นการย้ายแผ่นจานทั้งหมดไปเก็บไว้ที่เสา B ส่วนอีกรูปแบบนำไปเก็บไว้ที่เสา C) แต่ถ้าการแก้ปัญหานี้สามารถใช้กับแผ่นจานจำนวน n-1 การแก้ปัญหา n แผ่นจะง่ายเมื่อใช้รีเคอร์ซิฟ ดังนี้

1.     ย้ายแผ่นจานจำนวน n -1 ที่อยู่บนสุดจากเสาหลัก A ไปไว้ยังเสาหลัก C โดยมีเสาหลัก B ทำหน้าที่ช่วยเหลือในการสลับแผ่นไปมา

2.       ย้ายแผ่นจานขนาดใหญ่สุดที่เหลืออยู่จากเสาหลัก A ไปไว้ยังเสาหลัก B

3.       ย้ายแผ่นจานจำนวน n-1 จากเสาหลัก C ไปไว้ยังเสาหลัก B

ตามลำดับเมื่อย้ายแผ่นจานจำนวน n-1 จากเสาหลัก A ไปไว้เสาหลัก C ก็จะต้องย้ายแผ่นจานจำนวน n-2 จากเสาหลัก A ไปไว้เสาหลัก B ก่อน จากนั้นจึงย้ายแผ่นจานที่ n-1 ไปไว้เสาหลัก C จากอัลกอริทึมดังกล่าวนำมาเขียนเป็นฟังก์ชันรีเคอร์ซิฟ Move Diskและเขียนเป็นโปรแกรมจะได้ดังในตารางที่ 7.5 คือ โปรแกรม Towers.c

ผลลัพธ์ที่ได้

                วิธีการแก้ปัญหาหอคอยฮานอยเมื่อเขียนเป็นโปรแกรมและให้ทำงานจะมีการรอรับค่าที่เป็นจำนวนแผ่นจานทั้งหมดไว้ที่เสาหลัก A และเรียกฟังก์ชัน MoveDisk ถ้ากำหนดให้แผ่นจานมีทั้งหมด 4 แผ่นได้เป็นในรูปที่ 7.7

จำนวนแผ่นจาน 4 แผ่นอยู่บนเสาหลัก A ตอนเริ่มต้น

                หลังจากนั้นฟังก์ชัน MoveDisk ทำการเรียกตัวเองมาทำงานพร้อมกับทำการย้ายแผ่นจานตามลำดับทีละแผ่น ดังในรูปที่ 7.8 ตั้งแต่รูป (a) จนถึงรูป (0) ซึ่งแผ่นจานทั้งหมดถูกย้ายไปอยู่ที่เสาหลัก B จำนวนการย้ายแผ่นจานทั้งหมดทีละแผ่นเท่ากับ 15 ครั้ง

ลำดับการย้ายแผ่นจานจากเสาหลัก A ไปไว้ที่เสาหลัก B

                การทำงานของฟังก์ชันนี้ถ้ามีแผ่นจาน 1 แผ่นจะมีการย้าย 1 ครั้ง มี 2 แผ่นจะมีการย้าย 3 ครั้ง และมี 3 แผ่นจะมีการย้าย 7 ครั้ง ซึ่งอยู่ในรูปแบบของ M (n) = 2n-1 ดังนั้น ถ้าแผ่นจานมีทั้งหมด 64 แผ่นจะมีการย้ายแผ่นจานจำนวนประมาณ 1.84 * 1019 ครั้ง หากการย้ายแผ่นแต่ละครั้งใช้เวลา 1 วินาทีจะต้องใช้เวลาทั้งหมดประมาณ 585 พันล้านปีจึงจะย้ายสำเร็จหรือให้คอมพิวเตอร์ทำการย้ายได้หนึ่งล้านครั้งต่อวินาทีจะใช้เวลาทั้งหมดประมาณ 585,000 ปี

 

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s