/ BasicKnowledge

[365 วันแห่งโปรแกรม #day23] Recursion

วันที่ยี่สิบสามของ ‪#‎365วันแห่งโปรแกรม‬ วันนี้เราจะมีคุยกันเรื่อง Recursion


Recursion คืออะไร?

Recursion ในทางคอมพิวเตอร์หมายถึงกระบวนการแก้ปัญหาโดยการแบ่ง solution ออกเป็นส่วนย่อยๆ ที่ใช้แก้ปัญหาเดียวกัน

โปรแกรมเมอร์ส่วนใหญ่จะรู้จักเรื่อง recursion จาก recursive function หรือฟังก์ชันเรียกตัวเอง ซึ่งนั่นเป็นวิธีหลักที่เราใช้ในการแยกตัวปัญหาออกเป็นส่วนเล็กๆ

Factorial

Recursion ในการเขียนโปรแกรมนั้นก็มาจากวิธีการในคณิตศาสตร์เช่นกัน ทำให้นักคณิตศาสตร์จะเคยกับการทำ recursion มากกว่าการเขียน iteration และส่งผลให้ภาษาโปรแกรมที่เป็น Pure Functional ไม่มี syntax สำหรับทำ iteration

ด้านล่างนี้เป็นนิยามทางคณิตศาสตร์ของฟังก์ชัน Factorial

Factorial 0 = 1;
Factorioal n = n * Factorial n - 1

Factorial เป็นตัวอย่างที่ดีสำหรับใช้ในการเปรียบเทียบวิธีเขียน solution แบบ recursion และแบบ iteration

long factorial_recursion(long n){
	if (n <= 0)
		return 1;
	return n * factorial_recursion(n - 1);
}

โค้ดด้านบนนี้เป็นการเขียนแบบ recursion จะเห็นว่ามีการเรียกตัวเองในส่วนของ return

เราสามารถเปลี่ยนโค้ดด้านบนนี้เป็นแบบ iteration ได้ ดังนี้

long factorial_iteration(long n){
	long result = 1;
	for (; n > 0; n--){
		result *= n;
	}
	return result;
}

Recursion มีข้อเสียหรือไม่?

เมื่อพิจารณาโค้ดด้านบนทั้งสองอันแล้ว จะพบว่าเมื่อ n มีค่ามาก ก็ยิ่งมีการเรียกตัวเองซ้อนกันมากครั้ง นั่นทำให้ เกิด stack frame ซ้อนกันอยู่เป็นจำนวนมาก ซึ่งอาจจะทำให้เกิด stack overflow ได้

สำหรับการทำ iteration ปกติ จำนวน stack frame จะคงที่ตลอดเวลา เพราะ ไม่มีการเรียกใช้งานฟังก์ชันอื่น

แก้เรื่อง stack overflow ได้ไหม

แน่นอนว่าทุกปัญหาย่อมมีทางออก และทุกทางออกก็ย่อมมีปัญหา ในคอมไพเลอร์ของหลายๆ ภาษาโปรแกรม มี option สำหรับ optimize การทำ recursion เรียกว่า tail call optimization แต่มีข้อจำกัดว่า จะต้องเขียน recursive function แบบ tail recursive เท่านั้น

Tail Recursive คืออะไร?

Tail Recursive คือรูปแบบของ recursive function ที่จบด้วยการเรียกตัวเองซ้ำ แล้ว return ทันที

ตัวอย่างแรกนั้น ไม่ถือว่าเป็น tail recursive เพราะว่าในส่วนของการ return หลังจากทำการเรียกตัวเองแล้ว ยังมีการเอาผลที่ได้ไปคูณด้วย n อีกที

เราสามารถแก้ recursive function ข้างต้นให้เป็น tail recursive ได้โดยส่งค่า result ปัจจุบัน เข้าไปในฟังก์ชันที่เรียก แล้วเมื่อถือส่วน tail (การเรียกตัวเองครั้งสุดท้าย) แล้วจะคืนผลลัพธ์กลับมาโดยไม่ทำอะไรเพิ่มเติม

long factorial_tail_recursion(long n){
	return factorial_tail_recursion(n, 1);
}

long factorial_tail_recursion(long n, long result){
	if (n <= 1)
		return result;
	return factorial_tail_recursion(n - 1, n * result);
}

จากตัวอย่างนี้จะเห็นว่าเราแบ่งฟังก์ชันออกเป็นสองอัน อันแรกสำหรับให้ user ใช้ อีกอันสำหรับทำงานจริงๆ (จริงๆ ต้องประกาศฟังก์ชันที่สองเป็น private ด้วย เพื่อให้เป็นไปตามหลักของ encapsulation)

ฟังก์ชันที่สองมีการส่งค่าผลลัพธ์ของปัจจุบันเข้าไปเรื่อยๆ จน n = 1 ดังนั้น จึงถือว่า function นี้เป็น tail recursive

Tail Call Optimization

เมื่อฟังก์ชันกลายเป็น tail recursive แล้ว คอมไพเลอร์จะสามารถแปลงโค้ดไปอยู่ในรูปแบบของ iteration แบบ goto ได้

long factorial_tail_recursion_optimized(long n){
	return factorial_tail_recursion_optimized(n, 1);
}

long factorial_tail_recursion_optimized(long n, long result){
begin:
	if (n <= 1)
		return result;
	result = result * n;
	n = n - 1;
	goto begin;
}

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

หลังจากนั้นเมื่อ optimize เข้าไปอีก คอมไพเลอร์จะทำการยุบรวมฟังก์ชันที่ไม่ถูกเรียกจากที่อื่นเข้าเป็นฟังก์ชันเดียวกัน จะได้ว่า

long factorial_tail_recursion_optimized(long n){
	int result = 1;
begin:
	if (n <= 1)
		return result;
	result = result * n;
	n = n - 1;
	goto begin;
}

เพียงเท่านี้โปรแกรมของเราก็จะมี performance ดีขึ้นแล้ว

แล้วทำไมใช้ใช้ iteration ไปเลยล่ะ?

ทุกปัญหาที่แก้ด้วย recursion ได้ ก็ย่อมสามารถแก้ด้วย iteration (loop) ได้เช่นกัน แต่ในหลายๆ สถานการณ์ การทำ iteration ดูเป็นเรื่องที่ซับซ้อนเกินไป เช่นการค้นหาข้อมูล ดังนั้นการใช้ recursion จึงทำให้ชีวิตเราสบายขึ้นแล้วก็ปล่อยให้ คอมไพล์เลอร์ optimize ไป รวมไปถึงในบางภาษาที่เป็น Functional ก็ไม่มี iteration ให้ใช้ด้วย ดังนนั้นโปรแกรมเมอร์ทุกคนควรจะเขียนได้ทั้งสองแบบครับ

‪#‎day23 #365วันแห่งโปรแกรม ‪#‎โครงการ365วันแห่ง‬...