แผนการเรียน
/

Recursion: Thinking in Subproblems
หัวใจสำคัญของการแบ่งปัญหาย่อย

Day 04 Morning: Concepts & Recursive Mathematical Functions

วัตถุประสงค์การเรียนรู้

1
เข้าใจแนวคิด Base Case และ Recursive Step
2
การแก้ปัญหาด้วยนิยามทางคณิตศาสตร์แบบเวียนเกิด
3
การวาด Recursion Trees และการวิเคราะห์ความลึกของ Stack

ความหมายของ Recursion

"อัลกอริทึมที่แก้ปัญหาโดยการ ลดขนาดของปัญหา ลงจนกลายเป็นปัญหาย่อยประเภทเดียวกันที่มีขนาดเล็กลง"

ในทางโปรแกรมมิ่ง คือฟังก์ชันที่ เรียกตัวเอง (Self-call) เพื่อทำงานที่ง่ายขึ้น

โครงสร้างของฟังก์ชันเวียนเกิด

1. Base Case

เงื่อนไขที่ทำให้ฟังก์ชัน หยุดเรียกตัวเอง เพื่อป้องกันการทำงานไม่รู้จบ (Infinite Loop)

2. Recursive Step

การลดขนาดปัญหาและ เรียกฟังก์ชันเดิม ด้วยพารามิเตอร์ที่เล็กลง

การคำนวณ Factorial

long long fact(int n) {
  if (n == 0) return 1; // Base Case
  return n * fact(n - 1); // Recursive Step
}
นิยาม: \(n! = n \times (n-1)!\) โดยที่ \(0! = 1\)

ลำดับฟีโบนัชชี (Fibonacci Numbers)

\(F_n = F_{n-1} + F_{n-2}\)

Base Cases

\(F_0 = 0\)
\(F_1 = 1\)

ลำดับที่ได้

0, 1, 1, 2, 3, 5, 8, 13...

Visualization of F7

แผนภูมิแสดงการเรียกฟังก์ชัน (Nodes = Function Calls)

"แต่ละโหนดจะแตกกิ่งก้านตามจำนวนครั้งที่เรียกตัวเองภายในฟังก์ชัน"

สังเกต: จำนวนการเรียกจะเพิ่มขึ้นเป็นทวีคูณ (Exponential)

ทำไม Backtracking ถึงช้า?

"Overlapping Subproblems"

การคำนวณ ปัญหาย่อยเดิมซ้ำๆ หลายครั้ง
เช่น การคำนวณ \(F_2\) ซ้ำกันหลายจุดในต้นไม้ของ \(F_7\)

วิเคราะห์ความซับซ้อนของ Fibonacci

Time Complexity

\(O(2^n)\)

Space Complexity

\(O(n)\)

Space ขึ้นอยู่กับความลึกของ Stack ที่เรียกใช้งาน

แนวคิด Memoization (Smart Recursion)

"จดบันทึกผลลัพธ์ของปัญหาย่อยลงในอาร์เรย์ (Array) หลังจากคำนวณครั้งแรก เพื่อเรียกใช้ใหม่ได้ทันที"

เปลี่ยนจาก \(O(2^n)\) เป็น \(O(n)\) !

Implementation with Memoization

long long memo[13];
long long fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n]; // ใช้ค่าที่จดไว้
  return memo[n] = fib(n - 1) + fib(n - 2); // จดบันทึก
}

หลักการ "First make it work, then make it fast"

แบบฝึกหัดพื้นฐาน Recursion & Memoization

1. Sum of Digits

ฝึกพื้นฐานการนิยามความสัมพันธ์แบบเวียนเกิด (Recurrence Relation)

2. Fibonacci Numbers (CSES)

เรียนรู้การใช้ Memoization เพื่อแก้ปัญหา TLE ในกรณีที่ปัญหาย่อยทับซ้อนกัน

3. Recursive "Hello World" (Kattis)

ฝึกควบคุมจำนวนการเรียกฟังก์ชันแทนการใช้ Loop ปกติ

Problem 1: Sum of Digits

โจทย์: จงเขียนฟังก์ชันเวียนเกิดเพื่อหา "ผลรวมของเลขหลัก" ทั้งหมดของจำนวนเต็ม \(n\)
ตัวอย่าง: ถ้า \(n = 126\) ผลรวมคือ \(1+2+6 = 9\)

เงื่อนไขเพิ่มเติม:

  • ห้ามใช้คำสั่ง for หรือ while
  • ห้ามแปลงเลขเป็น String

Step-by-Step Logic

1 แยกปัญหาย่อย: ผลรวมของ \(126\) คือ เลขหลักสุดท้าย (\(6\)) บวกกับผลรวมของเลขที่เหลือ (\(12\))
2 นิยาม: sumDigits(n) = (n % 10) + sumDigits(n / 10)
int sumDigits(int n) {
  if (n == 0) return 0; // Base Case
  return (n % 10) + sumDigits(n / 10);
}

Problem 2: Fibonacci (CSES Style)

จงหาค่า \(F_n\) เมื่อกำหนด \(n \le 10^6\)

ความท้าทาย: หากใช้ Naive Recursion จะติด TLE แน่นอน เพราะความซับซ้อนคือ \(O(2^n)\)

"เราต้องใช้ Memoization เพื่อลดความซับซ้อนให้เหลือ \(O(n)\)"

Implementation Strategy

long long memo; // เก็บคำตอบที่เคยหาแล้ว

long long fib(int n) {
  if (n <= 1) return n;
  if (memo[n] != -1) return memo[n]; // 1. ตรวจสอบว่าเคยมีคำตอบไหม

  // 2. ถ้าไม่มี ให้คำนวณแล้วจดบันทึกไว้
  return memo[n] = (fib(n - 1) + fib(n - 2)) % MOD;
}
Tip: อย่าลืมทำความสะอาด Array memo ด้วยค่า -1 ก่อนเริ่มทำงานทุกครั้ง

Problem 3: Recursive Greeting

จงพิมพ์คำว่า "Hello World!" จำนวน \(N\) บรรทัด โดยห้ามใช้คำสั่งวนซ้ำ (Loop) ใดๆ ทั้งสิ้น

โจทย์นี้ใช้เพื่อทดสอบความเข้าใจเรื่องความลึกของการเรียก (Recursion Depth) และการทำงานของ Stack

Functional Logic

void sayHello(int n) {
  if (n == 0) return; // Base Case: หยุดเมื่อครบจำนวน
  cout << "Hello World!\n";
  sayHello(n - 1); // Recursive Step: เรียกครั้งที่เหลือ
}

ข้อควรระวัง!

ในภาษา C++ ความลึกของ Recursion ที่มากเกินไป (เช่น \(N > 10^6\)) อาจทำให้เกิด Stack Overflow ได้

สัมประสิทธิ์ทวินาม \(\binom{n}{k}\)

\[\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\]

Base Cases

\[\binom{n}{0} = 1\]
\[\binom{n}{n} = 1\]

ความหมายทางการนับ

จำนวนวิธีเลือกของ \(k\) ชิ้น จากทั้งหมด \(n\) ชิ้น โดยไม่สนใจลำดับ

Binomial Coefficient Implementation

int C(int n, int k) {
  if (k == 0 || k == n) return 1;
  return C(n - 1, k - 1) + C(n - 1, k);
}

"โครงสร้างนี้สัมพันธ์โดยตรงกับ สามเหลี่ยมปาสกาล"

การหา ห.ร.ม. (Greatest Common Divisor)

"ห.ร.ม. ของ \(a\) และ \(b\) คือ ห.ร.ม. ของ \(b\) และเศษที่เหลือจากการหาร \(a\) ด้วย \(b\)"

\[gcd(a, b) = gcd(b, a \pmod b)\]

กรณีฐาน: \(gcd(a, 0) = a\)

Recursive GCD

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

นี่เป็นหนึ่งในอัลกอริทึมเวียนเกิดที่มีประสิทธิภาพสูงที่สุด (\(O(\log(\min(a, b)))\))

Fast Exponentiation

การหาค่า \(x^n\) ในเวลา \(O(\log n)\) แทนที่จะเป็น \(O(n)\)

หาก \(n\) เป็นเลขคู่: \(x^n = (x^{n/2})^2\)

หาก \(n\) เป็นเลขคี่: \(x^n = x \times (x^{(n-1)/2})^2\)

"ใช้แนวคิด Divide and Conquer ในการลดขนาดกำลังลงครึ่งหนึ่งในทุกขั้นตอน"

แบบฝึกหัด: ฟังก์ชันคณิตศาสตร์

1. Binomial

คำนวณการเลือกโดยใช้ความสัมพันธ์แบบเวียนเกิดและ Memoization

2. R2 (Kattis)

ฝึกมองความสัมพันธ์ของตัวเลขในเชิงสมการเวียนเกิดเบื้องต้น

3. Greatest Common Divisor

เขียนฟังก์ชัน ห.ร.ม. แบบ Recursive ตามหลักของ Euclid

Problem 1: Binomial Coefficients

โจทย์: จงคำนวณค่า \(\binom{n}{k}\) โดยใช้นิยามเวียนเกิด:
\(\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}\)

Challenge:

หากไม่ใช้ Memoization ฟังก์ชันจะเรียกซ้ำมหาศาลจนติด Time Limit Exceeded ได้ง่ายมาก

Logic & Implementation

"Base Cases: \(\binom{n}{0} = 1\) และ \(\binom{n}{n} = 1\)"
long long memo;
long long C(int n, int k) {
  if (k == 0 || k == n) return 1;
  if (memo[n][k] != -1) return memo[n][k];
  return memo[n][k] = C(n - 1, k - 1) + C(n - 1, k);
}

*หมายเหตุ: สำหรับค่า n ขนาดใหญ่มาก ควรระวังเรื่อง Integer Overflow

Problem 2: The Mean Relationship

โจทย์: เรารู้ค่า \(R1\) และค่าเฉลี่ย \(S\) จงหาค่า \(R2\) ที่ทำให้ \(S = (R1 + R2) / 2\)

เป้าหมายของการฝึก:

แม้จะแก้ด้วยสมการตรงๆ ได้ แต่ให้ลองวิเคราะห์ว่าคำตอบเปลี่ยนแปลงอย่างไรเมื่อค่าเฉลี่ยเพิ่มขึ้น (Recursive Thinking)

Step-by-Step Logic

1 วิเคราะห์สมการ: \(S = (R1 + R2) / 2 \implies 2S = R1 + R2\)
2 ย้ายข้างเพื่อหา R2: \(R2 = 2S - R1\)
cout << (2 * s) - r1 << endl;

Problem 3: Euclid's Algorithm

"จงเขียนฟังก์ชัน ห.ร.ม. แบบเวียนเกิด (Recursive GCD) ที่รับค่า \(a\) และ \(b\) แล้วคืนค่าตัวหารร่วมที่มากที่สุด"

Hint: อัลกอริทึมนี้ทำงานในเวลา \(O(\log n)\) โดย \(n = \min(a, b)\)

Implementation of GCD

int gcd(int a, int b) {
  if (b == 0) return a; // Base Case
  return gcd(b, a % b); // Recursive Step
}
Competitive Tip: ในภาษา C++ คุณสามารถใช้ฟังก์ชันสำเร็จรูป __gcd(a, b) ได้ทันทีสำหรับการแข่งขันจริง

Mutual Recursion

"สถานการณ์ที่ฟังก์ชันสองฟังก์ชันหรือมากกว่า เรียกสลับกันไปมา เพื่อแก้ปัญหาหนึ่งๆ"
bool isEven(int n) {
  if (n == 0) return true;
  return isOdd(n - 1);
}
bool isOdd(int n) {
  if (n == 0) return false;
  return isEven(n - 1);
}

แบบฝึกหัด: ประสิทธิภาพและการจัดการบิต

1. Fast Modular Exponentiation

คำนวณ \(x^n \pmod M\) สำหรับค่า \(n\) ขนาดมหาศาลโดยใช้เวลา \(O(\log n)\)

2. Reverse Binary Numbers (Kattis)

ฝึกการใช้ Bit Manipulation ร่วมกับการเวียนเกิดเพื่อสลับลำดับบิต

Problem 1: Fast Power (mod M)

โจทย์: รับจำนวนเต็ม \(x, n,\) และ \(M\) จงหาค่าของ \((x^n) \pmod M\)
Constraints: \(n \le 10^{18}\) และ \(M \le 10^9\)

ทำไมต้อง Fast Exponentiation?

การวนลูป \(10^{18}\) ครั้งจะทำให้ติด TLE ทันที เราต้องลดจำนวนการคูณให้เหลือเพียง \(\approx 60\) ครั้งโดยการแบ่งครึ่งกำลังในทุกขั้นตอน

Logic: Divide and Conquer

หลักการ: \(x^n = (x^{n/2})^2\) ถ้า \(n\) เป็นเลขคู่ และ \(x \cdot x^{n-1}\) ถ้า \(n\) เป็นเลขคี่
long long modpow(long long x, long long n, long long m) {
  if (n == 0) return 1 % m;
  long long u = modpow(x, n / 2, m);
  u = (u * u) % m; // คำนวณ u เพียงครั้งเดียว
  if (n % 2 == 1) u = (u * x) % m;
  return u;
}

"Time Complexity: \(O(\log n)\) "

Problem 2: Reverse Binary

โจทย์: รับจำนวนเต็ม \(N\) ในฐานสิบ แปลงเป็นฐานสอง แล้ว "กลับลำดับบิต" จากหลังมาหน้า จากนั้นแสดงผลลัพธ์เป็นฐานสิบ

ตัวอย่าง: 13 (1101) \(\rightarrow\) กลับเป็น 1011 \(\rightarrow\) ผลลัพธ์คือ 11

ฝึกการใช้ Bitwise Operators: &, >>, <<, |

Implementation Strategy

1 ใช้ (n & 1) เพื่อดึงบิตขวาสุด (LSB)
2 ส่งบิตที่ดึงได้ไปสะสมในผลลัพธ์ใหม่โดยการใช้ (ans << 1) | bit
int reverseBits(int n, int ans = 0) {
  if (n == 0) return ans;
  return reverseBits(n >> 1, (ans << 1) | (n & 1));
}

หมายเหตุ: n >> 1 คือการเลื่อนบิตไปทางขวา (หารสอง)

ข้อดีและข้อเสียของ Recursion

ข้อดี

  • • โค้ดสั้น อ่านง่าย (Elegant)
  • • ลดความซับซ้อนของปัญหาใหญ่
  • • เหมาะกับโครงสร้างแบบ Tree/Graph

ข้อเสีย

  • • ใช้หน่วยความจำ (Stack) สูง
  • • อาจช้ากว่าลูป (Overhead)
  • • เสี่ยงต่อปัญหา Stack Overflow

Stack Overflow Alert!

"ทุกครั้งที่มีการเรียกฟังก์ชัน คอมพิวเตอร์จะเก็บข้อมูลลงใน Stack Memory หากเรียกซ้อนกันลึกเกินไป (เช่น \(10^6\) ชั้น) โปรแกรมจะแครชทันที"

ทางแก้: ตรวจสอบ Base Case ให้แม่นยำ หรือเปลี่ยนไปใช้ Iteration ในกรณีที่จำเป็น

Space Complexity Analysis

ความซับซ้อนทางพื้นที่ (Space) ของ Recursion คือ...

\(O(Depth)\)

ไม่ได้ขึ้นอยู่กับจำนวนโหนดทั้งหมด แต่ขึ้นอยู่กับ กิ่งที่ลึกที่สุด ใน Recursion Tree ณ ขณะหนึ่ง

สรุปแนวคิด Recursion

• Base Case: ต้องมีและต้องไปถึงได้เสมอ

• Memoization: เครื่องมือสำคัญในการเปลี่ยน Exponential เป็น Linear

• Math Functions: \(n!\), \(F_n\), \(gcd\), และ \(\binom{n}{k}\) คือแม่แบบของการคิดแบบเวียนเกิด

• Big O: ต้องวิเคราะห์ทั้งเวลา (Time) และพื้นที่ (Stack Space)

ช่วงบ่ายเตรียมพบกับ: Complete Search & Backtracking

แบบฝึกหัด: การตัดสินใจและโครงสร้างการค้นหา

1. Generating Subsets

ฝึกสร้างปัญหาย่อยจากการตัดสินใจ "เลือก" หรือ "ไม่เลือก"

2. Generating Permutations

ฝึกการจัดการสถานะ (State) และการคืนค่าสถานะเมื่อค้นหาเสร็จ

3. Kattis - 4 thought

ประยุกต์ใช้การลองทุกความเป็นไปได้ (Brute Force) กับปัญหาการคำนวณ

Problem 1: All Subsets

โจทย์: จงสร้างสับเซต (Subset) ทั้งหมดของเซต \(\{0, 1, \dots, n-1\}\) โดยใช้การเรียกตัวเอง (Recursion)
ตัวอย่าง: ถ้า \(n = 3\) ต้องได้ชุดข้อมูล 8 ชุด (รวมเซตว่าง)

แนวคิด Decision Tree:

สำหรับสมาชิกแต่ละตัว เรามี 2 ทางเลือกเสมอ: ใส่ลงในสับเซตปัจจุบัน หรือ ไม่ใส่

Step-by-Step Logic

1 Recursive Call: ที่ตำแหน่ง \(k\) ให้เรียก search(k+1) สองครั้ง (ครั้งแรกไม่ใส่ \(k\), ครั้งที่สองใส่ \(k\) เข้าไปในเวกเตอร์)
void search(int k) {
  if (k == n) { /* ประมวลผลสับเซตที่ได้ */ return; }
  search(k+1); // กรณีไม่เลือก k
  subset.push_back(k);
  search(k+1); // กรณีเลือก k
  subset.pop_back(); // Backtrack เพื่อลองทางอื่น
}

Problem 2: All Permutations

จงสร้างวิธีเรียงสับเปลี่ยน (Permutation) ทั้งหมดของตัวเลข \(1\) ถึง \(n\)

ความต่าง: จำนวนวิธีคือ \(n!\) ซึ่งมากกว่าสับเซตมากเมื่อ \(n\) เพิ่มขึ้น

"เราต้องใช้ Array เพื่อจำว่าเลขตัวไหนถูก 'เลือก' ไปแล้วในลำดับปัจจุบัน"

Backtracking Logic

void search() {
  if (permutation.size() == n) { /* ได้ 1 วิธี */ return; }
  for (int i = 1; i <= n; i++) {
    if (chosen[i]) continue; // ข้ามถ้าใช้ไปแล้ว
    chosen[i] = true; permutation.push_back(i);
    search();
    chosen[i] = false; permutation.pop_back(); // ล้างสถานะ
  }
}
Note: เทคนิคการวนลูปแล้วเรียกตัวเองซ้ำพร้อมล้างค่าสถานะคือหัวใจของ Backtracking

Problem 3: The 4 Thought Challenge

มีเลข 4 อยู่สี่ตัว (\(4 \dots 4 \dots 4 \dots 4\)) จงเติมเครื่องหมาย \(\{+, -, *, /\}\) ลงในช่องว่าง 3 ช่อง เพื่อให้ได้ผลลัพธ์ตามที่โจทย์กำหนด

Brute Force Approach: มีความเป็นไปได้เพียง \(4^3 = 64\) วิธี
"ลองทุกวิธีแล้วเก็บคำตอบไว้ล่วงหน้า"

Implementation Strategy

1 สร้างลูปซ้อนกัน 3 ชั้น หรือใช้ Recursion ความลึก 3 เพื่อสุ่มเลือกเครื่องหมาย
2 คำนวณผลลัพธ์โดยระวัง Operator Precedence (คูณ/หาร ทำก่อน บวก/ลบ)
char op[] = {'+', '-', '*', '/'};
for(int i=0; i<4; i++)
  for(int j=0; j<4; j++)
    for(int k=0; k<4; k++)
      /* คำนวณนิพจน์ (4 op[i] 4 op[j] 4 op[k] 4) */