9.1 ฟังก์ชันที่เรียกตัวเอง

น้องต่อแถวซื้อข้าวที่ยาวมาก มองไม่เห็นหัวแถว อยากรู้ว่าตัวเองอยู่ลำดับที่เท่าไร วิธีหนึ่งคือสะกิดถามคนข้างหน้าว่า "เธออยู่ลำดับที่เท่าไร" แล้วเอาคำตอบมาบวกหนึ่ง คนข้างหน้าก็ไม่รู้เหมือนกัน เลยถามคนข้างหน้าเขาต่อ ถามต่อกันไปเรื่อยๆ จนถึงคนแรกสุด ซึ่งไม่มีใครอยู่ข้างหน้าแล้ว ตอบได้ทันทีว่า 1 จากนั้นคำตอบก็ส่งกลับมาทีละคน 2 3 4 จนถึงน้อง

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

ฟังก์ชันนับถอยหลัง

นับถอยหลังปล่อยจรวดจาก n ถึง 1 แล้วพิมพ์ liftoff ถ้าคิดแบบแถวซื้อข้าว การนับถอยหลังจาก 3 คือพิมพ์ 3 แล้ว นับถอยหลังจาก 2 ซึ่งเป็นงานเดิมที่เล็กลง

#include <stdio.h>

void countdown(int n)
{
    if (n == 0) { // (1)!
        printf("liftoff\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1); // (2)!
}

int main()
{
    countdown(3);
    return 0;
}

1. กรณีฐาน (base case) กรณีที่เล็กพอจะตอบได้ทันทีโดยไม่ต้องเรียกตัวเอง เหมือนคนแรกในแถว พอถึง 0 ก็พิมพ์ liftoff แล้วจบ
2. กรณีเรียกซ้ำ (recursive case) เรียกตัวเองด้วยปัญหาที่เล็กลง จาก n เหลือ n - 1

3
2
1
liftoff

ไล่ดูทีละจังหวะ

1. main เรียก countdown(3) n ไม่ใช่ 0 จึงพิมพ์ 3 แล้วเรียก countdown(2)
2. countdown(2) พิมพ์ 2 แล้วเรียก countdown(1)
3. countdown(1) พิมพ์ 1 แล้วเรียก countdown(0)
4. countdown(0) เข้ากรณีฐาน พิมพ์ liftoff แล้ว return ไม่เรียกตัวเองอีก

recursion ที่ถูกต้องทุกตัวต้องมีครบสองข้อนี้

• มีกรณีฐาน ที่ตอบได้เลยโดยไม่เรียกตัวเอง
• ทุกครั้งที่เรียกตัวเอง ปัญหาต้องเล็กลงจนถึงกรณีฐานได้จริง ในตัวอย่างนี้ n ลดทีละ 1 จาก 3 จึงต้องถึง 0 แน่นอน

ขาดข้อไหนไป ฟังก์ชันจะเรียกตัวเองไม่รู้จบ ซึ่งดูได้ในส่วนลองทำให้พังท้ายหน้า

พิมพ์ก่อนหรือหลังเรียกตัวเอง

ลองย้าย printf ไปไว้ทั้งก่อนและหลังบรรทัดที่เรียกตัวเอง ฟังก์ชัน dive นี้ดำลงไปทีละชั้นแล้วลอยกลับขึ้นมา

#include <stdio.h>

void dive(int n)
{
    if (n == 0) {
        printf("bottom\n");
        return;
    }
    printf("down %d\n", n);
    dive(n - 1);
    printf("up %d\n", n);
}

int main()
{
    dive(3);
    return 0;
}

down 3
down 2
down 1
bottom
up 1
up 2
up 3

บรรทัด up ออกมากลับลำดับกับ down เพราะบรรทัดที่ 11 ของ dive(3) จะทำได้ก็ต่อเมื่อ dive(2) ในบรรทัดที่ 10 ทำงาน จบทั้งหมด แล้ว และ dive(2) จะจบได้ก็ต่อเมื่อ dive(1) จบก่อน ชั้นที่ลงไปทีหลังจึงจบก่อน

• งานที่อยู่ ก่อน การเรียกตัวเอง ทำตอนขาลง ลำดับจากใหญ่ไปเล็ก
• งานที่อยู่ หลัง การเรียกตัวเอง ทำตอนขากลับ ลำดับจากเล็กไปใหญ่

ถ้าลบบรรทัดที่ 9 ทิ้ง เหลือแต่ up จะได้ฟังก์ชันนับขึ้นจาก 1 ถึง n ที่ไม่ต้องมีตัวแปรนับเลย เรื่องขาลงขากลับนี้จะใช้อีกหลายครั้ง เช่น พิมพ์เลขฐานสองในแบบฝึกหัด

call stack เก็บทุกชั้นที่ยังไม่จบ

ตอน dive(1) ทำงาน dive(3) กับ dive(2) ยังไม่จบ แต่ละตัวหยุดรออยู่ที่บรรทัดที่ 10 และแต่ละตัวมี n ของตัวเอง 3 กับ 2 ไม่ได้ใช้ n ร่วมกัน เพราะพารามิเตอร์คือตัวแปร local ของการเรียกแต่ละครั้งตามที่เรียนในบทที่ 8

คอมพิวเตอร์จำของพวกนี้ไว้ในหน่วยความจำส่วนที่ชื่อ stack ส่วนเดียวกับที่เก็บอาเรย์ใน main ในบทที่ 5 การเรียกฟังก์ชันหนึ่งครั้งได้ที่หนึ่งชั้น เก็บพารามิเตอร์ ตัวแปร local และจุดที่ต้องกลับไปทำต่อ เรียกฟังก์ชันใหม่ก็วางชั้นใหม่ซ้อนไว้ด้านบน ฟังก์ชันจบก็ยกชั้นบนสุดออก เหมือนจานที่ซ้อนกัน วางเพิ่มด้านบนและหยิบออกจากด้านบนเท่านั้น ชั้นทั้งหมดนี้เรียกรวมว่า call stack

ดูให้ชัดกับฟังก์ชันที่คืนค่า แฟกทอเรียล ของ n เขียนว่า n! คือผลคูณ 1 × 2 × ... × n เช่น 4! = 24 ใช้นับจำนวนวิธีเรียงของ n ชิ้น เช่น เรียงหนังสือ 4 เล่มบนชั้นได้ 24 แบบ สังเกตว่า 4! = 4 × 3! และ 3! = 3 × 2! ไปเรื่อยๆ จนถึง 0! ซึ่งนิยามให้เป็น 1

#include <stdio.h>

long long factorial(int n)
{
    if (n == 0) {
        return 1;
    }
    return n * factorial(n - 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%lld\n", factorial(n));
    return 0;
}

4

24

บรรทัดที่ 8 คูณ n กับคำตอบของปัญหาที่เล็กลงหนึ่งขั้น แต่การคูณยังทำไม่ได้จนกว่า factorial(n - 1) จะคืนค่ากลับมา ภาพนี้คือ call stack ตอนที่ลงไปลึกที่สุด ชั้นบนสุดคือการเรียกที่กำลังทำงานอยู่ ลูกศรด้านขวาคือค่าที่แต่ละชั้นคืนให้ชั้นข้างล่าง

ขาลง stack สูงขึ้นทีละชั้นจาก factorial(4) ถึง factorial(0) รวมห้าชั้นบนหัวของ main ขากลับ factorial(0) คืน 1 แล้วชั้นนั้นถูกยกออก factorial(1) ได้ 1 มาก็คูณกับ n ของตัวเองแล้วคืนต่อ ไล่ลงมาจนถึง factorial(4) ที่ได้ 6 มาคูณ 4 เป็น 24

พิมพ์ให้เห็นทุกชั้น

เวลา recursion ให้คำตอบผิด วิธีที่ได้ผลที่สุดคือให้มันพิมพ์ทุกครั้งที่เข้าและออก โดยเยื้องตามความลึก จะเห็นภาพเดียวกับข้างบนในหน้าต่างดำ เพิ่มพารามิเตอร์ depth ไว้นับว่าลึกเท่าไร แล้วพิมพ์ช่องว่าง 4 ช่องต่อหนึ่งชั้น

#include <stdio.h>

void indent(int depth)
{
    for (int i = 0; i < depth; i++) {
        printf("    ");
    }
}

long long factorial(int n, int depth)
{
    indent(depth);
    printf("factorial(%d) starts\n", n);
    long long result;
    if (n == 0) {
        result = 1;
    } else {
        result = n * factorial(n - 1, depth + 1);
    }
    indent(depth);
    printf("factorial(%d) returns %lld\n", n, result);
    return result;
}

int main()
{
    factorial(3, 0);
    return 0;
}

factorial(3) starts
    factorial(2) starts
        factorial(1) starts
            factorial(0) starts
            factorial(0) returns 1
        factorial(1) returns 1
    factorial(2) returns 2
factorial(3) returns 6

บรรทัด starts กับ returns ของการเรียกเดียวกันเยื้องเท่ากัน อ่านคู่กันได้ทันที ฟังก์ชันนี้เขียน if else แยกแล้วเก็บผลไว้ใน result ก่อน เพื่อให้พิมพ์ตอนขาออกได้ทั้งสองกรณี หาบั๊กเสร็จแล้วก็ลบบรรทัดที่พิมพ์ออก

ลองทำให้พัง

แบบที่ 1 ไม่มีกรณีฐาน

ลบ if ที่เป็นกรณีฐานออกจากโปรแกรมนับถอยหลัง

#include <stdio.h>

void countdown(int n)
{
    printf("%d\n", n);
    countdown(n - 1);
}

int main()
{
    countdown(3);
    return 0;
}

countdown.c:3:6: warning: infinite recursion detected [-Winfinite-recursion]
    3 | void countdown(int n)
      |      ^~~~~~~~~
countdown.c:6:5: note: recursive call
    6 |     countdown(n - 1);
      |     ^~~~~~~~~~~~~~~~

infinite recursion แปลว่าเรียกตัวเองไม่รู้จบ GCC 14 ที่มากับ Code::Blocks ตรวจเจอกรณีง่ายๆ แบบนี้ให้ แต่เป็นแค่ warning ถ้ารันต่อ โปรแกรมจะพิมพ์ 3 2 1 0 -1 -2 ลงไปเรื่อยๆ บนเครื่องที่เขียนเอกสารนี้ ให้ผลลัพธ์ลงไฟล์แล้วนับดู พิมพ์ลงไปถึงราว -43000 แล้วปิดตัวเอง Code::Blocks ขึ้นว่า

Process returned -1073741571 (0xC00000FD)

0xC00000FD คือ stack overflow รหัสเดียวกับตอนประกาศอาเรย์ใหญ่ใน main ในบทที่ 5 ทุกครั้งที่เรียกตัวเองได้ชั้นใหม่บน stack และชั้นเก่ายังไม่มีใครจบ stack จึงสูงขึ้นเรื่อยๆ จนเต็มที่ราว 2 MB โปรแกรมก็พัง ถ้าส่งให้ grader จะได้ผล runtime error

แบบที่ 2 กรณีฐานที่ไปไม่ถึง

ใช้โปรแกรม factorial เดิมทุกตัวอักษร แต่ป้อน -1 คอมไพล์ผ่านโดยไม่มีคำเตือน เพราะ compiler ไม่รู้ว่าจะมีคนป้อนเลขติดลบ แต่พอรัน โปรแกรมพังด้วย 0xC00000FD เหมือนแบบที่ 1

กรณีฐานมีอยู่ก็จริง แต่ n เริ่มที่ -1 แล้วลดลงเรื่อยๆ เป็น -2 -3 ไม่มีวันเท่ากับ 0 นี่คือการผิดกฎข้อที่สอง คือปัญหาต้องเล็กลง จนถึงกรณีฐานได้จริง ถ้าโจทย์รับประกันว่า n ไม่ติดลบก็ไม่เป็นไร แต่ถ้าไม่แน่ใจ เขียนกรณีฐานเป็น if (n <= 0) จะไม่พังไม่ว่าป้อนอะไร

แบบที่ 3 ลืม return หน้าการเรียกตัวเอง

เขียนบรรทัดที่ 8 ของโปรแกรม factorial เป็น n * factorial(n - 1); โดยไม่มี return

factorial.c:8:7: warning: value computed is not used [-Wunused-value]
    8 |     n * factorial(n - 1);
      |     ~~^~~~~~~~~~~~~~~~~~
factorial.c:9:1: warning: control reaches end of non-void function [-Wreturn-type]
    9 | }
      | ^

คำเตือนแรกบอกว่าคำนวณแล้วไม่ได้เอาค่าไปใช้ คำเตือนที่สองบอกว่าฟังก์ชันที่ต้องคืนค่า เดินมาถึงปีกกาปิดโดยไม่เจอ return ค่าที่คืนจึงเป็นอะไรก็ได้ บนเครื่องที่เขียนเอกสารนี้ ป้อน 4 5 หรือ 10 ก็ได้ 1 ทุกครั้ง ทุกเส้นทางของฟังก์ชันที่ไม่ใช่ void ต้องจบด้วย return เสมอ รวมถึงกรณีเรียกซ้ำด้วย

ลึกได้กี่ชั้น

stack มีที่จำกัด recursion จึงลึกได้จำกัด แม้จะมีกรณีฐานถูกต้อง ลองกับฟังก์ชันหาผลรวม 1 + 2 + ... + n ที่เรียกตัวเองลึก n ชั้น

#include <stdio.h>

int sum_to(int n)
{
    if (n == 0) {
        return 0;
    }
    return n + sum_to(n - 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    printf("%d\n", sum_to(n));
    return 0;
}

10000

50005000

บนเครื่องที่เขียนเอกสารนี้ คอมไพล์แบบ Code::Blocks (-Wall ไม่มี -O2) แล้วป้อนค่าต่างๆ ค่าละ 10 ครั้ง ได้ผลดังนี้

• ป้อน 43000 ได้ 924521500 ครบทั้ง 10 ครั้ง
• ป้อน 44000 พังด้วย 0xC00000FD ทั้ง 10 ครั้ง
• ค่าที่อยู่ระหว่างนั้น เช่น 43300 บางครั้งผ่านบางครั้งพัง ขอบไม่ตายตัว เพราะ stack ไม่ได้เริ่มที่ตำแหน่งเดิมเป๊ะทุกครั้ง

stack ราว 2 MB หารด้วยราวสี่หมื่นสามพันชั้น ได้ชั้นละประมาณ 48 byte ฟังก์ชันที่มีพารามิเตอร์หรือตัวแปร local มากกว่านี้ จะลึกได้น้อยกว่านี้

เรื่องแปลกคือ พอคอมไพล์โปรแกรมเดียวกันด้วย -O2 ป้อนถึงหนึ่งร้อยล้านก็ยังไม่พัง (คำตอบผิดเพราะผลรวมเกิน int แต่ไม่พัง) เพราะ compiler เห็นว่าฟังก์ชันนี้เขียนเป็นลูปได้ จึงแปลงเป็นลูปให้เอง ห้ามพึ่งเรื่องนี้ compiler ไม่ได้แปลงให้ทุกฟังก์ชัน และ grader แต่ละที่ตั้งขนาด stack ไม่เท่ากัน หลักที่ปลอดภัยคือ

• ลึกไม่เกินหลักพันชั้น ใช้ recursion ได้สบาย
• ลึกหลักหมื่นชั้นขึ้นไปให้เขียนเป็นลูป ตัวเลขข้างบนพังตั้งแต่สี่หมื่นกว่าชั้น และฟังก์ชันที่มีพารามิเตอร์มากกว่านี้พังเร็วกว่านั้นอีก เช่น เรียกตัวเองหนึ่งครั้งต่อสมาชิกหนึ่งตัวของอาเรย์ขนาดแสน หน้า 9.4 จะดูว่าเมื่อไรควรเลือกแบบไหน

สรุป

• recursion คือฟังก์ชันที่เรียกตัวเองเพื่อแก้ปัญหาเดิมที่เล็กลง
• ต้องมีกรณีฐานที่ตอบได้ทันที และทุกการเรียกซ้ำต้องเข้าใกล้กรณีฐานจนถึงได้จริง
• งานก่อนการเรียกตัวเองทำตอนขาลง งานหลังการเรียกทำตอนขากลับในลำดับย้อนกลับ
• การเรียกแต่ละครั้งมีตัวแปร local ของตัวเอง เก็บเป็นหนึ่งชั้นบน call stack
• เรียกตัวเองไม่รู้จบ หรือลึกเกินไป ได้ stack overflow 0xC00000FD บนเครื่องที่เขียนเอกสารนี้ลึกได้ราวสี่หมื่นชั้น
• หาบั๊กด้วยการพิมพ์ตอนเข้าและออก เยื้องตามความลึก