Recursion

មាតិកា

1. Function ដែលហៅខ្លួនឯង
2. ផ្នែកពីរនៃរាល់ Recursion
3. មើល Call Stack
4. Stack Overflow
5. កន្លែងដែលអ្នកជួប Recursion នៅកន្លែងធ្វើការ
6. គិតបែប Recursive
7. អន្ទាក់ Fibonacci និង Memoization
8. Recursion ទល់នឹង Loop
9. បែងចែកហើយយកឈ្នះ៖ Fast Power
10. Backtracking៖ Subset, Permutation, វង់ក្រចក
11. រូបមន្ត៖ recursion.ts សម្រាប់ algolab
12. សាកល្បងដោយខ្លួនឯង

1. Function ដែលហៅខ្លួនឯង

ស្រមៃតុក្កតាប្រដាប់ដាក់គ្នារបស់រុស្ស៊ី៖ បើកតុក្កតាធំ នៅខាងក្នុងមានតុក្កតាតូចជាងដែលបើកបានដូចគ្នា ហើយនៅខាងក្នុងនោះមានតូចជាងទៀត រហូតដល់តុក្កតាតូចមួយដែលបើកមិនបាន។ ដើម្បីរាប់តុក្កតា អ្នកអាចនិយាយថា៖ "ចំនួនតុក្កតាគឺមួយ (តុក្កតានេះ) បូកចំនួនតុក្កតានៅខាងក្នុងវា"។ ប្រយោគនោះកំណត់ចម្លើយតាមរយៈសំណួរដូចគ្នាលើបញ្ហាតូចជាង។ វាឈប់នៅតុក្កតាតូចបំផុត។

នោះគឺជា recursion៖ function ដែលដោះស្រាយបញ្ហាដោយហៅខ្លួនវាផ្ទាល់លើកំណែតូចជាងនៃបញ្ហា រហូតដល់បញ្ហាតូចរហូតដល់ចម្លើយច្បាស់។

Recursion មើលទៅចម្លែកនៅដំបូង ហើយមនុស្សជាច្រើនយល់ថាវាពិបាកជាង loop។ វាក្លាយជារឿងធម្មជាតិ នៅពេលអ្នកជឿលើច្បាប់មួយ៖ សន្មតថា function ដំណើរការរួចហើយសម្រាប់ input តូចជាង ហើយគ្រាន់តែប្រើវា។ ជំពូកនេះបណ្តុះទម្លាប់នោះដោយឧទាហរណ៍តូចៗ បន្ទាប់មកប្រើវាសម្រាប់បញ្ហាដែល loop ចាប់ផ្តើមស្មុគស្មាញ៖ ទិន្នន័យជាន់គ្នា ការសាកល្បងរាល់ការបន្សំ និងការបែងចែកបញ្ហាជាពាក់កណ្តាល។ Tree និង graph នៅជំពូកក្រោយៗស្ទើរតែមិនអាចដោះស្រាយបានដោយគ្មានវា។

2. ផ្នែកពីរនៃរាល់ Recursion

រាល់ recursive function ដែលដំណើរការមានពីរផ្នែកយ៉ាងពិតប្រាកដ៖

1. Base case៖ input តូចរហូតដល់ function return ចម្លើយដោយផ្ទាល់ ដោយមិនហៅបន្ត។
2. Recursive case៖ function ហៅខ្លួនវាផ្ទាល់លើ input តូចជាង ហើយប្រើចម្លើយនោះដើម្បីបង្កើតចម្លើយរបស់ខ្លួន។

ឧទាហរណ៍បុរាណគឺ factorial។ 5! = 5 × 4 × 3 × 2 × 1 = 120។ ចំណាំថា 5! = 5 × 4!។ បញ្ហាធំមានច្បាប់ចម្លងតូចជាងនៃខ្លួនវា៖

function factorial(n: number): number {
  if (n < 0) throw new RangeError("n must be 0 or more");
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // recursive case: a smaller problem
}

console.log(factorial(5)); // 120

ពីរផ្នែកនោះទាញទៅទិសផ្សេងគ្នា។ Recursive case ត្រូវតែផ្លាស់ទី ឆ្ពោះទៅ base case រាល់ការហៅ។ ទីនេះ n ថយចុះម្តងមួយ ដូច្នេះ n ទីបំផុតដល់ 1។ បើអ្នកភ្លេចបន្ថយ input ឬសរសេរ base case ដែលមិនអាចទៅដល់បាន (ឧទាហរណ៍ n === 0 ហើយអ្នកហៅជាមួយ n = 5.5) function នឹងហៅខ្លួនវាជារៀងរហូត។

បញ្ជីត្រួតពិនិត្យសម្រាប់ recursive function ណាមួយ៖

• តើ base case ជាអ្វី? តើរាល់ input អាចទៅដល់វាបានឬទេ?
• តើរាល់ recursive call ទទួលបានបញ្ហា តូចជាង ឬទេ?
• បើខ្ញុំជឿថា recursive call ត្រឹមត្រូវ តើជំហានបន្សំរបស់ខ្ញុំត្រឹមត្រូវឬទេ?

សំណួរចុងក្រោយគឺជាការលោតដោយជំនឿ។ សម្រាប់ factorial៖ "បើ factorial(n - 1) ត្រឹមត្រូវ នោះ n * factorial(n - 1) ត្រឹមត្រូវ។" នោះគ្រប់គ្រាន់ហើយ។ អ្នកមិនចាំបាច់ចងចាំរាល់ការហៅទាំងអស់ក្នុងក្បាលក្នុងពេលតែមួយទេ។

3. មើល Call Stack

ក្នុងជំពូកមុន អ្នកបានរៀនថា call stack ផ្ទុក frame មួយសម្រាប់រាល់ function call ដែលកំពុងសកម្ម។ Recursion ធ្វើឲ្យ stack នោះអាចមើលឃើញ។ នេះគឺ factorial(3) ជាជំហានៗ៖

factorial(3)
  = 3 * factorial(2)
          = 2 * factorial(1)
                  = 1               <- base case reached
          = 2 * 1  = 2
  = 3 * 2  = 6

ជា stack នៃ frame ដែលកើនចុះក្រោម ហើយបន្ទាប់មកថយចុះ៖

call:      factorial(3)  waiting for factorial(2)
call:        factorial(2)  waiting for factorial(1)
call:          factorial(1)  returns 1
return:      factorial(2)  returns 2 * 1 = 2
return:    factorial(3)  returns 3 * 2 = 6

Frame នីមួយៗចងចាំ n របស់ខ្លួន និងកន្លែងដែលវានៅក្នុងការគណនា។ Frame ត្រូវបាន push ពេល function ចូលជ្រៅ ហើយត្រូវបាន pop ពេលចម្លើយត្រឡប់មក។ គ្មានអ្វីពិសេសទេ៖ វាគឺជា call stack ធម្មតា គ្រាន់តែមាន function ដូចគ្នាច្រើនដង។

លេខពីរពិពណ៌នាតម្លៃ៖

• Time៖ ចំនួនការហៅសរុប។ សម្រាប់ factorial(n) គឺ n ដង ដូច្នេះ O(n)។
• Space៖ ជម្រៅដែល stack ឡើងដល់។ សម្រាប់ factorial(n) គឺ n frame នៅចំណុចជ្រៅបំផុត ដូច្នេះ O(n) space ទោះបីយើងមិនដែលបង្កើត array ក៏ដោយ។ តម្លៃ space ដែលលាក់នេះងាយភ្លេច។

4. Stack Overflow

Call stack មានទំហំកំណត់។ បើ recursion ចូលជ្រៅពេក engine នឹងបោះបង់ដោយមានកំហុស។ សាកល្បងបូកលេខពី 1 ដល់មួយលាន៖

function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}

console.log(sumTo(100)); // 5050

try {
  sumTo(1_000_000);
} catch (e) {
  console.log((e as Error).name, (e as Error).message);
}
// RangeError Maximum call stack size exceeded

ដែនកំណត់ច្បាស់លាស់ពឹងលើ engine និងចំនួនដែល frame នីមួយៗរក្សាទុក។ ក្នុង Node.js ជាធម្មតាវាប្រហែលដប់ពាន់ frame ឬច្រើនជាងសម្រាប់ function សាមញ្ញ ដូច្នេះ sumTo(5000) ដំណើរការ ប៉ុន្តែមួយលានមិនដំណើរការទេ។

អ្នកនឹងជួបកំហុសនេះក្នុងស្ថានភាពពីរ៖

1. Bug៖ base case បាត់ ឬមិនអាចទៅដល់បាន។ Recursion មិនដែលឈប់ ហើយ stack overflow យ៉ាងលឿន។
2. Input ជ្រៅពិតប្រាកដ៖ ដូចជា list ដែលមានធាតុមួយលាន ឬរចនាសម្ព័ន្ធតភ្ជាប់ដែលជ្រៅខ្លាំង។

សម្រាប់ករណីទីពីរ អ្នកមានវិធីដោះស្រាយពីរ។ សរសេរ recursion ឡើងវិញជា loop (ប្រហែលជាជាមួយ Stack របស់អ្នកផ្ទាល់ពីជំពូកមុន) ឬកំណត់ជម្រៅនៃ input។ JavaScript engine មិនអនុវត្ត "tail call optimization" ដោយទុកចិត្តបានទេ ដែល call នៅទីតាំងចុងក្រោយប្រើ frame ឡើងវិញ ដូច្នេះកុំពឹងលើវា។ កំណែ loop មិនដែល overflow ទេ៖

function sumToLoop(n: number): number {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

console.log(sumToLoop(1_000_000)); // 500000500000

(ហើយក្នុងករណីជាក់លាក់នេះ រូបមន្ត n * (n + 1) / 2 ពី Math for Programmers ធ្វើបានក្នុង O(1)។)

5. កន្លែងដែលអ្នកជួប Recursion នៅកន្លែងធ្វើការ

• ទិន្នន័យជាន់គ្នា។ File system (folder ក្នុង folder), DOM (element ក្នុង element), JSON ដែលមាន object ជាន់គ្នា, comment thread ដែលមានចម្លើយតបចំពោះចម្លើយតប និងម៉ឺនុយដែលមានម៉ឺនុយរង សុទ្ធតែជា recursive តាមធម្មជាតិ។ Function ដែលដោះស្រាយមួយកម្រិត ហើយហៅខ្លួនវាសម្រាប់កូនៗ ដោះស្រាយបានគ្រប់ជម្រៅ។
• Parser និង compiler។ Expression ដែលមានវង់ក្រចកមាន expression តូចជាងនៅខាងក្នុង។
• បែងចែកហើយយកឈ្នះ (Divide and conquer)។ Merge sort, quick sort និង binary search សុទ្ធតែបំបែកបញ្ហាទៅជាច្បាប់ចម្លងតូចជាងនៃខ្លួនវា។
• Tree និង graph។ Depth-first search គឺជា recursion ដូចដែលអ្នកនឹងឃើញក្នុងជំពូក tree និង graph។
• ការស្វែងរក និងល្បែងផ្គុំ។ ដោះស្រាយ Sudoku, រកគ្រប់ផ្លូវ, បង្កើតគ្រប់ការបន្សំ៖ សាកល្បងជម្រើសមួយ recurse រួច undo ជម្រើស (backtracking នៅពេលក្រោយក្នុងជំពូកនេះ)។
• Deep copy និងការប្រៀបធៀប។ structuredClone, deep equality ក្នុង test library និង JSON serializer សុទ្ធតែ recurse ចូលតម្លៃជាន់គ្នា។

6. គិតបែប Recursive

ទម្លាប់ល្អគឺឆ្លើយសំណួរទាំងនេះតាមលំដាប់ មុនសរសេរកូដ៖

1. តើ input តូចបំផុត ជាអ្វី ហើយចម្លើយរបស់វាជាអ្វី? (Base case។)
2. តើខ្ញុំអាចធ្វើឲ្យ input តូចជាងមួយជំហានដោយរបៀបណា?
3. បើខ្ញុំមានចម្លើយសម្រាប់ input តូចជាង តើខ្ញុំទទួលបានចម្លើយសម្រាប់មួយនេះដោយរបៀបណា?

ឧទាហរណ៍៖ តើ string ជា palindrome ឬទេ? String តូចបំផុតគឺ string ទទេ និងអក្សរតែមួយ៖ ទាំងពីរជា palindrome។ សម្រាប់ string វែងជាងនេះ ប្រៀបធៀបតួអក្សរដំបូង និងចុងក្រោយ។ បើវាខុសគ្នា វាមិនមែនជា palindrome ទេ។ បើវាត្រូវគ្នា ចម្លើយពឹងលើថាតើផ្នែកកណ្តាល (ដោយគ្មានតួអក្សរទាំងពីរនោះ) ជា palindrome ឬទេ។

function isPalindrome(s: string): boolean {
  if (s.length < 2) return true; // base case
  if (s[0] !== s[s.length - 1]) return false;
  return isPalindrome(s.slice(1, -1)); // smaller problem
}

console.log(isPalindrome("racecar")); // true
console.log(isPalindrome("abca")); // false

(slice ចម្លង string រាល់ការហៅ ដូច្នេះនេះគឺ O(n ការេ) ក្នុងករណីអាក្រក់បំផុត។ Loop ជាមួយ two pointer ពីជំពូក array ល្អជាងក្នុងការអនុវត្តជាក់ស្តែង។ កំណែ recursive គឺសម្រាប់រៀនលំនាំ។)

ឧទាហរណ៍៖ ធ្វើឲ្យ array ជាន់គ្នារាបស្មើ (flatten)។ [1, [2, [3, [4]], 5]] គួរតែក្លាយជា [1, 2, 3, 4, 5]។ យើងមិនដឹងថាការជាន់គ្នាជ្រៅប៉ុនណាទេ ដែលធ្វើឲ្យ loop ធម្មតាពិបាក។ Recursion៖ សម្រាប់ធាតុនីមួយៗ បើវាជាលេខ រក្សាវា។ បើវាជា array flatten array នោះ ហើយរក្សាលទ្ធផល។

type Nested<T> = T | Nested<T>[];

function flatten<T>(items: Nested<T>[]): T[] {
  const out: T[] = [];
  for (const item of items) {
    if (Array.isArray(item)) out.push(...flatten(item as Nested<T>[]));
    else out.push(item as T);
  }
  return out;
}

console.log(JSON.stringify(flatten([1, [2, [3, [4]], 5]])));
// [1,2,3,4,5]

Base case លាក់ខ្លួន៖ array ដែលគ្មាន array ជាន់គ្នា គ្រាន់តែមិនដែលធ្វើ recursive call។ Recursive function ជាច្រើនលើទិន្នន័យជាន់គ្នាមើលទៅដូចនេះ។ JavaScript មាន arr.flat(Infinity) ក្នុងខ្លួនដែលធ្វើការងារដូចគ្នា។

7. អន្ទាក់ Fibonacci និង Memoization

លេខ Fibonacci រត់ 0, 1, 1, 2, 3, 5, 8, 13, ... ដែលលេខនីមួយៗជាផលបូកនៃពីរមុនវា។ និយមន័យនេះ recursive រួចហើយ ដូច្នេះកូដសរសេរខ្លួនវាឯង៖

function fibSlow(n: number): number {
  if (n < 2) return n; // base cases: fib(0) = 0, fib(1) = 1
  return fibSlow(n - 1) + fibSlow(n - 2);
}

វាត្រឹមត្រូវ ហើយវាជាមហន្តរាយ។ រាប់ថាតើ function ត្រូវបានហៅប៉ុន្មានដង៖

រាល់ការឡើងមួយជំហាននៃ n គុណចំនួនការហៅប្រហែល 1.6។ នោះគឺជាកំណើន exponential ប្រហែល O(2 ស្វ័យគុណ n) ដែលអ្នកបានជួបក្នុងជំពូក Big-O។ fibSlow(40) ចំណាយពេលប្រហែលកន្លះវិនាទីលើ laptop ហើយ fibSlow(50) ចំណាយពេលមួយនាទី ឬច្រើនជាងនេះ។

ហេតុអ្វីបានជាមានការហៅច្រើនម្ល៉េះ? មើល tree នៃការហៅសម្រាប់ fib(5)៖

                      fib(5)
                    /        \
              fib(4)          fib(3)
             /      \         /     \
        fib(3)    fib(2)   fib(2)   fib(1)
        /   \
    fib(2) fib(1)  ...

fib(3) ត្រូវបានគណនាពីរដង fib(2) បីដង ហើយការធ្វើម្តងទៀតកើនឡើងដូចគ្រាប់ព្រិល។ Function ស្វែងរក បញ្ហារងដដែល ម្តងហើយម្តងទៀត។

ដំណោះស្រាយគឺ memoization៖ ចងចាំចម្លើយនីមួយៗនៅលើកដំបូង ហើយប្រើវាឡើងវិញ។ Map ល្អឥតខ្ចោះ (ជំពូក hash map)៖ key n value fib(n)។

function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

console.log(fibMemo(50)); // 12586269025

ឥឡូវនេះ n នីមួយៗត្រូវបានគណនាម្តង ដូច្នេះមានតែប្រហែល n ការគណនាពិតប្រាកដ៖ O(n) time ជាមួយ O(n) space សម្រាប់ map និង stack។ ការហៅដដែលដែលចំណាយពេលមួយនាទី ឥឡូវភ្លាមៗ។ គ្មានអ្វីផ្លាស់ប្តូរក្នុងតក្កវិជ្ជាទេ។ យើងគ្រាន់តែឈប់ធ្វើការងារដដែលៗ។

Memoization ដំណើរការសម្រាប់ pure function ណាមួយ៖ function ដែលតែងតែ return output ដូចគ្នាសម្រាប់ input ដូចគ្នា ហើយគ្មាន side effect។ អ្នកអាចសរសេរវាម្តងជា wrapper៖

function memoize<A extends unknown[], R>(
  fn: (...args: A) => R,
): (...args: A) => R {
  const cache = new Map<string, R>();
  return (...args: A): R => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

useMemo របស់ React ការ cache ការគណនា API ដែលថ្លៃ និង helper lodash.memoize សុទ្ធតែជាគំនិតនេះ។ ប្រយ័ត្នអង្គចងចាំ៖ cache ដែលមិនដែលបណ្តេញធាតុចាស់ គឺជា memory leak ដែលរង់ចាំ production។ នេះជាគ្រាប់ពូជនៃ dynamic programming ដែលនឹងមានជំពូកផ្ទាល់ខ្លួននៅពេលក្រោយ។

8. Recursion ទល់នឹង Loop

អ្វីៗដែល recursive អាចសរសេរជា loop បាន ហើយផ្ទុយមកវិញក៏ដូចគ្នា។ តើអ្នកគួរប្រើអ្វី?

function fibLoop(n: number): number {
  let a = 0;
  let b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

fibLoop រត់ក្នុង O(n) time និង O(1) space។ វាគ្មានបញ្ហាជម្រៅ stack និងគ្មាន map។ សម្រាប់ Fibonacci loop ឈ្នះ។

ក្បួនមេដៃ៖

• បើទិន្នន័យ រាបស្មើ ឬការងារជាការបូកសរុបសាមញ្ញ ត្រូវប្រើ loop។
• បើទិន្នន័យ ជាន់គ្នា ឬ មានមែក (tree, graph, "សាកល្បងរាល់ជម្រើស") recursion ជាធម្មតាច្បាស់ជាង ហើយ loop នឹងត្រូវការ stack ផ្ទាល់ខ្លួនដើម្បីចងចាំកន្លែងដែលអ្នកនៅ។
• បើជម្រៅអាចធំខ្លាំង (រាប់សែន) សូមពេញចិត្ត loop ជាមួយ stack ច្បាស់លាស់។

ក្នុងការសម្ភាសន៍ ការដោះស្រាយបញ្ហាដោយ recursive ជារឿយៗត្រូវបានទទួលយក។ ត្រូវត្រៀមខ្លួនសម្រាប់សំណួរបន្ត "តើមានអ្វីកើតឡើងជាមួយ input ជ្រៅខ្លាំង?" ហើយអាចនិយាយថា "call stack អាច overflow ដូច្នេះខ្ញុំនឹងបំប្លែងវាទៅជា loop ជាមួយ stack ផ្ទាល់ខ្លួន"។

9. បែងចែកហើយយកឈ្នះ៖ Fast Power

Recursion ក៏ជាវិធី បែងចែកជាពាក់កណ្តាល បញ្ហាផងដែរ។ ដើម្បីគណនា 2^10 ដោយ loop អ្នកគុណដប់ដង។ ប៉ុន្តែ 2^10 = (2^5)^2 ហើយ 2^5 = 2 × (2^2)^2។ ការបែងចែក exponent ជាពាក់កណ្តាលរាល់ពេលត្រូវការតែប្រហែល log2(n) ជំហាន៖

function power(base: number, exp: number): number {
  if (exp === 0) return 1;
  const half = power(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

console.log(power(2, 10)); // 1024
console.log(power(3, 5)); // 243

គណនា half ម្តង ហើយប្រើវាឡើងវិញ។ បើអ្នកសរសេរ power(base, e / 2) * power(base, e / 2) អ្នកនឹងគណនារឿងដដែលពីរដង ហើយបាត់បង់អត្ថប្រយោជន៍ទាំងមូល។ នោះគឺជាកំហុស Fibonacci ក្នុងសំលៀកបំពាក់ក្លែងបន្លំ។

តាមដាន power(2, 10)៖

វាចំណាយ O(log n) time និងជម្រៅ stack O(log n)។ ការបែងចែកបញ្ហាជាពាក់កណ្តាលរាល់ជំហាន គឺជាគំនិតដូចគ្នានៅពីក្រោយ binary search (ជំពូកបន្ទាប់) និង merge sort។ នៅពេលណាដែលអ្នកឃើញ recursion ដែលបែងចែក input ជាពាក់កណ្តាល សូមរំពឹងជម្រៅ log n។

10. Backtracking៖ Subset, Permutation, វង់ក្រចក

Backtracking គឺជា recursion សម្រាប់ "សាកល្បងរាល់លទ្ធភាព"៖ ធ្វើជម្រើសមួយ ស្វែងរករាល់អ្វីដែលកើតពីវា បន្ទាប់មក undo ជម្រើសនោះ ហើយសាកល្បងជម្រើសបន្ទាប់។ ស្រមៃដើរក្នុងព្រៃល្អក់ ហើយត្រឡប់ទៅផ្លូវបំបែកចុងក្រោយនៅពេលជួបទីបញ្ចប់ដែលគ្មានផ្លូវទៅ។ វាបង្កើតការបន្សំ ដោះស្រាយល្បែងផ្គុំដូចជា Sudoku និងបញ្ហា N-Queens ហើយជំរុញការស្វែងរកដែលមានច្បាប់។

លំនាំតែងតែដូចគ្នា៖

explore(state):
  if state is a complete answer: save a copy, return
  for each choice available now:
    make the choice
    explore(new state)
    undo the choice

Subset

រាល់ subset នៃ [1, 2, 3] ("power set")៖ សម្រាប់ធាតុនីមួយៗ អ្នកអាច ទុកវាចោល ឬ យកវា។ នោះជាជម្រើសពីរសម្រាប់ធាតុនីមួយៗ ដូច្នេះមាន subset 2^n។

function subsets<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];

  function explore(i: number): void {
    if (i === items.length) {
      result.push([...current]); // save a COPY
      return;
    }
    explore(i + 1); // leave items[i] out
    current.push(items[i]); // choose it
    explore(i + 1);
    current.pop(); // un-choose (backtrack)
  }

  explore(0);
  return result;
}

console.log(JSON.stringify(subsets([1, 2, 3])));
// [[],[3],[2],[2,3],[1],[1,3],[1,2],[1,2,3]]

ព័ត៌មានលម្អិតពីរបណ្តាលឲ្យមាន bug ភាគច្រើន៖

1. រក្សាទុកច្បាប់ចម្លង ជាមួយ [...current]។ បើអ្នក push current ផ្ទាល់ រាល់លទ្ធផលដែលបានរក្សាទុកចង្អុលទៅ array ដូចគ្នា ហើយវាទាំងអស់ក្លាយជាទទេក្រោយ pop ចុងក្រោយ។
2. Undo អ្វីដែលអ្នកបានធ្វើយ៉ាងពិតប្រាកដ។ pop() បន្ទាប់ពី recursive call ទីពីរ undo push។ បើភ្លេចវា state នឹងលេចធ្លាយចូលមែកបន្ទាប់។

ជម្រើសបង្កើតជា tree ដែលកម្រិតនីមួយៗសម្រេចធាតុមួយបន្ថែមទៀត៖

                    []
         leave 1 /      \ take 1
               []        [1]
        leave 2/  \take 2     ...

Permutation

រាល់លំដាប់នៃ [1, 2, 3]៖ មាន n! (6 សម្រាប់ធាតុបី)។ នៅរាល់ទីតាំង សាកល្បងរាល់ធាតុដែលមិនទាន់ប្រើ។

function permutations<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];
  const used = new Array<boolean>(items.length).fill(false);

  function explore(): void {
    if (current.length === items.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(items[i]);
      explore();
      current.pop();
      used[i] = false;
    }
  }

  explore();
  return result;
}

console.log(JSON.stringify(permutations([1, 2, 3])));
// [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Array used កត់ត្រាថាធាតុណាខ្លះនៅក្នុង current រួចហើយ។ បីបន្ទាត់ "mark, push, recurse" និងបីបន្ទាត់ដែលតាមក្រោយ "pop, unmark" ឆ្លុះគ្នា។ ស៊ីមេទ្រីនោះគឺជារបៀបរក្សាកូដ backtracking ឲ្យត្រឹមត្រូវ។

បង្កើតវង់ក្រចកត្រឹមត្រូវ

បញ្ហា៖ រាយ string ទាំងអស់ដែលមាន n គូនៃវង់ក្រចកផ្គូផ្គងត្រឹមត្រូវ។ សម្រាប់ n = 3៖ ((())), (()()), (())(), ()(()), ()()()។

វិធីឆោតល្ងង់៖ បង្កើតរាល់ string នៃ ( និង ) ហើយត្រង។ នោះគឺ 2^(2n) string។ Backtracking ឆ្លាតជាង៖ វា prune មានន័យថាវាមិនដែលសាងសង់មែកដែលមិនអាចជោគជ័យ។ ច្បាប់គឺ៖

• អ្នកអាចបន្ថែម ( ខណៈដែលអ្នកបានប្រើតិចជាង n នៃវា។
• អ្នកអាចបន្ថែម ) បានលុះត្រាតែមាន ( ច្រើនជាង ) រហូតមកដល់ពេលនេះ។

function generateParentheses(n: number): string[] {
  const result: string[] = [];

  function build(text: string, open: number, close: number): void {
    if (text.length === 2 * n) {
      result.push(text);
      return;
    }
    if (open < n) build(text + "(", open + 1, close);
    if (close < open) build(text + ")", open, close + 1);
  }

  build("", 0, 0);
  return result;
}

console.log(generateParentheses(3).join(" "));
// ((())) (()()) (())() ()(()) ()()()

String គឺ immutable ដូច្នេះ text + "(" បង្កើត string ថ្មីសម្រាប់រាល់ការហៅ។ គ្មានអ្វីត្រូវ undo ទេ ដែលជាមូលហេតុដែលកំណែនេះគ្មាន pop។ Pruning គឺជាគំនិតធំ៖ ឈប់ស្វែងរកភ្លាមៗនៅពេលអ្នកដឹងថាផ្លូវមួយគ្មានសង្ឃឹម។

Towers of Hanoi

បុរាណមួយទៀត។ ផ្លាស់ទី disk n ពី peg A ទៅ peg C ម្តងមួយ មិនដែលដាក់ disk ធំលើ disk តូច ដោយប្រើ peg B ជាសំចតបម្រុង។ ការយល់ដឹង recursive៖ ដើម្បីផ្លាស់ទី disk n ជាដំបូងផ្លាស់ទី n - 1 ចេញពីផ្លូវ ផ្លាស់ទី disk ធំបំផុត បន្ទាប់មកផ្លាស់ទី n - 1 ត្រឡប់មកលើវា។

function hanoi(n: number, from = "A", to = "C", via = "B"): string[] {
  if (n === 0) return [];
  return [
    ...hanoi(n - 1, from, via, to),
    `${from}->${to}`,
    ...hanoi(n - 1, via, to, from),
  ];
}

console.log(hanoi(3).join(" "));
// A->C A->B C->B A->C B->A B->C A->C

វាតែងតែចំណាយ 2^n - 1 ចលនា៖ 7 សម្រាប់ disk បី។ គ្មាននរណាអាចធ្វើបានល្អជាងនេះទេ ហើយរឿងព្រេងនិយាយថា ការផ្លាស់ទី disk 64 នឹងចំណាយពេលយូរជាងអាយុនៃសកលលោក។

តើការស្វែងរកធំប៉ុនណា?

Backtracking អាចថ្លៃ ព្រោះចម្លើយខ្លួនឯងធំសម្បើម៖

ធាតុដប់ផ្តល់ subset 1,024 និង permutation 3,628,800។ ធាតុម្ភៃផ្តល់ subset លើសពីមួយលាន និង permutation ច្រើនជាងអ្វីដែលអ្នកអាចរាប់អស់។ នៅពេលអ្នកសម្ភាសន៍សុំ "ទាំងអស់" នៃអ្វីមួយ ចម្លើយគឺ exponential តាមធម្មជាតិ។ សូមលើកវាឡើង ហើយប្រើ pruning ដើម្បីជៀសវាងការស្វែងរកមែកដែលអ្នកមិនត្រូវការ។

11. រូបមន្ត៖ recursion.ts សម្រាប់ algolab

បង្កើត src/recursion.ts ហើយប្រមូល function ទាំងអស់ពីជំពូកនេះ៖

export function factorial(n: number): number {
  if (n < 0) throw new RangeError("n must be 0 or more");
  if (n <= 1) return 1; // base case
  return n * factorial(n - 1); // smaller problem
}

export function sumTo(n: number): number {
  if (n <= 0) return 0;
  return n + sumTo(n - 1);
}

export function sumToLoop(n: number): number {
  let total = 0;
  for (let i = 1; i <= n; i++) total += i;
  return total;
}

export function power(base: number, exp: number): number {
  if (exp === 0) return 1;
  const half = power(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

export function isPalindrome(s: string): boolean {
  if (s.length < 2) return true;
  if (s[0] !== s[s.length - 1]) return false;
  return isPalindrome(s.slice(1, -1));
}

export function fibSlow(n: number): number {
  if (n < 2) return n;
  return fibSlow(n - 1) + fibSlow(n - 2);
}

export function fibMemo(n: number, memo = new Map<number, number>()): number {
  if (n < 2) return n;
  const cached = memo.get(n);
  if (cached !== undefined) return cached;
  const result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  memo.set(n, result);
  return result;
}

export function fibLoop(n: number): number {
  let a = 0;
  let b = 1;
  for (let i = 0; i < n; i++) [a, b] = [b, a + b];
  return a;
}

export function memoize<A extends unknown[], R>(
  fn: (...args: A) => R,
): (...args: A) => R {
  const cache = new Map<string, R>();
  return (...args: A): R => {
    const key = JSON.stringify(args);
    if (cache.has(key)) return cache.get(key)!;
    const result = fn(...args);
    cache.set(key, result);
    return result;
  };
}

export type Nested<T> = T | Nested<T>[];

export function flatten<T>(items: Nested<T>[]): T[] {
  const out: T[] = [];
  for (const item of items) {
    if (Array.isArray(item)) out.push(...flatten(item as Nested<T>[]));
    else out.push(item as T);
  }
  return out;
}

export function subsets<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];

  function explore(i: number): void {
    if (i === items.length) {
      result.push([...current]);
      return;
    }
    explore(i + 1); // leave items[i] out
    current.push(items[i]); // choose it
    explore(i + 1);
    current.pop(); // un-choose (backtrack)
  }

  explore(0);
  return result;
}

export function permutations<T>(items: T[]): T[][] {
  const result: T[][] = [];
  const current: T[] = [];
  const used = new Array<boolean>(items.length).fill(false);

  function explore(): void {
    if (current.length === items.length) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < items.length; i++) {
      if (used[i]) continue;
      used[i] = true;
      current.push(items[i]);
      explore();
      current.pop();
      used[i] = false;
    }
  }

  explore();
  return result;
}

// All valid strings with n pairs of parentheses
export function generateParentheses(n: number): string[] {
  const result: string[] = [];

  function build(text: string, open: number, close: number): void {
    if (text.length === 2 * n) {
      result.push(text);
      return;
    }
    if (open < n) build(text + "(", open + 1, close);
    if (close < open) build(text + ")", open, close + 1);
  }

  build("", 0, 0);
  return result;
}

export function hanoi(n: number, from = "A", to = "C", via = "B"): string[] {
  if (n === 0) return [];
  return [
    ...hanoi(n - 1, from, via, to),
    `${from}->${to}`,
    ...hanoi(n - 1, via, to, from),
  ];
}

ហើយ test ក្នុង src/recursion.test.ts៖

import { test } from "node:test";
import assert from "node:assert/strict";
import {
  factorial, sumTo, sumToLoop, power, isPalindrome, fibSlow, fibMemo, fibLoop,
  memoize, flatten, subsets, permutations, generateParentheses, hanoi,
} from "./recursion.ts";

test("factorial", () => {
  assert.equal(factorial(0), 1);
  assert.equal(factorial(5), 120);
  assert.throws(() => factorial(-1), RangeError);
});

test("sumTo matches the loop", () => {
  assert.equal(sumTo(100), 5050);
  assert.equal(sumTo(100), sumToLoop(100));
});

test("power", () => {
  assert.equal(power(2, 10), 1024);
  assert.equal(power(3, 5), 243);
  assert.equal(power(7, 0), 1);
});

test("isPalindrome", () => {
  assert.equal(isPalindrome("racecar"), true);
  assert.equal(isPalindrome("abca"), false);
  assert.equal(isPalindrome(""), true);
});

test("three fibonaccis agree", () => {
  for (let n = 0; n <= 20; n++) {
    assert.equal(fibSlow(n), fibLoop(n));
    assert.equal(fibMemo(n), fibLoop(n));
  }
  assert.equal(fibMemo(50), 12586269025);
});

test("memoize caches", () => {
  let calls = 0;
  const square = memoize((n: number) => {
    calls++;
    return n * n;
  });
  assert.equal(square(4), 16);
  assert.equal(square(4), 16);
  assert.equal(calls, 1);
});

test("flatten", () => {
  assert.deepEqual(flatten([1, [2, [3, [4]], 5]]), [1, 2, 3, 4, 5]);
});

test("subsets", () => {
  const result = subsets([1, 2, 3]);
  assert.equal(result.length, 8);
  assert.deepEqual(result[0], []);
  assert.deepEqual(result[7], [1, 2, 3]);
});

test("permutations", () => {
  const result = permutations([1, 2, 3]);
  assert.equal(result.length, 6);
  assert.deepEqual(result[0], [1, 2, 3]);
  assert.deepEqual(result[5], [3, 2, 1]);
});

test("generateParentheses", () => {
  assert.deepEqual(generateParentheses(3), ["((()))", "(()())", "(())()", "()(())", "()()()"]);
});

test("hanoi", () => {
  assert.equal(hanoi(3).length, 7);
  assert.deepEqual(hanoi(2), ["A->B", "A->C", "B->C"]);
});

រត់វា៖

npx tsx --test

បន្ទាប់មកសាកល្បងការហៅពីរបីក្នុង demo.ts៖

import { factorial, sumTo, power, fibMemo, fibLoop, permutations, hanoi } from "./src/recursion";

console.log(factorial(5), sumTo(100), power(2, 10));
console.log(fibMemo(50), fibLoop(50));
console.log(permutations([1, 2, 3]).length);
console.log(hanoi(3).join(" "));

npx tsx demo.ts

120 5050 1024
12586269025 12586269025
6
A->C A->B C->B A->C B->A B->C A->C

ដើម្បីមានអារម្មណ៍ពីការផ្ទុះ exponential ដោយខ្លួនឯង ចូរវាស់ពេល fibSlow(35), fibSlow(38) និង fibSlow(40) ជាមួយ performance.now() ដូចក្នុងជំពូកដំបូង។ រាល់ជំហានពីរនៃ n គួរតែគុណពេលប្រហែល 2.6។ បន្ទាប់មកវាស់ពេល fibMemo(40) ហើយកត់សម្គាល់ថាអ្នកមិនអាចវាស់វាបានទេ។

12. សាកល្បងដោយខ្លួនឯង

1. ផលបូកខ្ទង់។ សរសេរ sumDigits(n) ជា recursive ដូច្នេះ sumDigits(1234) គឺ 10។ តើ base case ជាអ្វី? (គន្លឹះ៖ ខ្ទង់ចុងក្រោយគឺ n % 10 ហើយផ្នែកដែលនៅសល់គឺ Math.floor(n / 10) ជាគំនិតពីនព្វន្ត Modular។)
2. រាប់ចុះ និងរាប់ឡើង។ សរសេរ countdown(n) ដែលបោះពុម្ព n ចុះដល់ 1 ហើយបន្ទាប់មក "liftoff"។ បន្ទាប់មកផ្លាស់ប្តូរតែ លំដាប់នៃពីរបន្ទាត់ ដើម្បីឲ្យវាបោះពុម្ព 1 ឡើងដល់ n ជំនួសវិញ។ តើនេះប្រាប់អ្នកអ្វីអំពីពេលដែលការងារកើតឡើងធៀបនឹង recursive call?
3. ដើរកាត់ object ជ្រៅ។ សរសេរ countLeaves(value) ដែលរាប់តម្លៃដែលមិនមែនជា object ក្នុង object ជាន់គ្នាដូចជា { a: 1, b: { c: 2, d: { e: 3, f: 4 } } }។ ចម្លើយគឺ 4។ បន្ទាប់មកសរសេរ maxDepth(value) ដែល return ថាវាជ្រៅប៉ុនណា (3 ក្នុងករណីនេះ)។
4. ឡើងជណ្តើរ (សម្ភាសន៍)។ អ្នកអាចឡើងជណ្តើរ 1 ឬ 2 ជណ្តើរម្តង។ តើមានវិធីខុសគ្នាប៉ុន្មានដើម្បីឡើង n ជណ្តើរ? សរសេរវាជា recursive (ចម្លើយសម្រាប់ 4 ជណ្តើរគឺ 5) មើលវាយឺតសម្រាប់ n = 40 បន្ទាប់មកជួសជុលវាជាមួយ memoize។ ចំណាំថា recurrence ដូចគ្នានឹង Fibonacci។
5. ការបន្សំ (សម្ភាសន៍)។ សរសេរ combinations(items, k) ដែល return រាល់ subset ដែលមានទំហំ k យ៉ាងពិតប្រាកដ។ សម្រាប់ [1, 2, 3, 4] និង k = 2 មានលទ្ធផល 6។ ប្រើគ្រោង subsets ឡើងវិញ ហើយ prune មែកភ្លាមៗនៅពេល current មាន k ធាតុរួចហើយ ឬនៅពេលមិនមានធាតុគ្រប់គ្រាន់នៅសល់ដើម្បីទៅដល់ k។
6. ការបន្សំអក្សរ (សម្ភាសន៍)។ លើក្តារចុចទូរស័ព្ទ 2 គឺ "abc" ហើយ 3 គឺ "def"។ ផ្តល់ "23" return រាល់ការបន្សំអក្សរ៖ ad ae af bd be bf cd ce cf។ តើលំនាំ backtracking មួយណាសមស្រប?
7. បំប្លែងទៅជា loop។ សរសេរ sumTo ឡើងវិញជា loop ដែលប្រើ Stack ផ្ទាល់ខ្លួនរបស់អ្នក ដោយ push លេខជំនួសឲ្យការហៅ។ នេះគឺជារូបមន្តទូទៅសម្រាប់បំប្លែង recursion ណាមួយទៅជា loop។

Recursion បំបែកបញ្ហាទៅជាច្បាប់ចម្លងតូចជាង ហើយជឿលើច្បាប់ចម្លងតូចជាងថាដំណើរការ។ បន្ទាប់ យើងអនុវត្តគំនិតនៃការបែងចែកជាពាក់កណ្តាលទៅលើ ការស្វែងរក។ ក្នុង Searching អ្នកនឹងជួប binary search ដែលជា algorithm ស្វែងរកធាតុមួយក្នុងចំណោមមួយលានក្នុងប្រហែលម្ភៃជំហាន និងជាមួយដែលងាយបំផុតក្នុងការធ្វើឲ្យខុសដោយមិនដឹងខ្លួន។