အခန်း ၁၀ - Recursion

Recursion (ပြန်လည်ခေါ်ဆိုခြင်း) ဆိုတာ Function တစ်ခုက သူ့ကိုယ်သူ ပြန်ခေါ်ပြီး အလုပ်လုပ်တဲ့ နည်းလမ်းတစ်ခု ဖြစ်ပါတယ်။ ပြဿနာ (Problem) ကြီးတစ်ခုကို တူညီတဲ့ပုံစံရှိတဲ့ ပိုသေးငယ်တဲ့ ပြဿနာ (Smaller Subproblem) တွေအဖြစ် ခွဲခြမ်းပြီး ဖြေရှင်းသွားတဲ့ အတွေးအခေါ်ပါ။

Recursion ဟာ magic မဟုတ်ပါဘူး။ နောက်ကွယ်မှာ Function Call Stack ဆိုတဲ့ စနစ်နဲ့ အလုပ်လုပ်တာ ဖြစ်ပါတယ်။ ဒီအခန်းကို ကောင်းစွာ နားလည်ထားရင် နောက်ပိုင်း Trees, Graphs, Backtracking, Dynamic Programming အခန်းတွေအတွက် အခြေခံ ခိုင်မာသွားပါလိမ့်မယ်။

Recursion ၏ အဓိက အယူအဆ (Core Intuition)

Recursion ကို နားလည်ဖို့ အရိုးရှင်းဆုံး ဥပမာဖြစ်တဲ့ Factorial ($n!$) ကို ကြည့်ရအောင်။

$5! = 5 \times 4 \times 3 \times 2 \times 1 = 120$

ဒါကို ဂရုတစိုက် ကြည့်ရင် —

$5! = 5 \times 4!$

$4! = 4 \times 3!$

ဆိုတဲ့ ပုံစံကို တွေ့ရပါမယ်။ ဆိုလိုတာက factorial(5) ကို ဖြေဖို့ factorial(4) ကို သိရင်ရပြီ၊ factorial(4) ကို ဖြေဖို့ factorial(3) ကို သိရင်ရပြီ ဆိုတဲ့ သဘောပါ။ ဒါဟာ ပြဿနာကြီးတစ်ခုကို တူညီတဲ့ ပိုသေးတဲ့ ပြဿနာအဖြစ် ခွဲလိုက်တာ ဖြစ်ပါတယ်။

ဒါပေမယ့် ဒီလို ဆက်ခွဲနေရင် ဘယ်တော့ ရပ်မလဲ။ factorial(1) (သို့) factorial(0) ရောက်ရင် 1 ပြန်ပြီး ရပ်ရပါမယ် (0! = 1 ဖြစ်သည်)။ ဒါကို Base Case လို့ ခေါ်ပါတယ်။

factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))   // factorial(1) = 1 (Base Case)
= 5 * 4 * 3 * 2 * 1
= 120

ဒီနေရာမှာ Recursion ရဲ့ မရှိမဖြစ် အစိတ်အပိုင်း ၂ ခုကို တွေ့ရပါတယ်။

Base Case မရှိရင် function က ဘယ်တော့မှ မရပ်ဘဲ အဆုံးမဲ့ ခေါ်နေပြီး Stack Overflow ဖြစ်သွားပါလိမ့်မယ်။

Function Call Stack

Recursion ကို တကယ် နားလည်ဖို့ Call Stack ကို မြင်တတ်ရပါမယ်။ Function တစ်ခုကို ခေါ်လိုက်တိုင်း computer က အဲ့ဒီ function ရဲ့ အချက်အလက် (parameter, local variable, ပြန်ဆက်လုပ်ရမယ့်နေရာ) ကို Stack ထဲ ထည့်ထားပါတယ်။ Function ပြီးသွားမှ Stack ထဲကနေ ပြန်ထုတ် (pop) ပါတယ်။

factorial(3) ကို ခေါ်လိုက်တဲ့အခါ Call Stack က ဒီလို အလုပ်လုပ်ပါတယ်။

အောက်ဘက်ကို ဆင်းသွားတာ (function တွေ ထပ်ခေါ်တာ) ကို Winding လို့ ခေါ်ပြီး၊ Base Case ရောက်လို့ အပေါ်ပြန်တက်လာတာ (တန်ဖိုးတွေ ပြန်ပေးတာ) ကို Unwinding လို့ ခေါ်ပါတယ်။

Stack Overflow

Stack ရဲ့ နေရာက အကန့်အသတ်ရှိပါတယ်။ Recursion က အလွန်များတဲ့အကြိမ် (ဥပမာ - သိန်းနဲ့ချီ) ထပ်ခေါ်နေရင် Stack ပြည့်သွားပြီး Stack Overflow error ဖြစ်ပါတယ်။ ဒါကြောင့် —

• Base Case ကို မှန်ကန်စွာ သတ်မှတ်ထားရပါမယ်။
• Recursion depth အလွန်နက်နိုင်တဲ့ ပြဿနာတွေအတွက် iteration (loop) သို့မဟုတ် stack data structure ကို သုံးတာက ပိုသင့်တော်ပါတယ်။

Recursion vs Iteration

ပြဿနာတိုင်းကို Recursion နဲ့ ရော Loop (Iteration) နဲ့ ရော ဖြေလို့ ရပါတယ်။ ဘယ်ဟာ ရွေးမလဲ ဆိုတာ ပြဿနာရဲ့ သဘောပေါ်မူတည်ပါတယ်။

မှတ်ချက်: Factorial လို ရိုးရှင်းတဲ့ ပြဿနာတွေကို loop နဲ့ ရေးတာ ပိုသင့်တော်ပေမယ့်၊ Tree traversal, folder ထဲက folder ထဲက file ရှာတာ စတဲ့ ကိုယ်တိုင် ထပ်ဆင့်ခွဲထွက်တဲ့ (nested) ပြဿနာတွေအတွက်တော့ Recursion က အများကြီး ပိုရှင်းပါတယ်။

Tree Recursion

တစ်ခါတစ်ရံ function တစ်ခုက သူ့ကိုယ်သူ တစ်ကြိမ်ထက်ပိုပြီး ပြန်ခေါ်တတ်ပါတယ်။ ဒါကို Tree Recursion လို့ ခေါ်ပါတယ်။ အကောင်းဆုံး ဥပမာက Fibonacci ဖြစ်ပါတယ်။

$fib(n) = fib(n-1) + fib(n-2)$

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

ဒီပုံမှာ fib(2), fib(3) တွေကို အကြိမ်ကြိမ် ထပ်ခါတွက်နေတာ ကို သတိထားမိပါလိမ့်မယ်။ ဒီလို ထပ်နေတဲ့ အလုပ်တွေ (Overlapping Subproblems) ကို သိမ်းထားပြီး ပြန်သုံးတဲ့ နည်းလမ်းကို Dynamic Programming လို့ ခေါ်ပြီး အခန်း ၂၂ မှာ ဆက်လေ့လာရပါမယ်။

Real-world Examples

Recursion ဟာ ပညာရပ်သက်သက်ဆန်တဲ့ concept မဟုတ်ဘဲ၊ programming မှာ Nested ဖွဲ့စည်းထားတဲ့ data တွေကို ကိုင်တွယ်ရာမှာ အမြဲ ကြုံရပါတယ်။

• Folder Traversal — Folder တစ်ခုထဲမှာ folder တွေ ထပ်ရှိ၊ အဲ့ folder တွေထဲမှာ folder တွေ ထပ်ရှိ။ File တွေ အကုန် ရှာဖို့ recursion သုံးရသည်။
• Comment Replies — Comment တစ်ခုအောက်မှာ reply, reply အောက်မှာ reply ထပ်ရှိနိုင်သည် (nested thread)။
• Category Tree / Menu Tree — Category ကြီးအောက်မှာ subcategory, အဲ့အောက်မှာ ထပ်မံ subcategory။
• JSON / DOM Tree — Web page ရဲ့ HTML element တွေဟာ element ထဲ element ထပ်ရှိတဲ့ tree structure ဖြစ်သည်။

ဒီ data တွေအားလုံးရဲ့ တူညီချက်က ကိုယ်တိုင်ကိုယ်ကျ ထပ်ဆင့်ဖွဲ့စည်းထား (self-similar / nested) ခြင်း ဖြစ်ပြီး၊ ဒါက Recursion နဲ့ အကိုက်ညီဆုံး ဖြစ်ပါတယ်။

Questions

Recursion ကို ကောင်းစွာ နားလည်စေဖို့ အခြေခံကျတဲ့ မေးခွန်း ၆ မျိုးကို တစ်ဆင့်ချင်း လေ့လာကြည့်ရအောင်။

၁။ Factorial

အပြုသဘော ကိန်းပြည့် n တစ်ခုအတွက် n! (factorial) ကို recursion သုံးပြီး တွက်ပါ။

$n! = n \times (n-1) \times (n-2) \times \dots \times 1$ ဖြစ်ပြီး 0! = 1 ဖြစ်သည်။

Example 1:

Input: n = 5
Output: 120
Explanation: 5 * 4 * 3 * 2 * 1 = 120

ရှင်းလင်းချက်

ဒါက Recursion ရဲ့ အခြေခံအကျဆုံး ပုစ္ဆာ ဖြစ်ပါတယ်။

• Base Case: n က 0 သို့မဟုတ် 1 ဖြစ်ရင် 1 ကို တန်းပြန်သည်။
• Recursive Case: n * factorial(n - 1) ကို ပြန်သည်။

Time Complexity: $O(n)$ - function ကို n ကြိမ် ခေါ်သောကြောင့်။
Space Complexity: $O(n)$ - Call Stack တွင် တစ်ပြိုင်နက် n ကြိမ်စာ နေရာ ယူသောကြောင့်။

Java Solution

class Solution {
    public long factorial(int n) {
        // Base Case: n က 0 သို့ 1 ဆိုလျှင် ရပ်သည်
        if (n <= 1) {
            return 1;
        }
        // Recursive Case: သူ့ကိုယ်သူ ပိုသေးသော problem ဖြင့် ပြန်ခေါ်သည်
        return n * factorial(n - 1);
    }
}

၂။ Fibonacci Number

Fibonacci အစဉ်ဟာ 0, 1 နဲ့ စပြီး၊ နောက်ဂဏန်းတိုင်းသည် ရှေ့ဂဏန်း ၂ ခု ပေါင်းခြင်း ဖြစ်သည်။ n ပေးထားသည့်အခါ $n^{th}$ Fibonacci number ကို ပြန်ပါ။

$fib(0) = 0$, $fib(1) = 1$, $fib(n) = fib(n-1) + fib(n-2)$

Example 1:

Input: n = 6
Output: 8
Explanation: 0, 1, 1, 2, 3, 5, 8 — index 6 သည် 8 ဖြစ်သည်။

ရှင်းလင်းချက်

ဒါက Tree Recursion ရဲ့ ဥပမာ ဖြစ်ပါတယ်။ function တစ်ခုက သူ့ကိုယ်သူ ၂ ကြိမ် ပြန်ခေါ်ပါတယ်။

• Base Case: n < 2 ဆိုလျှင် n ကို တန်းပြန်သည် (fib(0)=0, fib(1)=1)။
• Recursive Case: fib(n-1) + fib(n-2) ကို ပြန်သည်။

သတိ: ဒီ pure recursion နည်းက subproblem တွေကို အကြိမ်ကြိမ် ထပ်တွက်နေလို့ $O(2^n)$ ကြာပါတယ်။ ဒါကို Memoization နဲ့ $O(n)$ အထိ လျှော့ချနိုင်ပုံကို အခန်း ၂၂ (Dynamic Programming) မှာ ဆက်လေ့လာပါမယ်။

Time Complexity: $O(2^n)$ - recursion tree က အပိုင်းနှစ်ခုစီ ထပ်ဖွဲ့သွားသောကြောင့်။
Space Complexity: $O(n)$ - Call Stack ရဲ့ အနက်ဆုံး အလွှာသည် n ဖြစ်သောကြောင့်။

Java Solution

class Solution {
    public int fib(int n) {
        // Base Case
        if (n < 2) {
            return n;
        }
        // Recursive Case: သူ့ကိုယ်သူ ၂ ကြိမ် ပြန်ခေါ်သည် (Tree Recursion)
        return fib(n - 1) + fib(n - 2);
    }
}

၃။ Reverse a String

Character array s တစ်ခုကို recursion သုံးပြီး နေရာချင်း ပြောင်းပြန် (reverse) လုပ်ပါ။ နေရာအပို မယူဘဲ (in-place) ပြုလုပ်ပါ။

Example 1:

Input: s = ['h','e','l','l','o']
Output: ['o','l','l','e','h']

ရှင်းလင်းချက်

Two Pointers သဘောကို recursion နဲ့ ပေါင်းစပ်ထားတာ ဖြစ်ပါတယ်။ left နဲ့ right အစွန်းနှစ်ဖက်က character တွေကို လဲ၊ ပြီးရင် အတွင်းဘက်ကို ဆက်ဝင်သည်။

• Base Case: left >= right ဆိုလျှင် အလယ်ရောက်ပြီ ဖြစ်လို့ ရပ်သည်။
• Recursive Case: s[left] နဲ့ s[right] ကို လဲပြီး reverse(s, left + 1, right - 1) ကို ဆက်ခေါ်သည်။

Time Complexity: $O(n)$ - character n ခုကို တစ်ကြိမ်စီ ထိသောကြောင့်။
Space Complexity: $O(n)$ - Call Stack အတွက် ဖြစ်သည်။

Java Solution

class Solution {
    public void reverseString(char[] s) {
        reverse(s, 0, s.length - 1);
    }

    private void reverse(char[] s, int left, int right) {
        // Base Case: pointer နှစ်ခု ဆုံသွားလျှင် ရပ်သည်
        if (left >= right) {
            return;
        }
        // အစွန်းနှစ်ဖက် character ကို လဲသည်
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        // အတွင်းဘက်သို့ ဆက်ဝင်သည်
        reverse(s, left + 1, right - 1);
    }
}

၄။ Sum of Nested List

ကိန်းဂဏန်းတွေ ရော list တွေ ရော ရောထားတဲ့ nested list တစ်ခု ပေးထားသည်။ ထဲက ကိန်းဂဏန်း အားလုံးရဲ့ စုစုပေါင်းကို ရှာပါ။ list ထဲမှာ list ထပ်ပါနိုင်သည် (အလွှာ မည်မျှ နက်နက်)။

Example 1:

Input: [1, [2, 3], [4, [5, 6]]]
Output: 21
Explanation: 1 + 2 + 3 + 4 + 5 + 6 = 21

ရှင်းလင်းချက်

ဒါက Recursion ရဲ့ အစစ်အမှန် အသုံးဝင်ပုံ ဖြစ်ပါတယ်။ Nested structure ကို ကိုင်တွယ်ဖို့ recursion က အကိုက်ညီဆုံးပါ။ Element တစ်ခုစီကို ကြည့်ပြီး —

• Base Case: element က ကိန်းဂဏန်း ဖြစ်ရင် အဲ့တန်ဖိုးကို ပေါင်းသည်။
• Recursive Case: element က list ဖြစ်ရင် အဲ့ list ထဲကို recursion နဲ့ ပြန်ဝင်ပြီး စုစုပေါင်းကို ယူသည်။

Time Complexity: $O(n)$ - nested element အားလုံး (စုစုပေါင်း n ခု) ကို တစ်ကြိမ်စီ ကြည့်သောကြောင့်။
Space Complexity: $O(d)$ - d သည် list ၏ အနက်ဆုံး အလွှာ (depth) ဖြစ်သည်။

Java Solution

import java.util.List;

class Solution {
    // Object ဖြစ်နိုင်သည် — Integer သို့မဟုတ် List
    public int sumNested(List<Object> list) {
        int total = 0;
        for (Object item : list) {
            if (item instanceof Integer) {
                // Base Case: ကိန်းဂဏန်းဖြစ်လျှင် တန်းပေါင်းသည်
                total += (Integer) item;
            } else {
                // Recursive Case: list ဖြစ်လျှင် ထဲကို ပြန်ဝင်သည်
                @SuppressWarnings("unchecked")
                List<Object> subList = (List<Object>) item;
                total += sumNested(subList);
            }
        }
        return total;
    }
}

၅။ Binary Tree Preorder Traversal

Binary tree တစ်ခု၏ root ကို ပေးထားသည်။ Node တန်ဖိုးများကို Preorder (root → left → right) အစီအစဉ်ဖြင့် ပြန်ပါ။

Example 1:

Input:
      1
       \
        2
       /
      3
Output: [1, 2, 3]

ရှင်းလင်းချက်

Tree ဆိုတာ သူ့အလိုလို recursive structure ဖြစ်ပါတယ် — node တိုင်းသည် သူ့အောက်မှာ subtree (ပိုသေးတဲ့ tree) တွေ ဆွဲထားပါတယ်။ ဒါကြောင့် tree traversal အတွက် recursion က သဘာဝအကျဆုံး နည်းလမ်း ဖြစ်ပါတယ်။

• Base Case: node က null ဖြစ်လျှင် ဘာမှ မလုပ်ဘဲ ပြန်သည်။
• Recursive Case: node ၏ တန်ဖိုးကို မှတ်၊ ပြီးရင် left subtree ကို recursion ဆက်ဝင်၊ ပြီးရင် right subtree ကို ဆက်ဝင်သည်။

Visit လုပ်တဲ့ အစီအစဉ်ကို ပြောင်းရုံနဲ့ Inorder (left → root → right) နဲ့ Postorder (left → right → root) ကိုလည်း တွက်နိုင်ပါတယ်။ Tree အကြောင်းကို အခန်း ၁၃ မှာ အသေးစိတ် ဆက်လေ့လာပါမယ်။

Time Complexity: $O(n)$ - node n ခုစလုံးကို တစ်ကြိမ်စီ ကြည့်သောကြောင့်။
Space Complexity: $O(h)$ - h သည် tree ၏ အမြင့် (Call Stack depth) ဖြစ်သည်။

Java Solution

import java.util.ArrayList;
import java.util.List;

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode(int val) { this.val = val; }
}

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        traverse(root, result);
        return result;
    }

    private void traverse(TreeNode node, List<Integer> result) {
        // Base Case: node မရှိလျှင် ရပ်သည်
        if (node == null) {
            return;
        }
        result.add(node.val);        // root
        traverse(node.left, result);  // left subtree
        traverse(node.right, result); // right subtree
    }
}

၆။ Generate All Subsets (Combinations Introduction)

Distinct ကိန်းဂဏန်းတွေပါတဲ့ array nums တစ်ခု ပေးထားသည်။ ဖြစ်နိုင်တဲ့ subset (power set) အားလုံးကို ထုတ်ပေးပါ။

Example 1:

Input: nums = [1, 2, 3]
Output: [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
Note: subset များ၏ အစီအစဉ်ကို မည်သို့ဖြစ်စေ (any order) ပြန်နိုင်သည်။

ရှင်းလင်းချက်

ဒါက Recursion ကနေ Backtracking (အခန်း ၁၆) ဆီ ကူးပြောင်းပေးတဲ့ မေးခွန်း ဖြစ်ပါတယ်။ Element တစ်ခုစီအတွက် "ထည့်မလား / မထည့်ဘူးလား" ဆိုတဲ့ ဆုံးဖြတ်ချက် ၂ ခု ရှိပါတယ်။ ဒီ ဆုံးဖြတ်ချက်တွေကို recursion tree အဖြစ် ဖွဲ့ပြီး အကုန်လိုက်စမ်းသွားရပါမယ်။

• Choose: လက်ရှိ element ကို subset ထဲ ထည့်ပြီး ရှေ့ဆက်သည်။
• Explore: နောက် element ဆီ recursion နဲ့ ဆက်ဝင်သည်။
• Undo (Backtrack): ထည့်ထားတဲ့ element ကို ပြန်ထုတ်ပြီး "မထည့်တဲ့" လမ်းကြောင်းကို စမ်းသည်။

Time Complexity: $O(n \times 2^n)$ - subset $2^n$ ခု ရှိပြီး တစ်ခုစီ ကူးယူရန် $O(n)$ ကြာသောကြောင့်။
Space Complexity: $O(n)$ - recursion depth နှင့် လက်ရှိ subset အတွက် (output array မပါ)။ Output အားလုံးကို တွက်ရင်တော့ subset $2^n$ ခု၊ တစ်ခုစီ အရှည် $O(n)$ ဖြစ်လို့ $O(n \cdot 2^n)$ ဖြစ်သည်။

Java Solution

import java.util.ArrayList;
import java.util.List;

class Solution {
    public List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] nums, int start, 
                           List<Integer> current, List<List<Integer>> result) {
        // လက်ရှိ subset ကို အဖြေထဲ ထည့်သည် (လမ်းကြောင်းတိုင်းသည် subset တစ်ခု)
        result.add(new ArrayList<>(current));

        for (int i = start; i < nums.length; i++) {
            // Choose: element ကို ထည့်သည်
            current.add(nums[i]);
            // Explore: နောက် element ဆီ ဆက်ဝင်သည်
            backtrack(nums, i + 1, current, result);
            // Undo: ပြန်ထုတ်ပြီး အခြားလမ်းကြောင်း စမ်းသည်
            current.remove(current.size() - 1);
        }
    }
}