C# Tutorial ตอนที่ 9 (recursive method)
posted on 11 Jul 2005 16:32 by tidno1 in csharp-and-dotnetRecursive method
ปกติแล้ว เราสามารถเรียก method นึงจากอีก method นึงได้
...
}
static void G() {
...
F();
}
ดังนั้นแล้วการจะเรียก method ตัวเองก็คงไม่ใช่เรื่องแปลก
...
F();
}
ดู ๆ แล้วอาจจะ non-sense นะครับ แต่ในความเป็นจริงแล้วการเขียนโปรแกรมแบบ recursive นี่ก็ช่วยให้โปรแกรมเขียนง่ายขึ้นมาก
ตัวอย่างที่เห็นได้ชัด ก็คือการนิยาม Factorial ในทางคณิตศาสตร์
นั่นก็มองเหมือนเป็นการเรียกฟังก์ชัน Factorial แบบ recursive ครับ ถ้าเขียนเป็นโปรแกรมก็คงเขียนได้แบบนี้
int fac;
if(n == 0) {
fac = 1;
} else {
fac = n * Fac(n - 1);
}
return fac;
}
แต่เขียนแบบข้างบนคงยาวไปหน่อย ปกติเค้าเขียนกันสั้น ๆ แบบนี้
if(n == 0) {
return 1;
}
return n * Fac(n - 1);
}
เขียนแบบเชิงคณิตศาสตร์ก็ประมาณนี้
= 3 * 2 * 1!
= 6 * 1 * 0!
= 6 *
= 6
ถ้าไม่มีตรง if(n ==0) ... คงคิดออกกันใช่มั้ยครับ ว่ามันคงเรียก method นี้ไม่จบ ดังนั้นจำไว้นะครับ การเขียน recursive method ทุกครั้งต้องมีการเช็ก ให้หยุดการเรียก method ที่ค่า ๆ หนึ่ง
ลองดูตัวอย่างยอดฮิตอีกอย่างนึงของเรื่องนี้ คือ fibonacci number
fn = fn - 1 + fn - 2
ถ้าเขียนเป็น method ก็ควรได้อย่างนี้
if(n == 0) {
return 0;
}
if(n == 1) {
return 1;
}
return Fibo(n - 1) + Fibo(n - 2)
}
recursive method สามารถเขียนกับกรณีอื่น ๆ ได้อีก ไม่เฉพาะตัวเลขเท่านั้น เช่นในเชิง data structure ก็ทำ tree traversal ด้วยวิธี recursive
หรือในทางคณิตศาสตร์มีนิยามสมาชิก set ของจำนวนเต็มไว้แบบหนึ่ง โดยแค่นิยาม constant และ ฟังก์ชันบางอย่างดังนี้
- constant 0
- successor function succ ซึ่งให้ค่าตัวถัดไป
- predecessor function pred ซึ่งให้ค่าตัวก่อนหน้านี้
- ...
ดังนั้นจะนิยาม set ของจำนวนเต็มได้ดังนี้
และนิยามต่อมาคือ operator +, - ของ set นี้ หรือจะมองเป็นฟังก์ชัน บวก, ลบ ก็ได้
add(n, 0) = n
add(n, m) = add(succ(n), pred(n))
sub(n, 0) = n
sub(n, m) = sub(pred(n), pred(m))
เราสามารถเขียนฟังก์ชัน ข้างบนนี้ได้ โดยการนิยาม succ, pred ด้วย operator ++, -- เช่น
if(m == 0) {
return n;
}
return Add(++n, --m);
}
static int Sub(int n, int m) {
if(m == 0) {
return n;
}
return Sub(--n, --m);
}
แต่อาจจะมองแล้วไม่เท่ เอาให้มองสวยหน่อยก็สร้าง method Succ กับ Pred มาก็ดี (ถ้าทำโจทย์ข้อนี้ด้วยภาษา pascal ก็มีฟังก์ชัน pred กับ succ ให้ใช้เลย)
return ++n;
}
static int Pred(int n) {
return --n;
}
static int Add(int n, int m) {
if(m == 0) {
return n;
}
return Add(Succ(n), Pred(m));
}
static int Sub(int n, int m) {
if(m == 0) {
return n;
}
return Sub(Pred(n), Pred(m));
}
static int Mul(int n, int m) {
...
}
static int Fac(int n, int m) {
...
}
ลองเขียน Mul กับ Fac ต่อ เป็นการบ้านละกันครับ
Hint : ลองนึกถึงนิยามการคูณดูครับ
อ้อ เสริมเล็กน้อย การเขียน method แบบ recursive นี้มีข้อระวังเล็กน้อย คือไม่ควรจะมีการเรียก method นั้นหลายชั้นมากจนเกินไป(โดยเฉพาะการเขียนไม่ครอบคลุม เช่นการเช็กการหยุดการเรียก method ผิด) เพราะจะทำให้ stack ของระบบ overflow ได้
)
จริงๆ แล้วโจทย์ข้อนี้ถือว่าเป็น Bad Practice นะ แต่ยังคิดไม่ออกเลยว่าจะหาโจทย์อย่างอื่นที่ใช้ได้จริง และเข้าใจง่ายด้วยมาใช้ยังไง
#1 By ลิ่ว on 2005-07-11 17:43