BlogGang.com : : Aufklarung : Recursion ทำได้อย่างไร และ เพื่ออะไร

Recursion ทำได้อย่างไร และ เพื่ออะไร

เกริ่นนำ
ทุกท่านที่เขียนโปรแกรมโครงสร้างเป็นคงจะจำได้นะครับ ว่าโปรแกรมโครงสร้างประกอบด้วยหลักๆคือ

- การวนซ้ำ หรือ Loop เช่น for,while,foreace เป็นต้น
- เงื่อนไข+กระโดด หรือ If-Then-Else,switch case เป็นต้น
- อื่นๆ ซึ่งเรายังไม่สนใจในเวลานี้ (ผู้เขียนลืมครับ แหะๆ)

แล้วการวนซ้ำมีกี่แบบล่ะ?
หลักๆที่ใช้กันก็มี 2แบบครับคือ

1. Iteration Loop
ตัวอย่างง่ายๆเลยก็พวก For หรือ While นั่นแหล่ะครับ Loop ประเภทนี้ง่าย ตรงไปตรงมา เช่น
For x := 1 to 10 do
ก็จะทำ expression โดย เพิ่มค่า X ตั้งแต่ 1 ไปจนถึง 10 (เพิ่มครั้งละ 1)

บาง compiler จะสามารถกำหนด step ได้ เช่น

For x := 1 to 10 step 2 do
ก็จะทำ expression โดย เพิ่มค่า X ตั้งแต่ 1 ไปจนถึง 10 (เพิ่มครั้งละ 2)

2. Recusion Loop
เจ้านี่เป็นเรื่องหลักที่จะกล่าวถึงในหัวข้อนี้ครับ ถามว่ามี loop แบบ iteration แล้ว ทำไมต้องมี
Recursion อีก คำตอบคือ iteration loop ไม่เหมาะกับงานบางอย่างครับ ยกตัวอย่างเช่น
- การท่องไปในโครงสร้าง tree
- การวน loop เพื่อหาค่าของ sieriesประหลาดๆ เช่น Fibonacci,Factorial
- การใช้งาน loop แบบเงื่อนไขไม่แน่นอน เช่น สร้างโปรแกรมที่ใช้แก้ปัญหา tower of hanoi ซึ่ง
loop พวกนี้จะมีจำนวนครั้งการวนไม่แน่นอนขึ้นกับเงื่อนไขบางอย่าง
หมายเหตุ มิใช่ Iteration จะทำงานพวกนี้ไม่ได้นะครับ คนที่เขียนโปรแกรมเก่งๆ สามารถทำได้เช่นกัน แต่โปรแกรม
ที่ได้อาจจะยาว และ ซับซ้อน ซึ่งโปรแกรมแบบ recursion จะดูง่ายกว่า

แล้ว Loop แบบ Recursionเขียนได้อย่างไรล่ะ ?
ง่ายมากครับ Recursion ประกอบด้วย 2 ส่วนเท่านั้น คือ
1. เงื่อนไขจบ เมื่อจบ ให้คืนค่าออกไป exit condition,return
2. ถ้าไม่จบ ก็เรียกตัวเองซ้ำลงไป recursion

งงใหมล่ะครับ ดูตัวอย่างดีกว่า

EXAMPLE#1ตัวอย่างที่1
อ้างอิงจาก //en.wikipedia.org/wiki/Factorial

ตัวอย่างที่นิยมที่สุดคือเจ้า factorialครับ (เขียนเป็นเครื่องหมายตกใจในเครื่องคิดเลข เช่น 5!
หมายถึง factorial ของ 5)
สูตรของเจ้า factorial คือ fac(n) = n * fac(n-1) คุ้นๆใหมครับ เหมือนข้อ 2ใหมครับ
เราจะยกเจ้านี่ไว้เป็นข้อ 2ละกัน
แล้วเงื่อนไขการจบละ มีต้องวน loopจนเป็นอนันต์เลยรึอย่างนี้ ไม่ครับ มีเงื่อนไขอยู่อันนึงคือ fac(0) = 1 ครับ ดังนั้น
ทดลองเขียนเป็นตัวเลขง่ายๆ เช่น
fac(5) = 5*fac(4)
fac(4) = 4*fac(3)
fac(3) = 3*fac(2)
fac(2) = 2*fac(1)
fac(1) = 1*fac(0) <-- แต่fac(0)ดันเท่ากลับ1
ดังนั้น
fac(0) = 1
fac(1) = 1*1 = 1
fac(2) = 2 * 1
fac(3) = 3 * 2 = 6
fac(4) = 4 * 6 = 24
fac(5) = 5 * 24 = 120 <-- ได้คำตอบละ
แล้วถ้าจะเขียนเป็นโปรแกรมล่ะ ตามนี้เลยครับ

fucntion fac(n is number) return number
begin

if n == 0 then return 1 //ส่วนที1
else return n * fac(n-1) //ส่วนที่2

end
ง่ายดีใหมครับ แล้วถ้าจะทำ iteration loopล่ะ ทำได้ใหม? คำตอบคือได้เหมือนกัน ตามนี้ครับ

function fac(n is number) return number
begin

declare i is number
declare result is number default 0
for i := 0 to n do
begin
if i == 0 then
result = 1
else
result = i * result
end for

return result
end
EXAMPLE#2 ตัวอย่างที่2
อ้างอิงจาก //en.wikipedia.org/wiki/Fibonacci_number

รู้จัก Fibonacci Sequence ใหมครับ มันเป็นอนุกรมของตัวเลขที่มีความสัมพันธ์ประหลาด
เช่น Fibonacci ของ 5 จะเท่ากับ 0,1,1,2,3,5
เงื่อนไขของ fibonacci number คือ
fib(0) = 0
fib(1) = 1 <-- 2 อันนี้เป็นเงื่อนไขจบนะครับ
fib(n) = fib(n - 1) + fib(n-2) เมื่อ nต้องไม่เป็นลบดังนั้น nต้องมากกว่าหรือเท่ากับ 2
เช่น
fib(5) = fib(4)+fib(3)
fib(4) = fib(3)+fib(2)
fib(3) = fib(2)+fib(1)
fib(2) = fib(1)+fib(0)
แต่เมื่อ fib(1) = 1 และ fib(0) = 0
จะได้
fib(0) = 0
fib(1) = 1
fib(2) = 1 + 0 = 1
fib(3) = 1 + 1 = 2
fib(4) = 2 + 1 = 3
fib(5) = 3 + 2 = 5

จับมาเขียนเป็น Recursion ได้ดังนี้
function fib(n is number) return number
begin

if n == 0 then return 0
else
if n == 1 then return 1
else

return fib(n - 1) + fib(n - 2)
end
ลอง Iteration บ้างสิ
function fib(n is number) return number
begin

declare i is number
declare r1,r2 is number
declare result is number
r1 := 0
r2 := 0
result := 0
for i := 0 to n then
if i == 0 then result = 0
else
if i == 1 then result = 1
else
begin
result = r1 + r2
end
r2 := r1
r1 := result
end for

end
สรุป
อ้าว แล้วทำไมจึงต้องจำการเขียน loop หลายๆแบบด้วยล่ะ คำตอบ ต้องลองมองดูโปรแกรมเทียบกันดูครับ
โปรแกรมแบบ recursionจะสั้น เรียบง่ายและตรงกับสูตรหรือวิธีคิดเป๊ะๆครับในขณะที่iteration
จะยาวกว่า และยาวกว่ามากกรณีที่เงื่อนไขการจบซับซ้อน

แล้วrecursion loop มีการใช้งานจริงหรือ คำตอบคือ มีครับเยอะด้วย เช่น
- การท่อง tree
- graph
- AI. โปรแกรม AI จำนวนมากที่ใช้ loop ชนิดนี้
- sorting ต่างๆที่ใช้ tree
- เมื่อมี sorting ก็ต้องมี searching
- ปัญหาเฉพาะอื่นๆ ฯลฯ

Create Date : 09 มกราคม 2550

Last Update : 9 มกราคม 2550 22:39:39 น.

0 comments

Counter : 2185 Pageviews.