9.4 recursion กับอาเรย์

อาเรย์ก็แบ่งเป็นปัญหาที่เล็กลงได้ อาเรย์ตั้งแต่ช่อง i ถึงท้าย คือช่อง i หนึ่งช่อง กับอาเรย์ที่สั้นลงหนึ่งช่องตั้งแต่ i + 1 หรือจะตัดครึ่งเหลือแค่ครึ่งซ้ายหรือครึ่งขวาก็ได้ หน้านี้ใช้วิธีคิดนี้หาผลรวม กลับลำดับ และค้นหาแบบแบ่งครึ่ง ซึ่งเป็นวิธีค้นหาที่เร็วที่สุดวิธีหนึ่งในข้อมูลที่เรียงแล้ว ท้ายหน้าดูว่าเมื่อไรควรเลิกใช้ recursion แล้วกลับไปใช้ลูป

ผลรวมของอาเรย์

ตอบสามคำถามกับผลรวมตั้งแต่ช่อง i ถึงช่องสุดท้าย

• ปัญหาที่เล็กลง ผลรวมตั้งแต่ช่อง i + 1 ถึงช่องสุดท้าย
• ประกอบคำตอบ บวก a[i] เข้าไป
• เล็กที่สุด i เท่ากับ n คือไม่เหลือช่องแล้ว ผลรวมเป็น 0

#include <stdio.h>

int scores[100];

int sum_from(int a[], int i, int n)
{
    if (i == n) {
        return 0;
    }
    return a[i] + sum_from(a, i + 1, n);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &scores[i]);
    }
    printf("%d\n", sum_from(scores, 0, n));
    return 0;
}

5
72 85 64 90 78

389

ส่งอาเรย์เข้าฟังก์ชันแบบในบทที่ 8 พร้อมพารามิเตอร์ i ที่บอกว่าตอนนี้อยู่ช่องไหน และ n ที่บอกว่าจบที่ไหน ทุกชั้นใช้อาเรย์เดียวกัน ต่างกันแค่ i เทคนิคเพิ่มพารามิเตอร์บอกตำแหน่งแบบนี้ใช้กับ recursion บนอาเรย์และสตริงแทบทุกตัว

กลับลำดับในอาเรย์

ในบทที่ 5 กลับลำดับด้วยลูปที่สลับช่องหัวกับท้ายแล้วขยับเข้าหากัน คิดแบบ recursion ได้ว่า กลับลำดับช่วง left ถึง right คือสลับสองปลาย แล้วกลับลำดับช่วงข้างในที่สั้นลงสองช่อง

#include <stdio.h>

int numbers[100];

void reverse(int a[], int left, int right)
{
    if (left >= right) {
        return;
    }
    int temp = a[left];
    a[left] = a[right];
    a[right] = temp;
    reverse(a, left + 1, right - 1);
}

int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
    reverse(numbers, 0, n - 1);
    for (int i = 0; i < n; i++) {
        if (i > 0) {
            printf(" ");
        }
        printf("%d", numbers[i]);
    }
    printf("\n");
    return 0;
}

6
4 8 15 16 23 42

42 23 16 15 8 4

กรณีฐานคือ left >= right ซึ่งครอบคลุมสองแบบ ถ้าจำนวนช่องเป็นคี่ สุดท้าย left กับ right จะชี้ช่องกลางช่องเดียวกัน ถ้าเป็นคู่ left จะเดินข้าม right ไปเลย ทั้งสองแบบแปลว่าไม่เหลืออะไรให้สลับ ถ้าเขียนแค่ == จะพังกับจำนวนคู่ ดูในส่วนลองทำให้พัง

reverse ไม่คืนค่าอะไร แต่แก้อาเรย์ได้จริง เพราะอาเรย์ที่ส่งเข้าฟังก์ชันคืออาเรย์ตัวเดียวกับใน main ตามที่เห็นในบทที่ 8 ต่างจากตัวแปรธรรมดาที่ฟังก์ชันได้แค่สำเนา เหตุผลเบื้องหลังจะเข้าใจในบทที่ 10

ค้นหาแบบแบ่งครึ่ง

มีเลขประจำตัวผู้สอบผ่าน N คน เรียงจากน้อยไปมาก อยากรู้ว่าเลข 1460 อยู่ในรายชื่อไหม วิธีไล่ดูทีละตัวต้องดูมากสุด N ตัว แต่ข้อมูลที่ เรียงแล้ว มีวิธีที่ดีกว่า เหมือนเปิดพจนานุกรมหาคำ ไม่มีใครเปิดทีละหน้าจากหน้าแรก เปิดกลางเล่มก่อน ถ้าคำที่หาอยู่ทีหลัง ก็ทิ้งครึ่งแรกไปเลย

• ปัญหาที่เล็กลง ค้นในครึ่งซ้ายหรือครึ่งขวา ครึ่งใดครึ่งหนึ่ง
• ประกอบคำตอบ ดูช่องกลาง ถ้าตรงก็เจอแล้ว ถ้าช่องกลางน้อยกว่าเลขที่หา เลขนั้นต้องอยู่ทางขวาถ้ามี ไม่อย่างนั้นอยู่ทางซ้าย คำตอบของครึ่งนั้นคือคำตอบเลย
• เล็กที่สุด ช่วงว่าง คือ low มากกว่า high ไม่มีให้ค้นแล้ว ตอบว่าไม่เจอ

วิธีนี้เรียกว่า binary search โปรแกรมข้างล่างพิมพ์ทุกครั้งที่เรียก ให้เห็นว่าช่วงหดลงยังไง ข้อมูลเข้าบรรทัดแรกคือ N กับเลขที่ต้องการหา บรรทัดที่สองคือรายชื่อ ตอบเป็น index ของช่องที่เจอ หรือ -1 ถ้าไม่เจอ

#include <stdio.h>

int ids[100000];

int search(int a[], int low, int high, int target)
{
    if (low > high) {
        printf("low=%d high=%d empty\n", low, high);
        return -1;
    }
    int mid = (low + high) / 2;
    printf("low=%d high=%d mid=%d a[mid]=%d\n", low, high, mid, a[mid]);
    if (a[mid] == target) {
        return mid;
    }
    if (a[mid] < target) {
        return search(a, mid + 1, high, target);
    }
    return search(a, low, mid - 1, target);
}

int main()
{
    int n, target;
    scanf("%d %d", &n, &target);
    for (int i = 0; i < n; i++) {
        scanf("%d", &ids[i]);
    }
    int position = search(ids, 0, n - 1, target);
    printf("position = %d\n", position);
    return 0;
}

10 1460
1012 1047 1105 1188 1230 1302 1377 1419 1460 1525

low=0 high=9 mid=4 a[mid]=1230
low=5 high=9 mid=7 a[mid]=1419
low=8 high=9 mid=8 a[mid]=1460
position = 8

ช่อง 4 คือ 1230 น้อยกว่า 1460 ช่อง 0 ถึง 4 จึงทิ้งได้ทั้งหมด เหลือ 5 ถึง 9 ช่อง 7 คือ 1419 ยังน้อยกว่า เหลือ 8 ถึง 9 แล้วก็เจอที่ช่อง 8 ถ้าเปลี่ยนเลขที่หาเป็น 1200 ซึ่งไม่มีในรายชื่อ จะได้

low=0 high=9 mid=4 a[mid]=1230
low=0 high=3 mid=1 a[mid]=1047
low=2 high=3 mid=2 a[mid]=1105
low=3 high=3 mid=3 a[mid]=1188
low=4 high=3 empty
position = -1

ช่วงหดจาก 10 ช่องเหลือ 4 เหลือ 2 เหลือ 1 แล้วว่าง ทุกครั้งทิ้งได้ครึ่งหนึ่ง ข้อมูลล้านตัวหารสองราวยี่สิบครั้งก็เหลือช่องเดียว ลองบนเครื่องที่เขียนเอกสารนี้กับเลขคู่ 0 ถึง 1999998 ล้านตัว หาเลขต่างๆ สิบแบบทั้งที่มีและไม่มี เรียกตัวเองมากสุด 21 ครั้ง ลึกแค่นั้น stack ไม่มีทางเต็ม เทียบกับไล่ดูทีละตัวที่อาจต้องดูครบล้านตัว ถ้ามีคำถามเป็นแสนข้อ ต่างกันเป็นหลายหมื่นเท่า

เมื่อไรควรใช้ลูปแทน

ผลรวมของอาเรย์แบบ recursion ข้างบนลึกหนึ่งชั้นต่อหนึ่งช่อง ลองขยายอาเรย์เป็นแสนช่องแล้วป้อนคะแนนเยอะๆ บนเครื่องที่เขียนเอกสารนี้ คอมไพล์แบบ Code::Blocks ป้อนคะแนน 32000 ตัวผ่านทั้ง 5 ครั้งที่ลอง ป้อน 33000 ตัวพังด้วย 0xC00000FD ทั้ง 5 ครั้ง ลึกได้น้อยกว่า sum_to ในหน้า 9.1 เพราะมีพารามิเตอร์มากกว่า แต่ละชั้นจึงกินที่มากกว่า

โจทย์ที่ให้อาเรย์ถึงแสนตัวมีเยอะมาก ลูป for ธรรมดาในบทที่ 5 ไม่มีปัญหานี้เลย ถึงแบบ -O2 จะรอดเพราะ compiler แปลงเป็นลูปให้ แต่ไม่ควรเสี่ยง หลักเลือกคือดูว่าเรียกตัวเองลึกแค่ไหน และแตกกิ่งหรือไม่

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

ลองทำให้พัง

แบบที่ 1 ลืมบวกหนึ่งให้ mid

ในโปรแกรม binary search ไม่มีบรรทัดที่พิมพ์ แล้วเขียนกรณีไปทางขวาเป็น

return search(a, mid, high, target);

คิดว่าไม่เป็นไร เพราะช่อง mid ก็แค่ถูกดูซ้ำอีกรอบ ลองกับรายชื่อเดิม หา 1460 ยังได้ 8 หา 1105 ได้ 2 แต่หา 1525 ซึ่งเป็นตัวสุดท้าย หรือหา 1200 ที่ไม่มีในรายชื่อ โปรแกรมพังด้วย 0xC00000FD ไม่มี warning สักตัว

ไล่ด้วยมือกับ 1525 จะเห็นว่าช่วงหดเหลือ low=8 high=9 แล้ว mid = (8 + 9) / 2 = 8 ช่อง 8 คือ 1460 น้อยกว่า 1525 จึงเรียก search(a, 8, 9, ...) ซึ่งเป็นช่วงเดิมเป๊ะ เรียกช่วงเดิมซ้ำไม่รู้จบจน stack เต็ม นี่คือการผิดกฎข้อที่สองของ recursion ปัญหาไม่ได้เล็กลง ทุกการเรียกซ้ำต้องทำให้ช่วงสั้นลงอย่างน้อยหนึ่งช่องเสมอ ช่อง mid ดูไปแล้วจึงต้องตัดทิ้งเป็น mid + 1 และ mid - 1

แบบที่ 2 กรณีฐานของการกลับลำดับเป็น ==

เขียนกรณีฐานของ reverse เป็น if (left == right) ป้อน 5 ตัว 1 2 3 4 5 ได้ 5 4 3 2 1 ถูกต้อง แต่ป้อน 6 ตัว 1 2 3 4 5 6 โปรแกรมพัง บนเครื่องที่เขียนเอกสารนี้ได้

Process returned -1073741819 (0xC0000005)

หกตัว left กับ right เดินเป็น 0 กับ 5 แล้ว 1 กับ 4 แล้ว 2 กับ 3 แล้วกลายเป็น 3 กับ 2 สวนกันไปโดยไม่เคยเท่ากัน ฟังก์ชันจึงสลับกลับคืน แล้วเดินต่อจนออกนอกอาเรย์ 0xC0000005 คือเข้าถึงหน่วยความจำที่ไม่มีสิทธิ์แบบในหน้า 5.5 ทดสอบ recursion ที่บีบสองข้างเข้าหากัน ต้องลองทั้งจำนวนคี่และจำนวนคู่เสมอ

สรุป

• recursion บนอาเรย์ใช้พารามิเตอร์บอกช่วง เช่น i ถึง n หรือ low ถึง high ทุกชั้นใช้อาเรย์ตัวเดียวกัน
• กรณีฐานของช่วงที่บีบเข้าหากันใช้ >= หรือ > ไม่ใช่ ==
• binary search ใช้ได้กับข้อมูลที่เรียงแล้ว ทิ้งครึ่งหนึ่งทุกครั้ง ข้อมูลล้านตัวเรียกราว 21 ครั้ง
• ทุกการเรียกซ้ำต้องทำให้ช่วงสั้นลงจริง mid + 1 กับ mid - 1 ห้ามใช้ mid
• recursion ที่ลึกเท่าขนาดอาเรย์ บนเครื่องที่เขียนเอกสารนี้พังที่ราวสามหมื่นกว่าชั้น งานแบบนี้ใช้ลูป