Recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း)

B2.4.4, B2.4.5 (HL): Explain the fundamental concept of recursion. Construct and trace recursive algorithms.
မြန်မာလို: recursion (method က သူ့ကိုယ်သူ ပြန်ခေါ်ခြင်း) ရဲ့ အခြေခံ သဘောတရားကို ရှင်းပြနိုင်ရပါမယ်။ Recursion ကို သုံးတဲ့ algorithm (အယ်လ်ဂိုရီသမ်၊ ပြဿနာကို အဆင့်ဆင့် ဖြေရှင်းတဲ့ နည်းလမ်း) တွေကို ကိုယ်တိုင် တည်ဆောက်နိုင်ပြီး trace (တစ်ဆင့်ချင်း လိုက်ကြည့်ပြီး မှတ်) လုပ်နိုင်ရပါမယ်။

ဒီစာမျက်နှာက HL အတွက်ပဲ ဖြစ်ပါတယ်။ SL (Standard Level) နဲ့ HL (Higher Level) ဆိုတာ IB Computer Science (နိုင်ငံတကာ ကျောင်းတွေမှာ သင်တဲ့ ကွန်ပျူတာသိပ္ပံ သင်ရိုး) သင်တန်းရဲ့ အဆင့်နှစ်ဆင့်ဖြစ်ပြီး HL အပိုင်းတွေက ပိုနက်နက်ရှိုင်းရှိုင်း လေ့လာရတဲ့ အပိုင်းတွေပါ။

• Recursion ဆိုတာ ဘာလဲ: method (သီးခြား အလုပ်တစ်ခု လုပ်ပေးတဲ့ code အပိုင်း) တစ်ခုက သူ့ကိုယ်သူ ပြန်ခေါ်တာပါ။ Base case (recursion ကို ရပ်စေတဲ့ condition) က recursion ကို ရပ်ပေးပြီး recursive case (သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ အပိုင်း) က base case ဆီ တစ်ဆင့်ချင်း နီးလာအောင် လုပ်ပေးပါတယ်။
• Call stack (လက်ရှိ method ခေါ်မှုတွေကို သိမ်းတဲ့ stack): ခေါ်မှု တစ်ခါစီက ကိုယ်ပိုင် variable (တန်ဖိုး သိမ်းထားတဲ့ နာမည်ပေးထားတဲ့ နေရာ) တွေကို သိမ်းထားတဲ့ frame (method ခေါ်မှု တစ်ခုစီရဲ့ ဒေတာကို သိမ်းထားတဲ့ အကွက်) တစ်ခုကို ထပ်ထည့်ပါတယ်။ Frame တွေ များလွန်းရင် StackOverflowError (call stack ပြည့်သွားလို့ ဖြစ်တဲ့ error) ဖြစ်ပါတယ်။
• Linear recursion နဲ့ branching recursion: ခေါ်မှု တစ်ခါစီမှာ သူ့ကိုယ်သူ တစ်ခါပဲ ပြန်ခေါ်ရင် ခေါ်မှုတွေက ကွင်းဆက် တစ်ကြောင်းလို ဖြစ်ပါတယ်။ နှစ်ခါ ဒါမှမဟုတ် ပိုပြီး ပြန်ခေါ်ရင် သစ်ပင်လို အကိုင်းအခက် ခွဲထွက်တဲ့ tree ပုံစံ ဖြစ်ပါတယ်။
• Recursion နဲ့ iteration နှိုင်းယှဉ်ချက်: tree လို self-similar (အပိုင်းတိုင်းက တစ်ခုလုံးနဲ့ ပုံစံတူ ဖြစ်နေတဲ့) ပြဿနာတွေအတွက် recursion က သင့်တော်ပါတယ်။ ရိုးရိုး ရေတွက်တာမျိုးအတွက်တော့ iteration (ထပ်ခါထပ်ခါ လုပ်ခြင်း) ဖြစ်တဲ့ loop (ထပ်ခါထပ်ခါ run တဲ့ code အပိုင်း) က သင့်တော်ပါတယ်။

---

အဓိက အယူအဆများ

Recursion ဆိုတာ ဘာလဲ

Recursion ဆိုတာ method တစ်ခုက ပြဿနာ တစ်ခုကို ပုံစံတူ ပြဿနာငယ်လေးတွေအဖြစ် ခွဲပြီး ဖြေရှင်းဖို့ သူ့ကိုယ်သူ ပြန်ခေါ်တာ ပါ။ ခေါ်မှု တစ်ခါစီက မူလ ပြဿနာရဲ့ ပိုရိုးရှင်းတဲ့ ပုံစံကို ဖြေရှင်းပြီး တိုက်ရိုက် ဖြေရှင်းလို့ရလောက်အောင် ရိုးရှင်းတဲ့ အခြေအနေကို ရောက်တဲ့အထိ ဆက်သွားပါတယ်။

Recursive method (သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ method) တိုင်းမှာ မပါမဖြစ် အပိုင်း နှစ်ခု ရှိပါတယ်:

1. Base case: recursion ကို ရပ်စေတဲ့ condition (မှန်လား မှားလား စစ်တဲ့ အခြေအနေ) ပါ။ Base case မပါရင် method က သူ့ကိုယ်သူ အဆုံးမရှိ ပြန်ခေါ်နေပါလိမ့်မယ်။ ဒါကို infinite recursion (ဘယ်တော့မှ မရပ်တဲ့ recursion) လို့ ခေါ်ပါတယ်။
2. Recursive case: method က ပိုရိုးရှင်းတဲ့ input (program ထဲ ထည့်ပေးတဲ့ ဒေတာ) နဲ့ သူ့ကိုယ်သူ ပြန်ခေါ်ပြီး base case ဆီ တစ်ဆင့်ချင်း နီးလာပါတယ်။

public static int factorial(int n) {
    if (n == 0) {           // base case
        return 1;
    }
    return n * factorial(n - 1);  // recursive case
}

def factorial(n):
    if n != 0:
        return n * factorial(n - 1)    # recursive case
    else:
        return 1                       # base case

Recursive method တိုင်းမှာ base case မဖြစ်မနေ ပါရပါမယ်။ Base case မပါရင် method က ဘယ်တော့မှ မရပ်ဘဲ StackOverflowError ကို ဖြစ်စေပါတယ် (Python မှာတော့ အလားတူ error က RecursionError ပါ)။

Recursion အလုပ်လုပ်ပုံ: Call Stack (လက်ရှိ method ခေါ်မှုတွေကို သိမ်းတဲ့ stack)

Method တစ်ခုက သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့အခါ Java က call stack ပေါ်ကို frame အသစ် တစ်ခု push လုပ်ပါတယ်၊ ဆိုလိုတာက stack (အပေါ်ကနေပဲ ထည့်၊ ထုတ်တဲ့ အထပ်) ရဲ့ အပေါ်ဆုံးမှာ ထည့်ပါတယ်။ Frame တစ်ခုစီမှာ local variable (method ထဲမှာပဲ ရှိတဲ့ variable) တွေနဲ့ parameter (method ကို ပေးလိုက်တဲ့ တန်ဖိုးကို လက်ခံတဲ့ variable) တွေရဲ့ ကိုယ်ပိုင် copy ရှိပါတယ်။ Base case ကို ရောက်တဲ့အခါ frame တွေကို တစ်ခုချင်း pop (stack ရဲ့ အပေါ်ဆုံးကနေ ဖယ်ထုတ်ခြင်း) လုပ်ပြီး frame တစ်ခုစီက သူ့ရလဒ်ကို သူ့ကို ခေါ်ခဲ့တဲ့ caller (ခေါ်တဲ့ method) ဆီ ပြန်ပေးပါတယ်။

factorial(4) ကို trace လုပ်ခြင်း:

factorial(4) = 4 * factorial(3)
             = 4 * 3 * factorial(2)
             = 4 * 3 * 2 * factorial(1)
             = 4 * 3 * 2 * 1 * factorial(0)
             = 4 * 3 * 2 * 1 * 1
             = 24

ခေါ်မှု တစ်ခါစီက stack ရဲ့ အပေါ်မှာ frame တစ်ခု ထပ်တင်ပါတယ်။ Return (ရလဒ်အဖြစ် ပြန်ပေး) လုပ်တိုင်း အပေါ်ဆုံး frame ကို pop လုပ်ပြီး သူ့တန်ဖိုးကို အောက်က caller ဆီ ပေးပါတယ်။ Return မလုပ်ခင် frame တွေ များလွန်းသွားရင် stack အတွက် memory (မှတ်ဉာဏ်) ကုန်သွားပြီး StackOverflowError ဖြစ်ပါတယ်။ Recursive method ကို input အရမ်းကြီးကြီးနဲ့ ခေါ်တိုင်း ဒီလို ပျက်နိုင်တာကို သတိထားပါ: ခေါ်မှုတွေရဲ့ ကွင်းဆက် ရှည်လွန်းရင် မှန်ကန်တဲ့ algorithm တောင် stack ကို ပြည့်လျှံစေနိုင်ပါတယ်။

Linear Recursion နဲ့ Branching Recursion

Recursive method တွေကို ခွဲခြားတဲ့ အဓိက နည်းက သူတို့ရဲ့ call chain (method ခေါ်မှုတွေ အဆင့်ဆင့် ဆက်သွားတဲ့ ကွင်းဆက်) ရဲ့ ပုံသဏ္ဌာန် ပါ:

• Linear recursion (တစ်ကြောင်းတည်း ဆက်သွားတဲ့ recursion): method ကို တစ်ခါ ခေါ်တိုင်း recursive call (သူ့ကိုယ်သူ ပြန်ခေါ်မှု) အများဆုံး တစ်ခု ပဲ run ပါတယ်။ Call chain က မျဉ်းဖြောင့် တစ်ကြောင်းလို ဖြစ်ပါတယ်။ ဥပမာ: factorial၊ sumUpTo၊ array (အရွယ်အစား ပုံသေ၊ အမျိုးအစားတူ ဒေတာစု) ထဲက တန်ဖိုးတွေ ပေါင်းခြင်း၊ binary search (တစ်ဝက်စီ ခွဲပြီး ရှာနည်း)၊ string (စာသား) ကို ပြောင်းပြန်လှန်ခြင်း၊ countDigits။
• Branching recursion (အကိုင်းအခက် ခွဲထွက်တဲ့ recursion): method ကို တစ်ခါ ခေါ်တိုင်း recursive call နှစ်ခု ဒါမှမဟုတ် ပိုပြီး run ပါတယ်။ Call chain က tree ပုံစံ ဖြစ်လာပါတယ်။ ဥပမာ: Fibonacci၊ BST (binary search tree: ဘယ်ဘက် ငယ်၊ ညာဘက် ကြီးတဲ့ binary tree) traversal (tree ထဲက node တိုင်းကို အစဉ်တကျ သွားကြည့်ခြင်း)၊ quicksort (pivot နဲ့ ခွဲပြီး မြန်မြန် စီတဲ့ နည်း)၊ Towers of Hanoi (ပြားတွေကို တိုင် တစ်တိုင်ကနေ နောက်တစ်တိုင်ကို ရွှေ့ရတဲ့ ပဟေဠိ)၊ fractal (အပိုင်းတိုင်းက တစ်ခုလုံးရဲ့ အသေးပုံစံ ဖြစ်နေတဲ့ ပုံ) တွေ။

if / else if / else ထဲမှာ recursive call ရေးထားတဲ့ call site (code ထဲမှာ method ကို ခေါ်ထားတဲ့ နေရာ) နှစ်ခု ပါတဲ့ method ဖြစ်ပေမယ့် ခေါ်မှု တစ်ခါမှာ branch (လမ်းကြောင်း) တစ်ခုပဲ အလုပ်လုပ်ရင် linear ပဲ ဖြစ်ပါတယ်: အရေးကြီးတာက code ထဲမှာ ခေါ်မှု ဘယ်နှစ်ခု ရေးထားလဲ မဟုတ်ဘဲ ခေါ်မှု တစ်ခါမှာ ဘယ်နှစ်ခု တကယ် run လဲ ဆိုတာပါ။

Linear recursion က ယေဘုယျအားဖြင့် ကုန်ကျမှု နည်းပါတယ် (လိုတဲ့ memory က call chain ရဲ့ အနက်၊ ဆိုလိုတာက ခေါ်မှု အဆင့် အရေအတွက်နဲ့ အချိုးကျ တိုးပါတယ်)။ မှန်မှန်ကန်ကန် ရေးရလည်း ပိုလွယ်ပါတယ်။ Branching recursion ကတော့ self-similar ဒေတာတွေကို ဖော်ပြဖို့ ပိုသင့်တော်ပေမယ့် ပြဿနာငယ် တစ်ခုတည်းကို အကြိမ်ကြိမ် ပြန်တွက်နေရရင် အရမ်းကို နှေးသွားနိုင်ပါတယ် (အောက်က Fibonacci ကို ကြည့်ပါ)။

IB CS သင်တန်း တက်နေသူတွေအတွက် မှတ်ချက် (B2.4 syllabus): IB CS ရဲ့ လက်ရှိ syllabus (သင်ရိုး) ထဲက B2.4 အပိုင်းက recursion ကို ကျွမ်းကျင်မှု နှစ်ခု ခွဲထားပါတယ်။ ပထမ တစ်ခုက B2.4.4 Explain (ရှင်းပြပါ) ဖြစ်ပြီး recursion ကို ဖော်ပြတာ၊ base case နဲ့ recursive case တွေကို ခွဲခြား ပြတာ၊ recursion ကို သုံးတဲ့ နေရာတွေကို သိတာနဲ့ ပေးထားတဲ့ ဘယ် recursive method ကိုမဆို (linear ဖြစ်ဖြစ် branching ဖြစ်ဖြစ်) trace လုပ်တာတွေ ပါပါတယ်။ ဒုတိယ တစ်ခုက B2.4.5 Construct and trace (ကိုယ်တိုင် တည်ဆောက်ပါ၊ တစ်ဆင့်ချင်း လိုက်ပြီး မှတ်ပါ) ဖြစ်ပြီး ရိုးရှင်းတဲ့ non-branching၊ ဆိုလိုတာက linear ဖြစ်တဲ့ recursive method တွေကို ရေးတာ ပါပါတယ်။ Branching ဥပမာတွေ (Fibonacci၊ quicksort၊ tree traversal၊ Towers of Hanoi) ကိုတော့ မှတ်မိပြီး trace လုပ်နိုင်ရုံပဲ လိုပါတယ်၊ IB စာမေးပွဲမှာ ကိုယ်တိုင် ရေးခိုင်းမှာ မဟုတ်ပါဘူး။ ဒီ အတိုင်းအတာနဲ့ ကိုက်အောင် အောက်က လေ့ကျင့်ခန်းတွေထဲက construct (ကိုယ်တိုင် ရေးရတဲ့) မေးခွန်း အားလုံးက linear ဖြစ်ပါတယ်။

သိပြီးသား အကြောင်းအရာတွေ

Recursion က သုံးဖူးပြီးသား အယူအဆတွေပေါ်မှာ တည်ဆောက်ထားတာပါ:

• Parameter နဲ့ return type (method က ပြန်ပေးတဲ့ ဒေတာ အမျိုးအစား) ပါတဲ့ method တွေ: recursion ဆိုတာ သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ method ပါ၊ ဒီစာမျက်နှာမှာတော့ static method (class ကိုယ်တိုင် ပိုင်တဲ့ method) ပါ
• Iteration (while / do-while / for loop တွေ): recursion က iteration ရဲ့ အစားထိုး နည်းလမ်း ပါ။ Loop တော်တော်များများကို recursive call တွေအဖြစ် ပြန်ရေးလို့ ရပါတယ်
• Binary search: while loop နဲ့ ရေးခဲ့ဖူးပါတယ်။ ဒီစာမျက်နှာမှာ အဲဒီ algorithm ကိုပဲ တဖြည်းဖြည်း ကျဉ်းလာတဲ့ (low, high) အပိုင်းနဲ့ recursion အဖြစ် ပြထားပါတယ်
• Binary search tree traversal: pre-order / in-order / post-order အစဉ်တွေအတိုင်း စာရွက်ပေါ်မှာ လိုက်သွားခဲ့တုန်းက နာမည် မသိဘဲ recursive ပုံစံ တစ်ခုကို လိုက်နေခဲ့တာပါ

---

အဆင့်ဆင့် ရှင်းပြထားတဲ့ ဥပမာများ

ဥပမာ တစ်ခုစီမှာ LINEAR (linear recursion) ဒါမှမဟုတ် BRANCHING (branching recursion) လို့ တံဆိပ် ကပ်ထားလို့ call chain ရဲ့ ပုံသဏ္ဌာန်ကို တစ်ချက်ကြည့်ရုံနဲ့ သိနိုင်ပါတယ်။ IB စာမေးပွဲမှာ ကိုယ်တိုင် ရေးခိုင်းတဲ့ (construct) မေးခွန်းတွေက LINEAR ဥပမာတွေကပဲ လာပါတယ်။

ဥပမာ 1: နောက်ပြန် ရေတွက်ခြင်း (LINEAR)

အသုံးဝင်တဲ့ recursion တွေထဲမှာ အရိုးရှင်းဆုံးပါ: n ကနေ 1 အထိ နံပါတ်တွေကို နောက်ပြန် print ထုတ်ပြီး နောက်ဆုံးမှာ “Go” ကို print ထုတ်ပါတယ်။

public static void countDown(int n) {
    if (n == 0) {
        System.out.println("Go");
        return;
    }
    System.out.println(n);
    countDown(n - 1);
}

def count_down(n):
    if n != 0:              # recursive case
        print(n)
        count_down(n - 1)
    else:                   # base case
        print("Go")

countDown(3) လို့ ခေါ်ရင် ဒါကို print ထုတ်ပါတယ်:

3
2
1
Go

ခေါ်မှု တစ်ခါမှာ recursive call တစ်ခုပဲ ရှိပါတယ်။ Base case: n == 0။

ဥပမာ 2: Factorial (LINEAR)

Factorial (1 ကနေ n အထိ ကိန်းပြည့်တွေကို မြှောက်ထားတဲ့ ရလဒ်) ရဲ့ သင်္ချာ အဓိပ္ပာယ်: 5! = 5 * 4 * 3 * 2 * 1 = 120 ဖြစ်ပြီး 5! = 5 * 4! လို့လည်း ရေးလို့ ရပါတယ်။

Recursive အဓိပ္ပာယ်: n! = n * (n-1)! ဖြစ်ပြီး 0! = 1 ပါ။

public static int factorial(int n) {
    if (n == 0) {                 // base case
        return 1;
    }
    return n * factorial(n - 1);  // recursive case
}

def factorial(n):
    if n != 0:
        return n * factorial(n - 1)    # recursive case
    else:
        return 1                       # base case

ခေါ်မှု	ပြန်ပေးတဲ့ တန်ဖိုး	တွက်ပုံ
factorial(0)	1	Base case
factorial(1)	1	1 * factorial(0) = 1 * 1
factorial(2)	2	2 * factorial(1) = 2 * 1
factorial(3)	6	3 * factorial(2) = 3 * 2
factorial(4)	24	4 * factorial(3) = 4 * 6

Recursive အဓိပ္ပာယ်က သင်္ချာ အဓိပ္ပာယ်နဲ့ အတိအကျ တူပါတယ်။ ဒီပုံစံ (“f(n) ကို f(n-1) နဲ့ ဖော်ပြခြင်း”) ကြောင့် factorial က recursion ရဲ့ အနာမည်ကြီးဆုံး ဥပမာ ဖြစ်နေတာပါ။

ဥပမာ 3: Array ထဲက တန်ဖိုးတွေ ပေါင်းခြင်း၊ iterative နဲ့ recursive (LINEAR)

Iterative (တူညီတဲ့ အဆင့်တွေကို ထပ်ခါထပ်ခါ လုပ်တဲ့) ပုံစံကို သိပြီးသားပါ:

public static int sumIterative(int[] arr) {
    int total = 0;
    for (int i = 0; i < arr.length; i++) {
        total += arr[i];
    }
    return total;
}

def sum_iterative(arr):
    total = 0
    for i in range(len(arr)):
        total = total + arr[i]
    return total

Recursive ပုံစံမှာ loop variable မရှိလို့ index (နေရာအမှတ်) parameter တစ်ခု လိုပါတယ်:

public static int sumRecursive(int[] arr, int index) {
    if (index == arr.length) {                       // base case
        return 0;
    }
    return arr[index] + sumRecursive(arr, index + 1); // recursive case
}

def sum_recursive(arr, index):
    if index != len(arr):
        return arr[index] + sum_recursive(arr, index + 1)    # recursive case
    else:
        return 0                                             # base case

sumRecursive(arr, 0) နဲ့ ခေါ်ပါ။ Base case: index က array ရဲ့ အဆုံးကို ကျော်သွားတဲ့အခါ။ Recursive case: လက်ရှိ element (အစုထဲက အချက်) ကို သူ့နောက်က element အားလုံးရဲ့ ပေါင်းလဒ်နဲ့ ပေါင်းပါတယ်။

ဒီလို အစဉ်လိုက် တစ်ခုပြီးတစ်ခု လုပ်ရတဲ့ အလုပ်အတွက်တော့ iterative ပုံစံက များသောအားဖြင့် ပိုရှင်းပါတယ်။ Recursion က ပြဿနာမှာ tree တွေ ဒါမှမဟုတ် divide and conquer (ပြဿနာကို အပိုင်းလေးတွေ ခွဲပြီး ဖြေရှင်းနည်း) လို self-similar ဖွဲ့စည်းပုံ ရှိတဲ့အခါ တကယ် အသုံးဝင်ပါတယ်။ ရိုးရိုး array တစ်ခုကို အစကနေ အဆုံး လျှောက်သွားရုံ အလုပ်အတွက်တော့ မလိုပါဘူး။

ဥပမာ 4: Binary Search ကို recursion နဲ့ ရေးခြင်း (LINEAR)

W26 (သင်ခန်းစာ အစီအစဉ်ရဲ့ အပတ် 26) မှာ binary search ကို while loop နဲ့ ရေးခဲ့ပါတယ်။ ဒီမှာတော့ recursion အဖြစ် ရေးထားပါတယ်: algorithm က အတူတူပါပဲ၊ ဒါပေမယ့် loop ပတ်ရင်း တန်ဖိုး ပြောင်းပေးနေရတဲ့ variable တွေ မလိုတော့ပါဘူး:

public static int binarySearch(int[] arr, int target, int low, int high) {
    if (low > high) {                   // base case: not found
        return -1;
    }
    int mid = (low + high) / 2;
    if (arr[mid] == target) {           // base case: found
        return mid;
    }
    if (target < arr[mid]) {
        return binarySearch(arr, target, low, mid - 1);   // recurse left
    }
    return binarySearch(arr, target, mid + 1, high);      // recurse right
}

def binary_search(arr, target, low, high):
    if low > high:                      # base case: not found
        return -1
    mid = (low + high) // 2             # // is integer division - Java's int / does this automatically
    if arr[mid] == target:              # base case: found
        return mid
    if target < arr[mid]:
        return binary_search(arr, target, low, mid - 1)   # recurse left
    return binary_search(arr, target, mid + 1, high)      # recurse right

Array တစ်ခုလုံးကို ရှာမယ့် အပိုင်းအဖြစ် ပေးပြီး ခေါ်ပါ: binarySearch(arr, target, 0, arr.length - 1)။

binarySearch([2, 5, 8, 13, 21, 34, 55], 21, 0, 6) ကို trace လုပ်ခြင်း:

binarySearch(arr, 21, 0, 6): mid=3, arr[3]=13, 21 > 13, recurse right
binarySearch(arr, 21, 4, 6): mid=5, arr[5]=34, 21 < 34, recurse left
binarySearch(arr, 21, 4, 4): mid=4, arr[4]=21, return 4

Code ထဲမှာ recursive call site နှစ်ခု ရှိပါတယ် (ဘယ်ဘက် တစ်ဝက် ဒါမှမဟုတ် ညာဘက် တစ်ဝက်)၊ ဒါပေမယ့် ခေါ်မှု တစ်ခါမှာ တစ်ခုပဲ run ပါတယ်: if က branch တစ်ခုကိုပဲ အတိအကျ ရွေးပေးလို့ပါ။ ဒါကြောင့် call chain က မျဉ်းဖြောင့် တစ်ကြောင်းပဲ ဖြစ်ပါတယ်: ဒါက linear recursion ဖြစ်ပြီး factorial နဲ့ ပုံသဏ္ဌာန် တူပါတယ်။

ဥပမာ 5: Power (LINEAR)

base^exponent (base ကို exponent ခု ထပ်မြှောက်ထားတဲ့ တန်ဖိုး) ကို recursion နဲ့ တွက်ပါ: x^n = x * x^(n-1) ဖြစ်ပြီး x^0 = 1 ပါ။

public static int power(int base, int exponent) {
    if (exponent == 0) {
        return 1;
    }
    return base * power(base, exponent - 1);
}

def power(base, exponent):
    if exponent != 0:
        return base * power(base, exponent - 1)    # recursive case
    else:
        return 1                                   # base case

power(2, 5) လို့ ခေါ်ရင် 32 ကို ပြန်ပေးပါတယ်။ ဒါကလည်း “f(n) ကို f(n-1) နဲ့ ဖော်ပြခြင်း” ပုံစံ နောက်တစ်ခုပါ။

ဥပမာ 6: Fibonacci၊ branching ဥပမာ (BRANCHING၊ trace လုပ်ပြီး ရှင်းပြဖို့သာ)

Fibonacci sequence (Fibonacci ကိန်းစဉ်): 0, 1, 1, 2, 3, 5, 8, 13, … ကိန်း တစ်လုံးစီက သူ့ရှေ့က ကိန်း နှစ်လုံးရဲ့ ပေါင်းလဒ် ဖြစ်ပါတယ်။

public static int fibonacci(int n) {
    if (n == 0) return 0;                              // base case 1
    if (n == 1) return 1;                              // base case 2
    return fibonacci(n - 1) + fibonacci(n - 2);        // TWO recursive calls
}

def fibonacci(n):
    if n == 0:                                     # base case 1
        return 0
    if n == 1:                                     # base case 2
        return 1
    return fibonacci(n - 1) + fibonacci(n - 2)     # TWO recursive calls

Base case နှစ်ခု ရှိပြီး ခေါ်မှု တစ်ခါမှာ recursive call နှစ်ခု ရှိပါတယ်: ဒါက branching recursion ပါ။

fibonacci(4) ကို trace လုပ်ခြင်း:

ခေါ်မှုတွေက tree ရဲ့ အောက်ဘက်ကို ဆင်းသွားပြီး ပြန်ပေးတဲ့ တန်ဖိုးတွေက အပေါ်ကို ပြန်တက်လာပါတယ်။ အကွက် တစ်ကွက်စီက ခေါ်မှု တစ်ခုနဲ့ အဲဒီ ခေါ်မှုက ပြန်ပေးတဲ့ တန်ဖိုးကို ပြပါတယ်။ ပုံထဲက returns ဆိုတာ ပြန်ပေးတယ်၊ base case: returns at once ဆိုတာ base case ဖြစ်လို့ ချက်ချင်း ပြန်ပေးတယ်၊ fibonacci(2), worked out twice ဆိုတာ ခေါ်မှု တစ်ခုတည်းဖြစ်တဲ့ fibonacci(2) ကို နှစ်ခါ တွက်ရတယ်လို့ ဆိုလိုပါတယ်။

Fibonacci ကို recursion နဲ့ တွက်ရင် အရမ်းကို နှေးပါတယ်။ ခေါ်မှု တစ်ခါစီက ခေါ်မှု နှစ်ခု ထပ်ဖြစ်စေလို့ call tree က အဆင့်တိုင်းမှာ နှစ်ဆလောက် ကြီးလာပါတယ်: fibonacci(n) က O(2^n) ဖြစ်ပါတယ်။ Loop သုံးတဲ့ iterative ပုံစံကတော့ O(n) ပါ။ Recursive ပုံစံက fibonacci(4) တစ်ခုအတွက်တောင် fibonacci(2) ကို နှစ်ခါ ပြန်တွက်ပါတယ်။ fibonacci(30) ဆိုရင် ခေါ်မှု သန်း 2.7 ခန့် ဖြစ်ပြီး fibonacci(1) ကို 832,040 ကြိမ် တွက်ပါတယ်။

IB CS သင်တန်း တက်နေသူတွေအတွက် မှတ်ချက်: B2.4.4 မှာ Fibonacci က မှတ်မိပြီး ဖော်ပြနိုင်ရမယ့် ဥပမာပါ: trace လုပ်ရမယ်၊ ဘာကြောင့် နှေးလဲ ရှင်းပြရမယ်၊ iterative ပုံစံနဲ့ နှိုင်းယှဉ်ရမယ်၊ ဒါပေမယ့် ကိုယ်တိုင် ရေးရတဲ့ (construct) မေးခွန်း မဟုတ်ပါဘူး။ ဒီစာမျက်နှာက “recursive method တစ်ခု ရေးပါ” လေ့ကျင့်ခန်းတွေက linear recursion တွေပဲ ဖြစ်ပါတယ်။

ဥပမာ 7: String ကို ပြောင်းပြန်လှန်ခြင်း (LINEAR၊ ထပ်ဆောင်း)

W28 (သင်ခန်းစာ အစီအစဉ်ရဲ့ အပတ် 28) မှာ သင်ခဲ့တဲ့ String method တွေကို သုံးပြီး String ပေါ်မှာ recursion လုပ်ခြင်း:

public static String reverse(String s) {
    if (s.length() <= 1) {
        return s;
    }
    return reverse(s.substring(1)) + s.charAt(0);
}

def reverse(s):
    if len(s) > 1:
        return reverse(s[1:]) + s[0]    # s[1:] is Java's substring(1); s[0] is charAt(0)
    else:
        return s

reverse("JAVA") ကို trace လုပ်ခြင်း:

reverse("JAVA") = reverse("AVA") + 'J'
                = (reverse("VA") + 'A') + 'J'
                = ((reverse("A") + 'V') + 'A') + 'J'
                = (("A" + 'V') + 'A') + 'J'
                = "AV" + 'A' + 'J'
                = "AVA" + 'J'
                = "AVAJ"

Base case: အရှည် 0 ဒါမှမဟုတ် 1 ရှိတဲ့ string က ပြောင်းပြန်လှန်လည်း သူ့ကိုယ်သူပဲ ဖြစ်ပါတယ်။ ခေါ်မှု တစ်ခါစီက ရှေ့ဆုံးက character (စာလုံး ဒါမှမဟုတ် သင်္ကေတ) တစ်လုံးကို ဖယ်ထုတ်ပါတယ်၊ ဒါကြောင့် substring(1) က base case ကို ရောက်တဲ့အထိ string ကို တိုတိုလာစေပါတယ်။

---

Recursion အသုံးဝင်တဲ့ နေရာများ

IB syllabus က ဒီ အသုံးချ နေရာတွေကို ဖော်ပြထားပါတယ်။ ဒါတွေကို မှတ်မိပြီး ဖော်ပြနိုင်အောင် လုပ်ပါ: IB စာမေးပွဲမှာ branching ဥပမာတွေကို trace လုပ်ခိုင်းတာ ဒါမှမဟုတ် ရှင်းပြခိုင်းတာပဲ ရှိပြီး အစကနေ ကိုယ်တိုင် ရေးခိုင်းမှာ မဟုတ်ပါဘူး။

အသုံးချ နေရာ	ပုံသဏ္ဌာန်	Recursion သင့်တော်တဲ့ အကြောင်း
Factorial၊ GCD (အကြီးဆုံး ဘုံဆခွဲကိန်း)၊ 1 ကနေ n အထိ ပေါင်းခြင်း	Linear	သင်္ချာ အဓိပ္ပာယ်ကိုက သူ့ကိုယ်သူ ပြန်ညွှန်းထားပါတယ်: f(n) ကို f(n-1) နဲ့ ဖော်ပြပါတယ်။
Binary search	Linear	ရှာမယ့် အပိုင်းကို တစ်ဝက် ခွဲပြီး target (ရှာနေတဲ့ တန်ဖိုး) ရှိတဲ့ တစ်ဝက်ပေါ်မှာ recursion ဆက်လုပ်ပါတယ်။
String ပြောင်းပြန်လှန်ခြင်း၊ countDigits	Linear	ခေါ်မှု တစ်ခါမှာ character တစ်လုံး / ဂဏန်း တစ်လုံး ဖယ်ထုတ်ပါတယ်။
Fractal ပုံ ဖန်တီးခြင်း (Koch၊ Sierpinski)	Branching	အပိုင်း တစ်ခုစီက တစ်ခုလုံးရဲ့ အသေးချုံ့ထားတဲ့ ပုံတူ ဖြစ်ပါတယ်။
Tree traversal (BST ရဲ့ in-order / pre-order / post-order)	Branching	Node (tree ထဲမှာ ဒေတာ သိမ်းထားတဲ့ အကွက်) တစ်ခုရဲ့ subtree (node တစ်ခုအောက်က tree အသေး) ကိုယ်တိုင်က tree တစ်ခု ဖြစ်လို့ အဆင့်တိုင်းမှာ လုပ်ဆောင်ချက် တစ်ခုတည်းကို သုံးလို့ ရပါတယ်။
Sorting (အစဉ်တကျ စီခြင်း) algorithm များ (quicksort၊ merge sort)	Branching	Array ကို နှစ်ပိုင်း ခွဲပြီး အပိုင်း တစ်ခုစီကို စီပါတယ်: quicksort က pivot (ခွဲဖို့ ရွေးထားတဲ့ တန်ဖိုး) ကို အခြေခံပြီး partition (pivot ထက် ငယ်တာနဲ့ ကြီးတာ နှစ်ဘက် ခွဲခြင်း) လုပ်ပါတယ်။ Merge sort က array ကို တစ်ဝက်စီ ခွဲပြီး စီပြီးသား တစ်ဝက် နှစ်ခုကို ပြန်ပေါင်းပါတယ်။
Towers of Hanoi	Branching	ပြား n-1 ချပ်ကို ဘေးဖယ်ထားပါ၊ အောက်ဆုံး ပြားကို ရွှေ့ပါ၊ ပြီးရင် ပြား n-1 ချပ်ကို သူ့အပေါ် ပြန်တင်ပါ။
အထဲမှာ အထပ်ထပ် ပါနေတဲ့ ဒေတာ (folder တွေ၊ DOM tree၊ JSON tree)	Branching	ထည့်စရာ တစ်ခုစီထဲမှာ item (အချက်) တွေ ပါပြီး အဲဒီ item တချို့ကိုယ်တိုင်က ထည့်စရာတွေ ဖြစ်ပါတယ်။

အားလုံးမှာ တူတဲ့ အချက်: ပြဿနာ တစ်ခုရဲ့ ဒေတာ ဒါမှမဟုတ် အဓိပ္ပာယ်က self-similar ဖြစ်ရင်၊ ဆိုလိုတာက ဘယ်အပိုင်းမဆို တစ်ခုလုံးနဲ့ ဖွဲ့စည်းပုံ တူနေရင်၊ အဲဒီ ပြဿနာက သဘာဝအတိုင်း recursive ဖြစ်ပါတယ်။ Folder ထဲမှာ folder တွေ ပါပါတယ်။ BST ရဲ့ subtree ကိုယ်တိုင်က BST တစ်ခုပါ။ Fractal ရဲ့ အပိုင်း တစ်ခုက fractal တစ်ခုလုံးရဲ့ အသေးချုံ့ထားတဲ့ ပုံတူပါ။ Self-similar ဖွဲ့စည်းပုံကို တွေ့ရင် recursion က များသောအားဖြင့် အရှင်းဆုံး ဖြေရှင်းနည်းကို ပေးပါတယ်။

BST ထဲ ထည့်တာ (insertion) ဘာကြောင့် recursive ဖြစ်သလဲ

Binary search tree ထဲကို နာမည် တစ်ခု ထည့်တဲ့အခါ အဲဒီ နာမည်ကို လက်ရှိ node နဲ့ နှိုင်းယှဉ်ပြီး ဘယ်ဘက် subtree ဒါမှမဟုတ် ညာဘက် subtree ထဲကို ထည့်ပါတယ်။ ဒါပေမယ့် subtree က သူ့ကိုယ်တိုင် BST တစ်ခု ဖြစ်လို့ အဲဒီထဲကို ထည့်တာက ဒေတာ ပိုနည်းတဲ့ ပြဿနာ တစ်ခုတည်းပါပဲ၊ ဒါကြောင့် အဲဒီ subtree ပေါ်မှာ ထည့်ပေးတဲ့ method တစ်ခုတည်းကိုပဲ ပြန်ခေါ်ရုံပါပဲ။ Base case က ဗလာ subtree ကို ရောက်တာပါ: အဲဒီနေရာမှာ နာမည်က leaf (အောက်မှာ node မရှိတော့တဲ့ node) အသစ် ဖြစ်သွားပါတယ်။

ဒါက self-similar ဖွဲ့စည်းပုံ အကြောင်းပြချက်ကို အသုံးချ နေရာ တစ်ခုအတွက် ရေးပြထားတာပါ။ ဒီအကြောင်းပြချက်ကို ရှင်းရှင်းလင်းလင်း ပြောနိုင်တာ၊ ဥပမာ “data structure (ဒေတာ သိမ်းဆည်းပုံ) က အဆင့်တိုင်းမှာ ထပ်နေလို့ လုပ်ဆောင်ချက် တစ်ခုတည်းကို အဆင့်တိုင်းမှာ သုံးလို့ရတယ်” လို့ ပြောနိုင်တာက ဘယ် စာမေးပွဲ ဒါမှမဟုတ် အကဲဖြတ်မှုမှာမဆို “X က ဘာကြောင့် recursive ဖြစ်သလဲ ရှင်းပြပါ” ဆိုတဲ့ မေးခွန်းတွေကို ဖြေဖို့ အသုံးဝင်တဲ့ ကျွမ်းကျင်မှုပါ။

---

Recursion နဲ့ Iteration နှိုင်းယှဉ်ချက်

အချက်	Recursion	Iteration (Loop)
ဖွဲ့စည်းပုံ	Method က သူ့ကိုယ်သူ ပြန်ခေါ်တယ်	Loop က code အပိုင်း တစ်ခုကို ထပ်ခါထပ်ခါ run တယ်
ရပ်ပုံ	Base case	Loop condition (loop ဆက်လုပ်မလား စစ်တဲ့ အခြေအနေ) false ဖြစ်သွားတဲ့အခါ
Memory	Call stack ကို သုံးတယ် (ခေါ်မှု တစ်ခါကို frame တစ်ခု)	ပုံသေ ပမာဏ memory ပဲ သုံးတယ်
ဖတ်ရ လွယ်မှု	Tree / divide-and-conquer ပြဿနာတွေအတွက် များသောအားဖြင့် ပိုရှင်းတယ်	ရိုးရိုး ရေတွက်တာ / ပေါင်းစုတာတွေအတွက် များသောအားဖြင့် ပိုရှင်းတယ်
ဖြစ်နိုင်တဲ့ ပြဿနာ	Base case ကို မရောက်ရင် StackOverflowError	Condition က false ဘယ်တော့မှ မဖြစ်ရင် infinite loop (ဘယ်တော့မှ မရပ်တဲ့ loop)
မြန်နှုန်း	ပိုနှေးနိုင်တယ် (function ခေါ်တိုင်း ကုန်တဲ့ အပိုအလုပ် ရှိလို့)	ယေဘုယျအားဖြင့် ပိုမြန်တယ် (ခေါ်မှုအတွက် အပိုအလုပ် မရှိလို့)

Recursion ကို ဘယ်အချိန် သုံးမလဲ:

• ပုံစံတူ ပြဿနာငယ်လေးတွေအဖြစ် သဘာဝအတိုင်း ခွဲလို့ရတဲ့ ပြဿနာတွေ
• Tree traversal (binary search tree တွေ)
• Divide-and-conquer algorithm တွေ (quicksort၊ merge sort)
• သင်္ချာ အဓိပ္ပာယ်က recursive ဖြစ်နေတဲ့ ပြဿနာတွေ (factorial၊ Fibonacci)

Iteration ကို ဘယ်အချိန် သုံးမလဲ:

• ရိုးရိုး ရေတွက်တာ၊ ပေါင်းစုတာ ဒါမှမဟုတ် တစ်ခုချင်း လျှောက်ကြည့်တာ
• မြန်နှုန်းက အရမ်း အရေးကြီးပြီး ပြဿနာကို loop နဲ့ ရိုးရိုးရှင်းရှင်း ဖြေရှင်းလို့ ရတဲ့အခါ
• Recursion အဆင့် အရမ်းများရင် call stack ကုန်သွားနိုင်တဲ့အခါ

အကြံပြုချက်: Recursive ဖြေရှင်းနည်း တိုင်းကို iterative ပုံစံနဲ့ ပြန်ရေးလို့ ရပါတယ် (iterative ကိုလည်း recursive ပုံစံနဲ့ ပြန်ရေးလို့ ရပါတယ်)။ နှစ်မျိုးလုံး လုပ်နိုင်ရပါမယ်: recursive method ကို loop အဖြစ်၊ loop ကို recursive method အဖြစ် ပြောင်းရေးနိုင်ရပါမယ်။

---

အဖြစ်များတဲ့ အမှားများ

Base case မပါခြင်း:

public static int bad(int n) {
    return n * bad(n - 1);  // no base case, so it recurses until StackOverflowError
}

def bad(n):
    return n * bad(n - 1)    # no base case, so it recurses until RecursionError (Python's StackOverflowError)

Base case ကို ဘယ်တော့မှ မရောက်ခြင်း:

public static int bad(int n) {
    if (n == 0) { return 1; }
    return n * bad(n + 1);  // n increases, never reaches 0
}

def bad(n):
    if n != 0:
        return n * bad(n + 1)    # n increases, never reaches 0
    else:
        return 1

Base case မှာ off-by-one အမှား (တန်ဖိုး တစ် လွဲနေခြင်း):

public static int bad(int n) {
    if (n == 1) { return 1; }  // what if n == 0? Misses it.
    return n * bad(n - 1);
}

def bad(n):
    if n != 1:                   # what if n == 0? Misses it.
        return n * bad(n - 1)
    else:
        return 1

---

Quick Check (အမြန် စစ်ဆေးမေးခွန်း)

Q1. Recursive method မှာ base case ရဲ့ ရည်ရွယ်ချက်က ဘာလဲ။

Q2. factorial(3) က ဘာကို ပြန်ပေးသလဲ။

Q3. Recursive method မှာ base case မပါရင် ဘာဖြစ်မလဲ။

Q4. Recursion က iteration ထက် memory ဘာကြောင့် ပိုသုံးသလဲ။

Q5. fibonacci(5) က ဘာကို ပြန်ပေးသလဲ။

Q6. ဒီထဲက ဘယ်ဟာက linear (branching မဟုတ်တဲ့) recursion ရဲ့ ဥပမာ ဖြစ်သလဲ။

Q7. Recursive method တစ်ခုမှာ သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ return statement (code ထဲက ညွှန်ကြားချက်) နှစ်ခု ပါပါတယ်။ တစ်ခုက if branch ထဲမှာ၊ နောက်တစ်ခုက else branch ထဲမှာ ရှိပါတယ်။ ဒီ method ကို ဘယ်လို ခွဲခြားမလဲ။

---

Trace Exercise (code ကို တစ်ဆင့်ချင်း လိုက်ကြည့်ခြင်း)

Trace 1: power(3, 4) (LINEAR)

Trace: Frame တွေ တစ်ခုချင်း pop ဖြစ်ပြီး stack ပြန်ကျဉ်းလာတဲ့အခါ ခေါ်မှု တစ်ခုစီက ပြန်ပေးတဲ့ တန်ဖိုးကို ဖြည့်ပါ။

public static int power(int base, int exponent) {
    if (exponent == 0) { return 1; }
    return base * power(base, exponent - 1);
}

ခေါ်မှု	base	exponent	ပြန်ပေးတဲ့ တန်ဖိုး
power(3, 4)	3	4
power(3, 3)	3	3
power(3, 2)	3	2
power(3, 1)	3	1
power(3, 0)	3	0	1 (base case)

Trace 2: f(7)၊ မကိန်းတွေရဲ့ ပေါင်းလဒ် (LINEAR)

Trace: Call chain ထဲက ခေါ်မှု တစ်ခုစီက ပြန်ပေးတဲ့ တန်ဖိုးကို State (ဖော်ပြပါ) လုပ်ပါ။

public static int f(int n) {
    if (n <= 0) return 0;
    return n + f(n - 2);
}

ခေါ်မှု	ပြန်ပေးတဲ့ တန်ဖိုး
f(-1)	0 (base case)
f(1) = 1 + f(-1)
f(3) = 3 + f(1)
f(5) = 5 + f(3)
f(7) = 7 + f(5)

Trace 3: hop(8, 2)၊ call site နှစ်ခု ရှိပေမယ့် တစ်ခုပဲ run တယ် (LINEAR)

Trace: ဒီ method မှာ recursive call site နှစ်ခု ရှိပေမယ့် ခေါ်မှု တစ်ခါမှာ တစ်ခုပဲ run ပါတယ်: ဒါကြောင့် linear ပဲ ဖြစ်ပါတယ်။ ပြန်ပေးတဲ့ တန်ဖိုးတွေကို ဖြည့်ပါ။

public static int hop(int x, int y) {
    if (x % 2 == 0) {
        return hop(x - 3, y + x);
    } else if (x > 1) {
        return x + 3 * hop(x - 1, y);
    } else {
        return y - x;
    }
}

ခေါ်မှု	ရွေးခဲ့တဲ့ branch	ပြန်ပေးတဲ့ တန်ဖိုး
hop(1, 14)	else (base case)
hop(4, 10) = hop(1, 14)	if (x % 2 == 0)
hop(5, 10) = 5 + 3 * hop(4, 10)	else-if (x > 1)
hop(8, 2) = hop(5, 10)	if (x % 2 == 0)

Trace 4: mystery(5)၊ branching ဥပမာ (BRANCHING)

Trace: ခေါ်မှု တစ်ခါမှာ recursive call နှစ်ခု ရှိပါတယ်: call chain က မျဉ်းဖြောင့် မဟုတ်ဘဲ tree ပုံစံပါ။ ပြန်ပေးတဲ့ တန်ဖိုးတွေကို ဖြည့်ပါ။

public static int mystery(int n) {
    if (n <= 1) return n;
    return mystery(n - 1) + mystery(n - 2);
}

ခေါ်မှု	ပြန်ပေးတဲ့ တန်ဖိုး
mystery(0)	0 (base case)
mystery(1)	1 (base case)
mystery(2) = mystery(1) + mystery(0)
mystery(3) = mystery(2) + mystery(1)
mystery(4) = mystery(3) + mystery(2)
mystery(5) = mystery(4) + mystery(3)

ဒါက Fibonacci ပါပဲ။ mystery(5) ကို တွက်တဲ့ လမ်းမှာ mystery(3) ကို နှစ်ခါ၊ mystery(2) ကို သုံးခါ တွက်ရတာကို သတိထားကြည့်ပါ: branching ပုံသဏ္ဌာန်ကြောင့် ကွန်ပျူတာက လုပ်ပြီးသား အလုပ်ကို ထပ်လုပ်ရပါတယ်။ ဒါကြောင့် recursive Fibonacci က O(2^n) ဖြစ်တာပါ။

---

Code Completion (code ကွက်လပ် ဖြည့်ခြင်း)

Base case ကို ဖြည့်ပါ: sumUpTo

ကွက်လပ်တွေကို ဖြည့်ပါ: sumUpTo(4) က 1 + 2 + 3 + 4 = 10 ကို ပြန်ပေးရပါမယ်။

public static int sumUpTo(int n) {
    if (n == ) {
        return ;
    }
    return n + sumUpTo(n - );
}

Recursive case ကို ဖြည့်ပါ: factorial

ကွက်လပ်တွေကို ဖြည့်ပါ: factorial ရဲ့ recursive case က n * factorial(n - 1) ပါ။

public static int factorial(int n) {
    if (n == 0) {
        return ;
    }
    return  * factorial(n - );
}

Case နှစ်ခုလုံးကို ဖြည့်ပါ: countDigits

ကွက်လပ်တွေကို ဖြည့်ပါ: countDigits(4523) က 4 ကို ပြန်ပေးရပါမယ်။

public static int countDigits(int n) {
    if (n < ) {
        return ;
    }
    return 1 + countDigits(n / );
}

Base case ဆီ ရွေ့သွားအောင် လုပ်ပါ: countMatches

ကွက်လပ်တွေကို ဖြည့်ပါ: base case index == arr.length ကို နောက်ဆုံးမှာ ရောက်အောင် recursive call က ခေါ်တိုင်း index ကို 1 တိုးပေးရပါမယ်။

public static int countMatches(int[] arr, int target, int index) {
    if (index == arr.length) {
        return ;
    }
    if (arr[index] == target) {
        return  + countMatches(arr, target, index + );
    }
    return countMatches(arr, target, index + );
}

---

Spot the Error (အမှား ရှာခြင်း)

Bug 1: Recursive call က မှားတဲ့ ဘက်ကို သွားနေခြင်း

Bug (code ထဲက အမှား) ရှာပါ: ဒီ method က 1 + 2 + ... + n ကို ပြန်ပေးရမှာ ဖြစ်ပေမယ့် StackOverflowError ဖြစ်နေပါတယ်။

1public static int sum(int n) { 2 if (n > 0) { 3 // recursive case 4 return n + sum(n + 1); 5 } 6 return 0; 7}

Line 4 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Bug 2: Base case မပါခြင်း

Bug ရှာပါ: ဒီ method က n! ကို တွက်ဖို့ ရေးထားတာ ဖြစ်ပေမယ့် ဘယ် input ပေးပေး StackOverflowError ကို throw လုပ်ပါတယ်။

1public static int product(int n) { 2 return n * product(n - 1); 3}

မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

Bug 3: Base case မှာ off-by-one အမှား

Bug ရှာပါ: sumUpTo(3) က 6 အစား 7 ကို ပြန်ပေးနေပါတယ်။ Method က crash (program ရုတ်တရက် ပျက်ပြီး ရပ်သွားခြင်း) မဖြစ်ပေမယ့် အဖြေ မှားနေပါတယ်။

1public static int sumUpTo(int n) { 2 if (n == 0) { 3 return 1; 4 } 5 return n + sumUpTo(n - 1); 6}

Line 3 အတွက် မှန်ကန်တဲ့ ပြင်နည်းကို ရွေးပါ:

---

Predict the Output (output ကို ကြိုခန့်မှန်းခြင်း)

ကြိုခန့်မှန်းပါ: ဒီ code က ဘာကို print ထုတ်မလဲ။

public static void mystery(int n) {
    if (n == 0) { return; }
    System.out.println(n);
    mystery(n - 1);
}
// Call: mystery(4)

ကြိုခန့်မှန်းပါ: ဒီ code က ဘာကို print ထုတ်မလဲ။ (သတိပြုပါ: print က recursive call ရဲ့ နောက်မှာ ရှိပါတယ်။)

public static void mystery2(int n) {
    if (n == 0) { return; }
    mystery2(n - 1);
    System.out.println(n);
}
// Call: mystery2(4)

ကြိုခန့်မှန်းပါ: compute(5, 3) က ဘာကို ပြန်ပေးမလဲ။

public static int compute(int a, int b) {
    if (b == 0) return 0;
    if (b == 1) return a;
    return a + compute(a, b - 1);
}

---

Practice Exercises (လေ့ကျင့်ခန်းများ)

ဒီစာမျက်နှာက ကိုယ်တိုင် ရေးရတဲ့ (construct) လေ့ကျင့်ခန်း တိုင်းက linear recursion ပါ: base case ဆီ ရွေ့သွားတဲ့ recursive call တစ်ခုတည်းပဲ ပါပါတယ်။ Branching ဥပမာတွေ (Fibonacci၊ BST traversal၊ Towers of Hanoi၊ quicksort) ကိုတော့ trace လုပ်ဖို့နဲ့ ရှင်းပြဖို့ပဲ သုံးပါတယ်။ အဲဒါတွေကို အပေါ်က ဥပမာတွေနဲ့ “Recursion အသုံးဝင်တဲ့ နေရာများ” ဇယားမှာ ပြထားပါတယ်။

လေးထောင့်ကွင်းထဲက mark (အမှတ်) တွေက IB CS Paper 2 (IB Computer Science စာမေးပွဲမှာ programming မေးခွန်းတွေ ပါတဲ့ စာစောင်) ရဲ့ ပုံစံအတိုင်း ပေးထားတာပါ၊ IB syllabus နဲ့ လေ့လာနေတဲ့ ကျောင်းသားတွေ ကိုယ့်အဆင့်ကို ချိန်ကြည့်နိုင်အောင်ပါ။ IB သင်တန်း မတက်တဲ့ သူတွေကတော့ အယူအဆ တစ်ခုစီ ဘယ်လောက် အလေးပေးရလဲ နှိုင်းယှဉ်ကြည့်ဖို့ လမ်းညွှန်အဖြစ် သုံးနိုင်ပါတယ်။ ဥပမာ [2 marks] ဆိုတာ 2 မှတ် ဖြစ်ပါတယ်။

Core (အခြေခံ အဆင့်)

1. Programming မှာ သုံးတဲ့ “recursion” ဆိုတဲ့ ဝေါဟာရကို Define (အဓိပ္ပာယ်ကို တိတိကျကျ ဖော်ပြပါ) လုပ်ပါ။ [2 marks]

2. Recursive method တိုင်းမှာ မဖြစ်မနေ ပါရမယ့် အစိတ်အပိုင်း နှစ်ခုကို State လုပ်ပါ။ [2 marks]

3. အောက်က method call ကို Trace လုပ်ပြီး ပြန်ပေးတဲ့ တန်ဖိုးကို State လုပ်ပါ: [3 marks]

public static int f(int n) {
    if (n <= 0) return 0;
    return n + f(n - 2);
}

f(7);

def f(n):
    if n > 0:
        return n + f(n - 2)    # recursive case
    else:
        return 0               # base case

f(7)

4. n >= 1 ဖြစ်ရင် 1 + 2 + ... + n ကို ပြန်ပေးပြီး n == 0 ဖြစ်ရင် 0 ကို ပြန်ပေးတဲ့ recursive method public static int sumUpTo(int n) ကို ရေးပါ။ [3 marks]

Extension (တိုးချဲ့ အဆင့်)

5. arr ထဲမှာ index နေရာကနေ စပြီး target ဘယ်နှစ်ကြိမ် ပါလဲ ဆိုတဲ့ အရေအတွက်ကို ပြန်ပေးတဲ့ recursive method public static int countMatches(int[] arr, int target, int index) ကို ရေးပါ။ Method ကို index = 0 နဲ့ ခေါ်ရပါမယ်။ [4 marks]

6. စကားလုံးကို ရှေ့ကနေ ဖတ်ဖတ် နောက်ကနေ ဖတ်ဖတ် တူနေရင် true ကို ပြန်ပေးတဲ့ recursive method public static boolean isPalindrome(String word) ကို ရေးပါ။ charAt() နဲ့ substring() ကို သုံးပါ။ [4 marks]

7. အောက်က recursive method ကို ကြည့်ပါ:

public static int hop(int x, int y) {
    if (x % 2 == 0) {
        return hop(x - 3, y + x);
    } else if (x > 1) {
        return x + 3 * hop(x - 1, y);
    } else {
        return y - x;
    }
}

def hop(x, y):
    if x % 2 == 0:
        return hop(x - 3, y + x)
    elif x > 1:
        return x + 3 * hop(x - 1, y)
    else:
        return y - x

(a) hop(6, 1) method call ကို Trace လုပ်ပါ။ Recursive call တစ်ခုစီနဲ့ အဆင့်တိုင်းမှာ ပြန်ပေးတဲ့ တန်ဖိုးကို ပြပါ။ [4 marks]

(b) Method ရဲ့ body (method ထဲက code) မှာ recursive call နှစ်ခု ပါပါတယ်။ ဒီ method ကို branching recursion မဟုတ်ဘဲ linear recursion လို့ ဘာကြောင့် ခွဲခြားသလဲဆိုတာ Explain လုပ်ပါ။ [2 marks]

8. ထပ်ခါထပ်ခါ လုပ်ရတဲ့ ပြဿနာတွေကို ဖြေရှင်းတဲ့ နည်းလမ်းတွေအဖြစ် recursion နဲ့ iteration ကို Compare (နှစ်ခုလုံးကို တစ်လျှောက်လုံး ကိုးကားပြီး တူတဲ့ အချက်တွေကို ဖော်ပြပါ) လုပ်ပါ။ [4 marks]

Exam-Style (စာမေးပွဲ ပုံစံ မေးခွန်း၊ 14 marks)

9. Recursive method တစ်ခုကို အောက်ပါအတိုင်း သတ်မှတ်ထားပါတယ်:

public static int compute(int a, int b) {
    if (b == 0) return 0;
    if (b == 1) return a;
    return a + compute(a, b - 1);
}

def compute(a, b):
    if b == 0:
        return 0
    if b == 1:
        return a
    return a + compute(a, b - 1)

(a) compute(5, 3) method call ကို Trace လုပ်ပါ။ Recursive call တစ်ခုစီနဲ့ အဆင့်တိုင်းမှာ ပြန်ပေးတဲ့ တန်ဖိုးကို ပြပါ။ [4 marks]

(b) compute method က ယေဘုယျအားဖြင့် ဘာကို တွက်သလဲဆိုတာ Describe (ဖော်ပြရှင်းပြပါ) လုပ်ပါ။ [2 marks]

(c) ဒီ method ထဲက base case (တစ်ခု ဒါမှမဟုတ် တစ်ခုထက် ပို) ကို Identify (ဖြစ်နိုင်တဲ့ အဖြေတွေထဲက ရွေးပြီး ဖော်ပြပါ) လုပ်ပါ။ [2 marks]

(d) compute(a, b) နဲ့ ရလဒ် တူတဲ့ iterative method တစ်ခုကို ရေးပါ။ [3 marks]

(e) Iterative ပုံစံနဲ့ နှိုင်းယှဉ်ရင် recursive ပုံစံရဲ့ အားသာချက် တစ်ခုနဲ့ အားနည်းချက် တစ်ခုကို State လုပ်ပါ။ [2 marks]

(f) compute(5, -1) လို့ ခေါ်လိုက်ရင် ဘာဖြစ်မလဲဆိုတာ Explain လုပ်ပါ။ [1 mark]

Homework / Bonus (အိမ်စာ / အပို လေ့ကျင့်ခန်း)

10. Positive integer (အပေါင်း ကိန်းပြည့်) တစ်ခုမှာ ဂဏန်း ဘယ်နှစ်လုံး ပါလဲ ဆိုတာကို ပြန်ပေးတဲ့ recursive method public static int countDigits(int n) ကို ရေးပါ (ဥပမာ countDigits(4523) က 4 ကို ပြန်ပေးပါတယ်)။ အကြံပြုချက်: base case က n < 10 (ဂဏန်း တစ်လုံးတည်း) ဖြစ်ပြီး recursive case က 10 နဲ့ စားပါတယ်။ [3 marks]

---

GitHub Classroom (အလိုအလျောက် စစ်ဆေးတဲ့ test တွေပါတဲ့ programming assignment များ)

Recursion Exercises

Practice writing and tracing recursive methods. Every task is linear (single recursive call per invocation): branching examples like Fibonacci are on this page for tracing only, not for you to write. Each method must have a clearly identifiable base case and a recursive case that moves toward it.

A class assignment on GitHub Classroom: use it when your teacher has set it. It needs a free GitHub account.

Core + Extension Accept the assignment on GitHub

Working in the Codespace

1. Accept and open. Accept the assignment above, open the link in the email from GitHub, then press Open in Codespace. In Java, change the status bar from Lightweight to Standard mode.
2. Write and check. Open src/Factorial.java and complete each TODO with a single recursive call (n * factorial(n - 1)) guarded by the base case. Press Run and compare the output with the comments, or run bash run-tests.sh in the Terminal.
3. Submit. In Source Control, write a message, press Commit, then Sync Changes. Your teacher’s feedback arrives as a pull request called Feedback.

Work through the Core exercises first (factorial, power, countDigits, sumArray, sumUpTo) before moving on to Extension (countMatches, isPalindrome, stringReverse, compute).

The full Codespace guide, with pictures

---

ဆက်စပ် ခေါင်းစဉ်များ

• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Methods: recursion ဆိုတာ သူ့ကိုယ်သူ ပြန်ခေါ်တဲ့ method ပါ (ဒီစာမျက်နှာမှာတော့ static method ပါ)
• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Iteration: ထပ်ခါထပ်ခါ လုပ်ရတဲ့ အလုပ်အတွက် recursion က loop ရဲ့ အစားထိုး နည်းလမ်းပါ
• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: 1D Arrays (တန်းတစ်တန်းတည်းမှာ စီထားတဲ့ ဒေတာအစု): recursive ဥပမာ အများအပြားက index parameter နဲ့ array ကို လျှောက်ကြည့်ပါတယ်
• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Strings: isPalindrome နဲ့ reverse လေ့ကျင့်ခန်းတွေမှာ charAt နဲ့ substring ကို သုံးပါတယ်
• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Stacks: call stack က တကယ့် stack တစ်ခု ဖြစ်ပြီး အဲဒီ stack ပြည့်သွားရင် StackOverflowError ဖြစ်ပါတယ်
• အရင် လေ့လာထားရမယ့် ခေါင်းစဉ်: Big-O Notation (algorithm ရဲ့ ကြာချိန် တိုးနှုန်းကို ပြတဲ့ သင်္ကေတ): branching recursion (Fibonacci O(2^n)) က iteration (O(n)) ထက် ဘာကြောင့် အများကြီး ပိုနှေးလဲ ဆိုတာ ရှင်းပြပေးပါတယ်
• ဆက်စပ် ခေါင်းစဉ်: Searching Algorithms (ရှာဖွေရေး algorithm များ): binary search ကို တဖြည်းဖြည်း ကျဉ်းလာတဲ့ (low, high) အပိုင်းနဲ့ recursion အဖြစ် ပြန်ရေးထားပါတယ်
• နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Quicksort: divide and conquer ရဲ့ အဓိက ဥပမာပါ။ Trace လုပ်ပြီး ဖော်ပြနိုင်ရုံပဲ လိုပြီး ကိုယ်တိုင် ရေးဖို့ မလိုပါဘူး
• နောက်ထပ် လေ့လာမယ့် ခေါင်းစဉ်: Binary Search Trees: insertion (ထည့်ခြင်း)၊ search (ရှာခြင်း) နဲ့ traversal အားလုံးက recursive ပုံစံအတိုင်း အလုပ်လုပ်ပါတယ်