Recursion အခြေခံ

နားလည်ထားရမယ့် အချက်

Recursion ဟာ ပြဿနာတစ်ခုကို အတူတူပဲဖြစ်တဲ့ ပြဿနာအငယ်စား version တစ်ခုအဖြစ် ခွဲထုတ်ပြီး function ကိုယ်တိုင်ကို ခေါ်ပြီး အဲဒီ အငယ်စား piece ကို ဖြေရှင်းစေတာဖြင့် problem ကို ဖြေရှင်းပါတယ်။ recursive function မှန်ကန်တိုင်းမှာ အစိတ်အပိုင်းနှစ်ခု လိုအပ်ပါတယ် — base case, function က ထပ်ပြီး recurse မလုပ်ဘဲ တိုက်ရိုက်ဖြေနိုင်တဲ့ input အငယ်ဆုံး, နှင့် recursive case, ကိုယ်တိုင် input ငယ်တစ်ခုပေါ် ကိုယ်တိုင်ခေါ်ပြီး ရလာတဲ့ result ကို လက်ရှိ step ရဲ့ work နဲ့ ပေါင်းစပ်တဲ့နေရာ။ factorial(n) ကို ကြည့်ပါ — base case က factorial(0) = 1 ဖြစ်ပြီး နောက်ထပ် call လုပ်စရာမလိုဘဲ ချက်ချင်းဖြေပေးပါတယ်; recursive case က n > 0 အတွက် factorial(n) = n * factorial(n - 1) ဖြစ်ပါတယ်။ factorial(3) ကို ခေါ်လိုက်တာဟာ ချက်ချင်း answer မတွက်ပါဘူး — factorial(2) ကို ခေါ်ပြီး, ဒါက factorial(1) ကို ခေါ်ပြီး, ဒါက factorial(0) ကို ခေါ်ပါတယ်, call အသစ်တစ်ခုစီက caller ကို ခဏရပ်ပြီး call stack ပေါ်ကို frame အသစ်တစ်ခု push လုပ်ပါတယ်။ factorial(0) က 1 ကို return ပြန်တာနှင့် အဲဒီ answer ဟာ အပေါ်ကို ပြန်စီးဆင်းလာပါတယ် — factorial(1) က 1*1=1 return, factorial(2) က 2*1=2 return, factorial(3) က 3*2=6 return — stack ဟာ တက်လာတဲ့ order ကို ပြောင်းပြန်အတိအကျ unwind ဖြစ်သွားပါတယ်။ base case မရှိရင်, မှားနေရင်, (သို့) ဘယ်တော့မှ မရောက်ရင် (ဥပမာ ဆန့်ကျင်ဘက် direction ရေတွက်ခြင်း), call တွေဟာ frame အသစ်တွေကို ဆက်ပြီး push လုပ်နေမှာဖြစ်ပြီး call stack ကုန်သွားကာ stack overflow နှင့် crash ဖြစ်သွားပါလိမ့်မယ်။

လက်တွေ့ scenario နဲ့ ချိတ်ကြည့်မယ်

Tutorial Platform ရဲ့ course content ဟာ သဘာဝအတိုင်း nested ဖြစ်ပါတယ် — course တစ်ခုမှာ chapter တွေပါပြီး chapter တစ်ခုစီမှာ lesson တွေ ပါပါတယ် — ဒါဟာ recursion အတွက် တိကျစွာ ဒီဇိုင်းပုံသဏ္ဍာန်ပါပဲ။ table of contents ကို render လုပ်တဲ့ function တစ်ခု, (သို့) lesson တစ်ခုရဲ့ prerequisite chain ကို 'learner က ဒီ lesson မတိုင်ခင် လိုအပ်တာအားလုံး ပြီးမြောက်ပြီလား' ဆိုတာ စစ်ဆေးဖို့ walk လုပ်တဲ့ function တစ်ခုဟာ chapter (သို့) prerequisite တစ်ခုကို course တစ်ခုလုံးကို process လုပ်သလိုပဲ ကိုင်တွယ်နိုင်ပါတယ် — case အငယ်ဆုံး (prerequisite မရှိတဲ့ lesson တစ်ခုတည်း) ကို တိုက်ရိုက်ဖြေပြီး ပိုကြီးတာအားလုံးကို sub-part တွေပေါ် recursive call တစ်ခုကို လွှဲအပ်ပါတယ်။ base case ကို ဒီနေရာမှာ မှန်ကန်စွာ ရေးထားခြင်းဟာ lesson နှစ်ခု တစ်ခုနှင့်တစ်ခု ကိုးကားနေရင် (circular) prerequisite check ဟာ ထာဝရ loop မဖြစ်အောင် တားဆီးပေးတဲ့ အချက်ပါပဲ။

• recursive function တိုင်းမှာ base case (recurse ရပ်ခြင်း) နှင့် recursive case (input ငယ်ပေါ် ကိုယ်တိုင်ခေါ်ခြင်း) နှစ်ခုစလုံး လိုအပ်သည်
• recursive call တစ်ခုစီသည် call stack ပေါ် frame အသစ်ကို push လုပ်ပြီး result များသည် call return ပြန်တာနှင့်အမျှ ပြောင်းပြန် order ဖြင့် ပြန်စီးဆင်းလာသည်
• base case မှားယွင်း၊ မရှိ၊ (သို့) ဘယ်တော့မှ မရောက်ခြင်းသည် infinite recursion နှင့် stack overflow crash ကို ဖြစ်စေသည်

အတူတူ စမ်းရေးကြည့်မယ်

def factorial(n):
    # Base case: smallest input, answered directly, no further recursion
    if n == 0:
        return 1
    # Recursive case: solve a smaller subproblem, then combine with current step
    return n * factorial(n - 1)

# Trace for factorial(3):
#   factorial(3) -> 3 * factorial(2)
#     factorial(2) -> 2 * factorial(1)
#       factorial(1) -> 1 * factorial(0)
#         factorial(0) -> 1                (base case reached, stack starts unwinding)
#       factorial(1) returns 1 * 1 = 1
#     factorial(2) returns 2 * 1 = 2
#   factorial(3) returns 3 * 2 = 6
print('factorial(3) =', factorial(3))

comment ထဲက trace လုပ်ထားတဲ့ call stack နှင့် ကိုက်ညီစွာ 'factorial(3) = 6' ကို print ထုတ်သည် — nested call လေးခု factorial(0) အထိ တက်သွားပြီး result များ (1, 1, 2, 6) ပြန်စီးဆင်းလာသည်။

Wikipedia — Recursion (computer science) — Data Structures & Algorithms