9.3 ฟีโบนัชชีและการจำคำตอบ

recursion ที่เขียนถูกทุกบรรทัดก็ยังช้าจนใช้ไม่ได้ ถ้ามันแก้ปัญหาย่อยเดิมซ้ำเป็นล้านๆ รอบ หน้านี้จะวัดให้เห็นจริงว่าช้าแค่ไหนด้วยลำดับฟีโบนัชชี แล้วแก้ด้วยวิธีที่ง่ายมาก คือจดคำตอบที่เคยคำนวณแล้วไว้ในอาเรย์ วิธีนี้คือจุดเริ่มต้นของ dynamic programming ซึ่งเป็นหัวข้อใหญ่ที่สุดหัวข้อหนึ่งของค่าย 2

ลำดับฟีโบนัชชี

ลำดับฟีโบนัชชีเริ่มด้วย 0 กับ 1 แล้วตัวถัดไปคือผลบวกของสองตัวก่อนหน้า

fib(0) = 0
fib(1) = 1
fib(n) = fib(n - 1) + fib(n - 2)    เมื่อ n ≥ 2

0 1 1 2 3 5 8 13 21 34 55 ...

ลำดับนี้โผล่ในโจทย์นับวิธีบ่อยมาก เช่น ขึ้นบันได n ขั้น ก้าวทีละ 1 หรือ 2 ขั้น มีกี่วิธี ก้าวสุดท้ายต้องมาจากขั้น n - 1 หรือขั้น n - 2 จำนวนวิธีจึงเป็นผลบวกของจำนวนวิธีไปถึงสองขั้นนั้น โครงเดียวกับฟีโบนัชชีพอดี

นิยามเป็น recursion อยู่แล้ว แปลงเป็นโค้ดได้ตรงตัว มีกรณีฐานสองกรณีคือ 0 กับ 1 รวมเป็น n <= 1 แล้วคืน n

#include <stdio.h>

long long fib(int n)
{
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

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

10

55

หนึ่งครั้งแตกเป็นสองครั้ง

ต่างจากแฟกทอเรียลที่เรียกตัวเองครั้งเดียว fib เรียกตัวเองสองครั้ง แต่ละครั้งก็แตกเป็นสองครั้งอีก ภาพนี้คือทุกการเรียกที่เกิดขึ้นตอนคำนวณ fib(5) เส้นเชื่อมบอกว่าใครเรียกใคร

นับกล่องได้ 15 กล่อง คือเรียก 15 ครั้งเพื่อคำนวณ fib(5) ทั้งที่คำตอบมีแค่ 6 ค่าที่ต่างกันคือ fib(0) ถึง fib(5) ที่เหลือคือ คำนวณเรื่องเดิมซ้ำ fib(3) ทำสองรอบเต็มๆ fib(2) ทำสามรอบ ยิ่ง n ใหญ่ ต้นไม้ยิ่งแตกกิ่ง และงานซ้ำยิ่งพอกพูน

นับจำนวนครั้งที่เรียก

เพิ่มตัวแปร global calls แล้วบวกหนึ่งทุกครั้งที่เข้าฟังก์ชัน ใช้ long long เพราะจะเห็นว่ามันเกิน int ได้ง่ายมาก

#include <stdio.h>

long long calls = 0;

long long fib(int n)
{
    calls++;
    if (n <= 1) {
        return n;
    }
    return fib(n - 1) + fib(n - 2);
}

int main()
{
    int n;
    scanf("%d", &n);
    long long answer = fib(n);
    printf("fib(%d) = %lld\n", n, answer);
    printf("calls = %lld\n", calls);
    return 0;
}

30

fib(30) = 832040
calls = 2692537

เกือบสามล้านครั้งเพื่อตัวเลขตัวเดียว ทีนี้จับเวลาด้วย clock() แบบในหน้า 4.5 โดยเพิ่ม #include <time.h> ไว้บนสุด แล้วครอบการเรียก fib(n) ใน main แบบนี้

clock_t start = clock();
long long answer = fib(n);
clock_t end = clock();

แล้วพิมพ์ (double)(end - start) / CLOCKS_PER_SEC เพิ่มอีกบรรทัด วัดบนโน้ตบุ๊ก ASUS Vivobook S 14 ซีพียู AMD Ryzen AI 9 HX 370 Windows 11 กับ GCC 14.2 ของ Code::Blocks ทั้งแบบ Code::Blocks (-Wall อย่างเดียว) และแบบ -O2 ช่อง n = 30 ถึง 45 คือค่ากลางของการรัน 5 ครั้ง ช่อง n = 50 รันแบบละครั้งเดียวเพราะรอนานเกินไป

fib(40) เรียกตัวเองสามร้อยกว่าล้านครั้ง ใช้เวลาเกือบครึ่งวินาทีแบบ Code::Blocks n เพิ่มทีละ 5 จำนวนครั้งเพิ่มราว 11 เท่าทุกแถว พอถึง fib(50) ต้องรอเป็นนาที ทั้งที่ถ้าเขียนลูปบวกต่อกันทีละตัวจาก fib(0) ขึ้นไป ใช้แค่ราว 50 รอบ โจทย์ที่ให้ n ถึง 50 จึงไม่มีทางผ่านด้วยวิธีนี้ แม้คำตอบจะถูกทุกตัว

จดคำตอบไว้ในอาเรย์

ปัญหาไม่ได้อยู่ที่ recursion แต่อยู่ที่การคำนวณ fib(3) เรื่องเดิมใหม่ทุกครั้งที่มีคนถาม แก้ด้วยการจด พอคำนวณ fib(k) ได้ครั้งแรกก็จดไว้ในช่อง memo[k] ของอาเรย์ ครั้งต่อไปที่มีคนถาม fib(k) ก็เปิดสมุดตอบเลย ไม่ต้องคำนวณใหม่ วิธีนี้เรียกว่า memoization (การจำคำตอบ) มาจากคำว่า memo ที่แปลว่าบันทึกช่วยจำ

#include <stdio.h>

long long memo[91]; // (1)!
long long calls = 0;

long long fib(int n)
{
    calls++;
    if (n <= 1) {
        return n;
    }
    if (memo[n] != -1) { // (2)!
        return memo[n];
    }
    memo[n] = fib(n - 1) + fib(n - 2); // (3)!
    return memo[n];
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i <= 90; i++) {
        memo[i] = -1; // (4)!
    }
    long long answer = fib(n);
    printf("fib(%d) = %lld\n", n, answer);
    printf("calls = %lld\n", calls);
    return 0;
}

1. อาเรย์ global หนึ่งช่องต่อหนึ่งค่า n ตั้งแต่ 0 ถึง 90 ต้องเป็น global เพราะทุกชั้นของ recursion ต้องเห็นสมุดเล่มเดียวกัน
2. เคยคำนวณแล้ว ตอบจากสมุดทันที ไม่เรียกตัวเองต่อ
3. ยังไม่เคย ก็คำนวณตามสูตรเดิม แต่จดลงสมุดก่อนคืนค่า
4. เติม -1 ทุกช่อง แปลว่า "ยังไม่ได้คำนวณ" ใช้ -1 เพราะฟีโบนัชชีไม่มีค่าติดลบ จึงไม่มีวันสับสนกับคำตอบจริง

90

fib(90) = 2880067194370816120
calls = 179

179 ครั้งสำหรับ fib(90) ป้อน 40 ได้ calls = 79 จากเดิมสามร้อยกว่าล้านครั้ง จับเวลาแบบเดียวกับข้างบนได้ 0.000 วินาทีทั้ง n = 40 และ n = 90 คือเร็วเกินกว่าที่ clock() วัดได้

ทำไมเหลือน้อยขนาดนี้ แต่ละ k ตั้งแต่ 2 ถึง n คำนวณจริงแค่ครั้งแรกครั้งเดียว ครั้งนั้นเรียกตัวเองสองครั้ง ที่เหลือทุกครั้งตอบจากสมุดทันที ไม่แตกกิ่งต่อ จำนวนครั้งที่เรียกทั้งหมดจึงโตตาม n ตรงๆ ราว 2n ไม่ได้คูณ 11 เท่าทุกห้าขั้นอีกแล้ว ในภาพต้นไม้ข้างบน กล่อง fib(3) ทางขวาจะไม่แตกกิ่งลงไปเลย เพราะทางซ้ายจดคำตอบไว้ให้แล้ว

ขนาดของอาเรย์จดต้องพอสำหรับทุกค่าที่ถูกถาม ถ้าโจทย์บอกว่า n ไม่เกิน 90 ก็ประกาศ 91 ช่องสำหรับ 0 ถึง 90 และค่าที่จดต้องเก็บใน long long เพราะ fib(47) ก็เกิน int แล้ว

ลองทำให้พัง

แบบที่ 1 เช็กสมุดแต่ลืมจด

เขียนบรรทัดที่ 15 กับ 16 รวมกันเป็น return fib(n - 1) + fib(n - 2); ดูสั้นกว่า และยังมีบรรทัดเช็ก memo[n] อยู่ครบ

40

fib(40) = 102334155
calls = 331160281

คำตอบถูก แต่จำนวนครั้งเท่ากับแบบไม่มีสมุดทุกครั้ง เพราะไม่มีใครเขียนลงสมุดเลย ทุกช่องจึงเป็น -1 ตลอด เช็กทุกครั้งก็ไม่เคยเจอ compiler ไม่เตือนอะไร เพราะโค้ดถูกไวยากรณ์ทุกอย่าง วิธีจับคือนับจำนวนครั้งแบบในหน้านี้ หรือลองป้อน n ใหญ่ๆ ดูว่าเร็วจริงไหม

แบบที่ 2 ใหญ่เกิน long long

ขยายอาเรย์จดเป็น 100 ช่องแล้วถามไปเรื่อยๆ บนเครื่องที่เขียนเอกสารนี้ fib(92) ได้ 7540113804746346429 ถูกต้อง แต่ fib(93) ได้

fib(93) = -6246583658587674878

ฟีโบนัชชีติดลบไม่ได้ นี่คือ overflow แบบในหน้า 1.3 เพราะ fib(93) ใหญ่กว่า 9 × 10¹⁸ ที่ long long เก็บได้ จดได้เร็วแค่ไหนก็ช่วยเรื่องนี้ไม่ได้ โจทย์นับวิธีที่ให้ n ใหญ่ขนาดนี้จึงมักให้ตอบเป็นเศษจากการหาร ซึ่งอยู่ในบทที่ 12

สรุป

• recursion ที่เรียกตัวเองสองครั้งต่อชั้น จำนวนครั้งโตแบบทวีคูณ fib(40) แบบตรงๆ เรียก 331160281 ครั้ง
• สาเหตุคือคำนวณปัญหาย่อยเดิมซ้ำ ไม่ใช่ตัว recursion เอง
• memoization คือจดคำตอบลงอาเรย์ global ก่อนคืนค่า แล้วเช็กสมุดก่อนคำนวณทุกครั้ง
• เติมค่าเริ่มต้นที่ไม่มีทางเป็นคำตอบจริง เช่น -1 ไว้แทนคำว่ายังไม่ได้คำนวณ
• จดแล้ว fib(90) เรียกแค่ 179 ครั้ง วิธีคิดนี้คือจุดเริ่มของ dynamic programming ในบทที่ 24