9.2 แบ่งเป็นปัญหาที่เล็กลง

หน้าที่แล้วดูว่า recursion ทำงานยังไง หน้านี้ฝึกเขียนเอง ความยากของ recursion ไม่ได้อยู่ที่ไวยากรณ์ เพราะมันก็คือฟังก์ชันธรรมดาจากบทที่ 8 แต่อยู่ที่การมองปัญหาให้เห็นว่ามี ปัญหาเดิมที่เล็กกว่า ซ่อนอยู่ข้างใน หน้านี้ใช้โจทย์คณิตศาสตร์สามเรื่องที่เจอบ่อยในการแข่งขัน คือผลรวมหลัก ยกกำลัง และ ห.ร.ม. แบบยุคลิด ซึ่งวิธีแบ่งครึ่งในเรื่องยกกำลังจะได้ใช้อีกในบทที่ 12 และบทที่ 22

สามคำถามก่อนเขียน

ก่อนเขียน recursion ทุกครั้ง ให้ตอบสามคำถามนี้ให้ได้ก่อน

1. ปัญหาที่เล็กลงหน้าตาเป็นยังไง ต้องเป็นปัญหาแบบเดียวกัน แค่ข้อมูลเล็กลง
2. ถ้ามีคนบอกคำตอบของปัญหาที่เล็กลงให้ จะเอาไปทำเป็นคำตอบของปัญหานี้ยังไง
3. ปัญหาที่เล็กที่สุดคืออะไร และคำตอบของมันคืออะไร ข้อนี้คือกรณีฐาน

ลองกับแฟกทอเรียลในหน้าที่แล้ว

คำถามข้อสองคือหัวใจ ตอนเขียนบรรทัด return n * factorial(n - 1); ให้ เชื่อไปก่อน ว่า factorial(n - 1) คืนคำตอบที่ถูกมาให้ ไม่ต้องไล่ในหัวลงไปทุกชั้น ถ้ากรณีฐานถูก และคำตอบใหญ่ประกอบจากคำตอบเล็กได้ถูก ทุกชั้นก็ถูกตามกันไปเอง เหมือนโดมิโนที่ตัวแรกล้ม และแต่ละตัวล้มทับตัวถัดไปได้ ทั้งแถวก็ล้มหมด

ผลรวมของหลัก

หาผลรวมของเลขโดดทุกหลัก เช่น 2569 ได้ 2 + 5 + 6 + 9 = 22 ในบทที่ 4 ทำด้วยลูปไปแล้ว คราวนี้ตอบสามคำถาม

• ปัญหาที่เล็กลง ตัดหลักหน่วยทิ้งด้วย n / 10 2569 เหลือ 256 ยังเป็นการหาผลรวมหลักเหมือนเดิม
• ประกอบคำตอบ ผลรวมหลักของ 2569 คือหลักหน่วย 9 บวกผลรวมหลักของ 256 เขียนเป็น n % 10 + digit_sum(n / 10)
• เล็กที่สุด n = 0 ไม่มีหลักเหลือแล้ว ผลรวมคือ 0

#include <stdio.h>

int digit_sum(int n)
{
    if (n == 0) {
        return 0;
    }
    return n % 10 + digit_sum(n / 10);
}

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

2569

22

digit_sum(2569) = 9 + digit_sum(256)   = 9 + 13 = 22
digit_sum(256)  = 6 + digit_sum(25)    = 6 + 7  = 13
digit_sum(25)   = 5 + digit_sum(2)     = 5 + 2  = 7
digit_sum(2)    = 2 + digit_sum(0)     = 2 + 0  = 2
digit_sum(0)    = 0

อ่านตารางจากบนลงล่างคือขาลง อ่านคอลัมน์ขวาจากล่างขึ้นบนคือขากลับ ฟังก์ชันนี้ลึกแค่จำนวนหลักบวกหนึ่ง เลข int มีไม่เกิน 10 หลัก จึงไม่มีทางลึกจน stack เต็ม

ยกกำลัง

หา base^exponent เช่น 3⁴ = 81 วิธีแรกคิดเหมือนแฟกทอเรียล 3⁴ = 3 × 3³ ปัญหาเล็กลงคือเลขชี้กำลังลดลงหนึ่ง ประกอบคำตอบด้วยการคูณ base อีกตัว และเลขชี้กำลัง 0 ได้ 1

วิธีที่สองมองต่างไป 3⁸ คือ 3⁴ × 3⁴ ถ้ารู้ 3⁴ แล้ว ยกกำลังสองทีเดียวก็ได้ 3⁸ ปัญหาที่เล็กลงคือเลขชี้กำลัง ครึ่งหนึ่ง ไม่ใช่ลดลงหนึ่ง ถ้าเลขชี้กำลังเป็นคี่ เช่น 3⁹ หารสองได้ 4 เศษ 1 จึงเป็น 3⁴ × 3⁴ × 3 ต้องคูณ base เพิ่มอีกหนึ่งตัว

โปรแกรมนี้เขียนทั้งสองแบบ และใช้ตัวแปร global นับว่าแต่ละแบบเรียกตัวเองกี่ครั้ง

#include <stdio.h>

int slow_calls = 0;
int fast_calls = 0;

long long slow_power(long long base, int exponent)
{
    slow_calls++;
    if (exponent == 0) {
        return 1;
    }
    return base * slow_power(base, exponent - 1);
}

long long fast_power(long long base, int exponent)
{
    fast_calls++;
    if (exponent == 0) {
        return 1;
    }
    long long half = fast_power(base, exponent / 2); // (1)!
    if (exponent % 2 == 0) {
        return half * half;
    }
    return half * half * base;
}

int main()
{
    long long base;
    int exponent;
    scanf("%lld %d", &base, &exponent);
    long long slow = slow_power(base, exponent); // (2)!
    long long fast = fast_power(base, exponent);
    printf("slow: %lld (%d calls)\n", slow, slow_calls);
    printf("fast: %lld (%d calls)\n", fast, fast_calls);
    return 0;
}

1. เรียกตัวเองครั้งเดียว เก็บผลไว้ใน half แล้วใช้ซ้ำสองครั้ง ห้ามเรียกสองครั้ง ดูเหตุผลในส่วนลองทำให้พัง
2. เก็บผลใส่ตัวแปรก่อนพิมพ์ เพราะภาษา C ไม่ได้กำหนดว่า printf จะคำนวณค่าที่ส่งเข้าไปตัวไหนก่อน ถ้าเขียน slow_power(...) กับ slow_calls ไว้ใน printf เดียวกัน อาจได้จำนวนครั้งก่อนที่ฟังก์ชันจะทำงานเสียอีก

3 39

slow: 4052555153018976267 (40 calls)
fast: 4052555153018976267 (7 calls)

ได้คำตอบเดียวกัน แต่แบบแรกเรียก 40 ครั้ง คือหนึ่งครั้งต่อการลดเลขชี้กำลังลงหนึ่ง ส่วนแบบแบ่งครึ่งเรียกแค่ 7 ครั้ง เลขชี้กำลังเดินเป็น 39 19 9 4 2 1 0 ถ้าเลขชี้กำลังเป็นล้าน แบบแรกต้องเรียกล้านครั้งและลึกล้านชั้น เกินที่ stack รับได้ในหน้า 9.1 ไปมาก ส่วนแบบแบ่งครึ่งนับได้แค่ 21 ครั้ง เพราะหารสองราวยี่สิบครั้งก็ลดหนึ่งล้านจนเหลือ 0 แล้ว

การแบ่งปัญหาเป็นครึ่งแล้วประกอบคำตอบกลับแบบนี้คือ divide and conquer ซึ่งมีบทของมันเองคือบทที่ 22 ส่วนยกกำลังของเลขใหญ่จริงๆ ที่ต้องตอบเป็นเศษจากการหาร อยู่ในบทที่ 12

ห.ร.ม. แบบยุคลิด

มีกระดาษขนาด 84 × 60 เซนติเมตร อยากตัดเป็นสี่เหลี่ยมจัตุรัสขนาดเท่ากันทั้งหมดโดยไม่เหลือเศษ และให้ชิ้นใหญ่ที่สุด ด้านของสี่เหลี่ยมต้องหารทั้ง 84 และ 60 ลงตัว และต้องมากที่สุด นั่นคือ ห.ร.ม. (ตัวหารร่วมมาก, greatest common divisor หรือ gcd) ของ 84 กับ 60

หน้า 8.5 หา ห.ร.ม. ด้วยวิธีของยุคลิดเป็นลูปไปแล้ว พร้อมเหตุผลว่าทำไม ห.ร.ม. ของ a กับ b เท่ากับ ห.ร.ม. ของ b กับ a % b ประโยคนี้คือ recursion อยู่ในตัว เพราะบอกคำตอบของปัญหาหนึ่งด้วยปัญหาแบบเดียวกันที่เล็กกว่า เขียนเป็นฟังก์ชันที่เรียกตัวเองได้ตรงตามประโยคเลย ไม่ต้องพักค่าด้วยตัวแปร remainder แล้วสลับ a กับ b เองแบบลูป

ตอบสามคำถาม ปัญหาที่เล็กลงคือ ห.ร.ม. ของ b กับ a % b ซึ่ง a % b น้อยกว่า b เสมอ คำตอบของปัญหาเล็กคือคำตอบของปัญหานี้เลยไม่ต้องทำอะไรเพิ่ม และเล็กที่สุดคือเมื่อ b เป็น 0 ห.ร.ม. ของ a กับ 0 คือ a เพราะ 0 หารด้วยอะไรก็ลงตัว โปรแกรมนี้พิมพ์ทุกครั้งที่เรียก ให้เห็นว่าตัวเลขเล็กลงเร็วแค่ไหน

#include <stdio.h>

int gcd(int a, int b)
{
    printf("gcd(%d, %d)\n", a, b);
    if (b == 0) {
        return a;
    }
    return gcd(b, a % b);
}

int main()
{
    int a, b;
    scanf("%d %d", &a, &b);
    int answer = gcd(a, b);
    printf("answer = %d\n", answer);
    return 0;
}

84 60

gcd(84, 60)
gcd(60, 24)
gcd(24, 12)
gcd(12, 0)
answer = 12

ตัดได้สี่เหลี่ยมด้าน 12 เซนติเมตร 7 × 5 = 35 ชิ้น สังเกตสองเรื่อง

• ไม่ต้องสนว่าตัวไหนมากกว่า ป้อน 60 84 บรรทัดแรกเป็น gcd(60, 84) แล้วบรรทัดที่สองเป็น gcd(84, 60) เพราะ 60 % 84 = 60 สองตัวสลับที่กันเอง แล้วเดินต่อเหมือนเดิม
• เร็วมาก ตัวเลขเล็กลงอย่างน้อยครึ่งหนึ่งทุกสองครั้ง บนเครื่องที่เขียนเอกสารนี้นับจำนวนครั้งที่เรียกด้วยตัวแปร global แบบโปรแกรมยกกำลัง gcd(1836311903, 1134903170) ซึ่งเป็นคู่ที่ทำให้ยุคลิดช้าที่สุดคู่หนึ่งในช่วงของ int เรียกแค่ 45 ครั้ง

สูตร ค.ร.น. แบบหารก่อนคูณจากหน้า 8.5 ใช้กับฟังก์ชันนี้ได้เหมือนเดิม เรื่องจำนวนเต็มแบบนี้มีต่อในบทที่ 12

ลองทำให้พัง

แบบที่ 1 เรียกครึ่งซ้ำสองครั้ง

ใน fast_power ไม่ใช้ตัวแปร half แต่เรียกตัวเองตรงๆ สองครั้ง ดูเหมือนเป็นสูตรเดียวกัน

long long fast_power(long long base, int exponent)
{
    calls++;
    if (exponent == 0) {
        return 1;
    }
    if (exponent % 2 == 0) {
        return fast_power(base, exponent / 2) * fast_power(base, exponent / 2);
    }
    return fast_power(base, exponent / 2) * fast_power(base, exponent / 2) * base;
}

คำตอบยังถูก แต่ป้อน 3 39 แล้วนับได้ calls = 127 มากกว่าแบบช้าที่เรียก 40 ครั้งเสียอีก ป้อนเลขชี้กำลังหนึ่งล้านได้ calls = 2097151 เพราะทุกชั้นแตกเป็นสองทาง และแต่ละทางคำนวณสิ่งเดียวกันซ้ำ ความเร็วที่ได้จากการแบ่งครึ่งหายหมด คำนวณซ้ำแบบนี้คือต้นเหตุที่ฟีโบนัชชีในหน้าถัดไปช้ามาก

แบบที่ 2 กรณีฐานที่หารด้วยศูนย์

บางคนเขียนกรณีฐานของ ห.ร.ม. ว่า "ถ้า b หาร a ลงตัว คำตอบคือ b"

int gcd(int a, int b)
{
    if (a % b == 0) {
        return b;
    }
    return gcd(b, a % b);
}

ป้อน 84 60 ได้ 12 ถูกต้อง แต่ป้อน 7 0 ซึ่งคำตอบควรเป็น 7 โปรแกรมพังทันที

Process returned -1073741676 (0xC0000094)

รหัสเดียวกับหารด้วยศูนย์ในหน้า 1.2 เพราะบรรทัดที่ 3 คำนวณ 7 % 0 ก่อนจะได้เช็กอะไรเลย กรณีฐานต้องเช็กสิ่งที่ปลอดภัยก่อนจะคำนวณ แบบ if (b == 0) ในตัวอย่างข้างบนจึงดีกว่า ทั้งสั้นกว่าและไม่มีวันหารด้วยศูนย์

สรุป

• ก่อนเขียน ตอบให้ได้ว่าปัญหาที่เล็กลงคืออะไร ประกอบคำตอบยังไง และกรณีเล็กสุดคืออะไร
• ตอนเขียน เชื่อว่าการเรียกตัวเองกับปัญหาที่เล็กลงคืนคำตอบที่ถูกมา ไม่ต้องไล่ในหัวทุกชั้น
• ผลรวมหลัก n % 10 + digit_sum(n / 10) กรณีฐาน n = 0
• ยกกำลังแบบแบ่งครึ่งเรียกตัวเองราว log₂ ของเลขชี้กำลังครั้ง แต่ต้องเก็บผลครึ่งไว้ในตัวแปร ห้ามเรียกซ้ำสองครั้ง
• ห.ร.ม. แบบยุคลิด gcd(b, a % b) กรณีฐาน b = 0 เร็วมากแม้ตัวเลขถึงพันล้าน