Google         youtube            psv            สพม.11

รีเคอร์ซิฟโดยอ้อม

                ตัวอย่างฟังชัน รีเคอร์ซิฟที่ผ่านมาจะเรียกว่ารีเคอร์ซิฟโดยตรง (Direct Recursion) คือฟังก์ชันที่เรียกตัวเองมาทำงานโดยตรง แต่จะมีรีเคอร์ซิฟโดยอ้อม (Indirect Recursion) ที่มีการเรียกฟังก์ชันอื่นมาทำงานและเป็นการเรียกแบบลูกโซ่ที่ ย้อนกลับมาเรียกฟังก์ชันแรก ดังในรูปที่ 7.9 ชนิดของรีเคอร์ซิฟโดยอ้อมแบบง่าย ๆ คือ รีเคอร์ซิฟสองฝ่าย (Mutual Recursion) ซึ่งมีสองฟังก์ชันที่ต่างเรียกฟังก์ชันตรงข้ามมาทำงาน และรีเคอร์ซิฟโดยอ้อมทั่วไป (General Indirect Recursion) ที่มีหลายฟังก์ชันเรียกต่อกันโดยฟังก์ชันสุดท้ายเรียกย้อนกลับมา ยังฟังก์ชันแรก

ชนิดของรีเคอร์ซิฟโดยตรงและโดยอ้อม

ตัวอย่าง ที่นำมาแสดงการใช้รีเคอร์ซิฟโดยอ้อมจะเป็นรีเคอร์ซิฟสองฝ่าย เป็นการคำนวณหาค่าทางตรีโกณมิติของ Sine และCose ซึ่งมีสมการคำนวณหาดังนี้

Sin2θ = 2 Sin2θcos2θ

cos2θ = 1-2(sinθ) 2

จะเห็นว่า Sin มีการเรียกตัวเองและเรียก Cos มาทำงานส่วน Cos มีการเรียก sin มาทำงาน ถ้าให้ x=2θ จะได้ θ=x/2 และแทนที่จะได้เป็น

Sin x = 2Sin(x/2)Cos (x/2)

Cos x = 1-2(Sin(x/2)) 2

จาก สมการดังกล่าวนำมาเขียนเป็นฟังก์ชันรีเคอร์ซิฟ Sine และ Cose ดังในตัวอย่าง โปรแกรม Mutual.c จากตารางที่ 7.6 เนื่องจากฟังก์ชัน Cose กำหนดขึ้นมาทีหลังทำให้ฟังก์ชัน Sine ที่ต้องการ เรียกใช้งานแต่มองไม่เห็น จึงต้องประกาศฟังก์ชัน Coseล่วงหน้า (Prototype) โดยกำหนดเฉพาะส่วนหัวของ ฟังก์ชัน (ในภาษาซี สำหรับภาษาปาสคาลจะมีคำสงวน Forward ต่อท้าย) ฟังก์ชันรีเคอร์ซิฟทั้งสองต้องมีสองต้องมีส่วนที่เป็นกรณีพื้นฐานเพื่อสิ้น สุดการทำงาน โดยกำหนดค่าเป็นขอบเขตซึ่งอยู่ในช่วง-0.01< x < 0.01

ตารางที่ 7.6 ตัวอย่างโปรแกรม Mutual.c

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#include<math.h>

double code(double x);

double cose(double x){

if((-0.01<x)&&(x><0.01))

return x-x*x*x/6;

return 2* sine(x/2)*cose(x/2);

}

double cose(double x);

if((-0.01<x)&&(x><0.01))

return 1.0-x*x/2;

return 1-2*sine(x/2)*sine(x/2);

}

main(){

double x;

printf(“- – – – – – – – – – – – – – – – \n”);

for(x=0.0; x<1.0; x+=0.1)

printf(“%f\t%f\n”,sine(x),sin(x));

printf(“- – – – – – – – – – – – – – – – \n”);

for(x=0.0; x<1.0; x+=0.1)

printf(“%f\t%f\n”,cose(x),cose(x));

getch();

}

               

ตัวอย่าง โปรแกรมในตารางที่ 7.6 นี้จะแสดงตารางค่าทางตรีโกณมิติของ Sine และ Cose โดยใช้ฟังก์ชันรีเคอร์ซิ ฟที่เขียนขึ้นมา และมีการแสดงค่าที่ได้โดยใช้ฟังก์ชัน Sin และ Cos ของภาษาซีที่ให้มา ซึ่งผลลัพธ์ของทั้งสองค่าเท่ากัน

การสับเปลี่ยนลำดับ

วิธี การอย่างหนึ่งที่นำมาใช้งาน คือ การเรียงลำดับค่าหรือข้อมูล (Sorting) ซึ่งเรียงจากค่าน้อยที่สุดไปยังค่า มากที่สุดตามลำดับหรือจากค่ามากที่สุดไปยังค่าน้อยที่สุด แต่ในบางครั้งอาจต้องการจัดลำดับค่าเหล่านี้ตามตำแหน่งที่ไม่ซ้ำแบบเดิม เรียกว่าการสับเปลี่ยนลำดับ (Permutation) เช่น มีสมาชิก A, B, C เมื่อสับเปลี่ยนลำดับได้เป็น ABC, ACB, BAC, BCA, CBA, CAB และจำนวนรูปแบบของการสับเปลี่ยนลำดับที่ไม่ซ้ำกันเลยเท่ากับ 6

ถ้า มีสมาชิก n ตัวที่แตกต่างกัน ดังนั้น การเลือกสมาชิกมาจัดลำดับในครั้งแรกจึงมีโอกาสเลือกได้ n ตัว ครั้งที่สองมีโอกาสเลือกได้ n-1 ตัว ไปเรื่อย ๆ จนถึงครั้งสุดท้ายจะเหลือเพียงตัวเดียว จำนวนรูปแบบที่เป็นไปได้ของการสับเปลี่ยนลำดับได้เป็น n! (n Factorial) ซึ่งจะมากขึ้นอย่างรวดเร็ว เช่น มีสมาชิก 1 ตัวจะมี 1 แบบ ถ้า 3 ตัวจะมี 6 แบบ ถ้า 5 ตัวจะมีถึง 120 แบบ ปัญหาการสับเปลี่ยนลำดับไม่ได้ขึ้นกับจำนวนรูปแบบที่มากขึ้นอย่างรวดเร็ว แต่เป็นเรื่องแบบของการสับเปลี่ยนลำดับโดยการทำงานเป็นแบบวนลูปซ้อนกัน และใช้กับสมาชิก n=3

ตารางที่ 7.7 ฟังก์ชัน Permute3

void permute3 (){

int  i, j, k;

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

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

if(j= = i)

continue;

for(k=0;k<3;k++){

if(k= =i | | k= =j)

continue;

printf(“%d %d %d\n”, i, j, k);

}

}

}

 

                ฟังก์ชันนี้มีการวนลูปซ้อนกัน 3 ลูป โดยตัวแปร k จะสร้างได้ 18 แบบจากทั้งหมด 27 แบบที่ค่าของตัวแปร k กับ j ไม่เท่ากัน และเหลือเพียง 6 แบบที่ค่าของตัวแปรทั้งสามไม่เท่ากันฟังก์ชันนี้ง่ายในการเขียนขึ้นมาก แต่ถ้าต้องการสับเปลี่ยนลำดับสำหรับสมาชิก 4 ตัวก็ต้องเขียนฟังก์ชันขึ้นมาใหม่ ดังนั้นทำอย่างไรที่จะให้ฟังก์ชันสามารถสับเปลี่ยนลำดับสำหรับสมาชิกกี่ตัว ก็ได้

เมื่อนำฟังก์ชันรีเคอร์ซิฟมาใช้ทำงานแทนการวนลูปมีความเป็นไป ได้ที่เหมาะสมกว่า ถ้าให้ p(n) เป็นจำนวนการสับเปลี่ยนลำดับของสมาชิก n ตัว โดยที่ p(1)=1 และ p(2)=2  และได้ p(n) =n*p(n-1) ทำให้ทราบว่า p(n)=n! สำหรับ n>0 ซึ่งเป็นฟังก์ชันแฟคทอเรียล มีการทำงานเป็นแบบรีเคอร์ซิฟ ดังนั้น ก็จะได้ฟังก์ชันการสับเปลี่ยนลำดับที่เป็นแบบรีเคอร์ซิฟดังในตารางที่ 7.8 คือ ฟังก์ชันPermute ที่ใช้ในตัวอย่างโปรแกรม Permute.c

 

ตารางที่ 7.8 ตัวอย่างโปรแกรม Permute.c

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

void print (char *s, int 1){

int i;

for( i = 0; i <= 1; i++ )

printf(“%c”,s[i]);

printf(“\n”);

}

void swap ( char *s, int i, int j ){

char tmp = s[i];

s[i] = s[j];

s[j] = tmp;

}

void permute( char *s, int k, int m ){

int i;

if( k = = m)

print( s,m );

else

for( i = k; i <= m; i++ ){

swap( s,k,i);

permute( s,k+1,m );

swap ( s,k,i );

}

}

main (){

char str[] = {“01234”};

printf(“- – – – – -\n”);

permute( str,0,2 );

getch();

}

จากตัวอย่างโปรแกรมเป็นการสับเปลี่ยนลำดับที่มีสมาชิก 3 ตัว คือ 0, 1, 2 โดยเรียก Permute (str, 0, 2) ขึ้นมาทำงาน หากต้องการใช้ 4 ตัว คือ 0, 1, 2, 3 ก็จะเรียก Permute (str, 0, 3) มาทำงานแทนได้เลย

นอกจากฟังก์ชันรีเคอร์ซิฟจะนำมาใช้แทนการทำงานแบบวนลูปที่มีความเหมาะสมกว่า

แล้ว ในบางครั้งการแก้ปัญหาบางอย่างไม่สามารถใช้การทำงานแบบวนลูปได้ จะใช้ได้เฉพาะฟังก์ชันรีเคอร์ซิฟ เช่น ฟังก์ชันแอคเคอร์แมน (Ackerman’s Function) ซึ่งมีกฎเกณฑ์ ดังนี้

a (m, n) = n+1                                      if m = 0

a (m, n) = a (m-1, n)                           if m ≠ 0, n = 0

a (m, n) = a (m-1, a (m, n-1))          if m ≠ 0, n ≠ 0

ขั้นตอนการทำงานแบบรีเคอร์ซิฟ

                การ ทำงานในคอมพิวเตอร์จะคอยดูเส้นทางการทำงานของโปรแกรมหรือโปรแกรมย่อยที่ถูก เรียกขึ้นมาทำงาน ดังนั้น ก่อนที่โปรแกรมหรือโปรแกรมย่อยจะเริ่มทำงานจะมีการบันทึกเก็บข้อมูลข่าวสาร เดิมที่กำลังใช้งานอยู่ในขณะนั้นเพื่อจะนำกลับมาใช้ต่อไปหลังจากที่โปรแกรม หรือโปรแกรมย่อยทำงานจบสิ้นลง โดยคอมพิวเตอร์มีการจัดสรรพื้นที่หน่วยความจำ ส่วนหนึ่งเก็บข้อมูลข่าวสารเหล่านี้ และเรียกว่า แอคติเวชั่นเรคคอร์ด (Activation Record) เมื่อมีโปรแกรมย่อยหนึ่งถูกขัดจังหวะ (Interrupt) จากโปรแกรมย่อย อื่นก็จะมีการเก็บค่าของตัวแปรพารามิเตอร์ แอดเดรสถอยกลับ (Return Address) และค่าอื่นๆ ของโปรแกรมย่อยที่ถูกขัดจังหวะไว้ในแอคติเวชั่นเรคคอร์ด หลังจากที่โปรแกรมย่อยอื่นทำงานเสร็จก็จะนำค่าต่างๆ ก่อนถูกขัดจังหวะที่อยู่ในแอคติเวชั่นเรคคอร์ดกลับมาใช้ต่อไป

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

เพิ่มรูป

รูปที่ 7.10 ลำดับการเรียงฟังก์ชัน B และ C มาทำงานของโปรแกรม A

                จะ เห็นว่าโปรแกรมย่อยที่ถูกขัดจังหวะครั้งสุดท้ายจะเป็นโปรแกรมย่อยแรกที่กลับ มาทำงานก่อนในลักษณะของสแตก ดังนั้น จึงนำสแตกดำเนินการ (Execution Slack) มาใช้เก็บแอดเดรสของแอคติเวชั่นเรคคอร์คที่สร้างขึ้นมาและมีการดึง ค่ามาใช้ง่านเป็นแบบเข้าทีหลังออกก่อน ( Last-In-First-Out) ในความเป็นจริงการถอยกลับไม่ได้กลับไปยังโปรแกรมย่อยที่ ถูกขัดจังหวะโดยตรง แต่จะไปที่สแตกดำเนินการทำการดึงแอคติเวชั่นเรคคอร์ดออกมาและนำแอดเดรสถอย กลับที่เก็บไว้อ้างกลับไปยังโปรแกรมย่อยที่ตำแหน่งเดิมอีกทีหนึ่ง

จาก ตัวอย่างฟังก์ชันรีเคอร์ซิฟ Power ในตอนต้นของบทนี้ และส่วนการทำงานของโปรแกรม Main ที่เรียกฟังก์ชัน Powerมาทำงานดังในตาราง ที่ 7.9 โดยมี M และ P เป็นตำแหน่งแอดเดรสถอยกลับหลังจากเรียกฟังก์ชันอื่นมาทำงาน

ตารางที่ 7.9 ฟังก์ชัน Power และฟังก์ชัน Main

double power (double x, int n){

if(n = = 0)

return 1;

else

return x * power(x, n-1); (P)

}

main (){

…;

…;

…;

y = power (2.0,3); (M)

…;

…;

…;

}

เพิ่มรูป

รูปที่ 7.11 การเก็บข้อมูลข่าวสารในแอคติเวชั่นเรคคอร์ด

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

เมื่อ โปรแกรม Main ถูกขัดจังหวะในระหว่างทำงานเนื่องจากมีการเรียกฟัง ชัน Power พร้อมกับส่งค่าพารามิเตอร์ให้ คือ 2.0 และ 3 ค่าพารามิเตอร์และแอดเดรสถอยกลับ M รวมกับค่าอื่น ๆ จะถูกนำไปเก็บไว้ที่แอคติเวชั่นเรคคอร์ดที่สร้างขึ้นมาและเก็บลงในสแตกดังใน รูปที่ 7.12 (a) จากนั้นฟังก์ชัน Power ก็เริ่มต้นทำงานในครั้งแรกพร้อมกับสร้างแอ คติเวชั่นเรคคอร์ดขึ้นมา เมื่อฟังก์ชันทำงานถึงคำสั่ง Return x * Power(x, n-1); ก็จะถูกขัดจังหวะ ค่าพารามิเตอร์ 2.0, 2 และแอดเดรสถอยกลับ P1 ถูกนำไปเก็บไว้ที่แอคติเวชั่นเรอคอร์ดและเก็บลงใน สแตกดังในรูปที่ 7.12 (b)

เพิ่มรูป

รูปที่ 7.12 ลำดับการเรียกฟังก์ชันรีเคอร์ซิฟ Power กับการเก็บแอคติเวชั่นเรคคอร์ดลงในสแตก

                ฟังก์ชัน Power เป็น แบบรีเคอร์ซิฟมีการเรียกตัวเองขึ้นมาทำงานครั้งที่สองและสร้างแอคติเว ชั่นเรคคอร์ดขึ้นมา เมื่อถูกขัดจังหวะค่าพารามิเตอร์ 2.0, 1 และแอดเดรสถอยกลับ P2 เก็บไว้ที่แอคติเวชั่นเรคคอร์ดและเก็บลงในสแตกดังใน รูปที่ 7.12 (c) เมื่อเรียกมาทำงานครั้งที่สามและถูกขัดจังหวะค่าพารามิเตอร์ 2.0, 0 และแอดเดรสถอยกลับ P3 เก็บไว้ที่แอคติเวชั่นเรคคอร์ดและเก็บลงในสแตกดังใน รูปที่ 7.12 (d) การทำงานของฟังก์ชัน Power ที่มีค่าพารามิเตอร์ 2.0, 0 จะทำในส่วนกรณีพื้นฐานจึงไม่มีการขัดจังหวะ

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

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