Skip to main content

Let’s talk about Recursion

16 min read
Data Structure Backtracking
#dsa #recursion #swift
Let’s talk about Recursion

Introduction

Recursion ကို မသိတဲ့သူတော့မရှိလောက်ပါဘူး။ ကျွန်တော် programming စလုပ်တုန်းက recursion သဘောတရားကို နားမလည်ခဲ့ဘူး recrusive call မြင်ရင်ကို ကြောက်တယ်ပေါ့နော်။ နောက်တော့မှ တော်တော်လေးအချိန်ယူပြီး မျက်လုံးထဲမြင်လာအောင် လေ့ကျင့်ယူရတာပေါ့။ နောက်လူတွေ ကျွန်တော့်လိုမဖြစ်အောင် recursion အကြောင်း တတ်နိုင်သလောက် အလွယ်ဆုံးဖြစ်အောင် ရှင်းပြပေးထားပါတယ်။

What is recursion?

Function တစ်ခုက ကိုယ့်ကိုယ်ကိုပြန်ခေါ်လိုက်ရင် recursion ဖြစ်ပါတယ်။ ပြောရရင်တော့ ဒီလိုပေါ့ဗျာ

func foo() {
  print("foo() called")
  foo() // calling itself, hence, recursion
}

အဲ့လို foo ဆိုတဲ့ function က ကိုယ့်ကိုယ်ကိုပြန်ခေါ်တော့ဘာဖြစ်သလဲဆိုတော့ print ထုတ်ထားတဲ့စာကြောင်းတွေ အဆက်မပြတ်ထွက်လာတာပေါ့။ Recursion မသုံးဘဲ အဆက်မပြတ်ထွက်အောင် ဘာလုပ်လို့ရလဲဆိုတော့ while နဲ့ loop ပတ်ရင်လည်း ထွက်တာပါ။

while true {
  print("yoo")
}

အဆက်မပြတ်မထုတ်ချင်ဘူး ၁ ကနေ ၅ ထိ အစဥ်လိုက်ထုတ်ချင်တယ်ဆိုပါစို့။ ဒါဆိုရင် for loop ကိုသုံးလို့ရတယ်။ While နဲ့လဲရပေမယ့်လို့ ဒီနေရာမှာ for နဲ့ပဲရေးပြပေးလိုက်ပါတယ်။

for i in 1 ... 5 {
  print(i) // Will print 1, 2, 3, 4, 5
}

အဲ့တာဆိုရင် loop ပတ်တဲ့ code တိုင်းကို recursion နဲ့အစားထိုးလို့ရတယ်လို့ နားလည်လို့ရပါတယ်။ အပေါ်က for loop ကို recursion နဲ့ ရေးကြည့်ရအောင်ပါ။

func foo(_ i: Int = 1) {
  if i > 5 { return }
  print(i)
  foo(i + 1)
}

foo()

Recursion

အပေါ်က code ကိုကြည့်ပြီး နာလည်ရခက်သွားလား? အဲ့တာဆိုရင်တော့ ဆက်ပြောမယ့်အပိုင်းကို သေသေချာချာလေး နားလည်အောင်အချိန်ယူပြီးသေချာဖတ်ပါ။

Function တွေကို execute လုပ်ဖို့ရာ ဘယ်နေရာမှာသိမ်းသလဲဆိုတော့ stack ထဲမှာသိမ်းပါတယ်။ Stack အကြောင်း ရှေ့ article မှာ ပြောပြီးပါပြီ။ Stack ဆိုတာ last-in-first-out (LIFO) ပါ။ နောက်ဆုံးထည့်တာ အရင်ထွက်ပါတယ်။

Function တွေကို stack ပေါ်ဘယ်လိုသိမ်းသလဲဆိုတာ မျက်စိထဲမြင်လာအောင် ကြည့်ကြည့်ရအောင်ပါ။

func a() {
  b()
  print("A")
}

func b() {
  c()
  print("B")
}

func c() {
  d()
  print("C")
}

func d() {
  print("D")
}

func main() {
  a()
}

အပေါ်က code မှာ main ဆိုတဲ့ function က entry point လို့ယူဆကြည့်ရအောင်ပါ။ အပေါ်က code ကို run ကြည့်ရင် console ထဲ ဘာထွက်လာမယ်ထင်ပါသလဲ? “ABCD” လား? အမှန်ကတော့ “DCBA” ဆိုပြီးထွက်လာမှာပါ။ ဘာကြောင့်လဲကြည့်ရအောင်ပါ။

ပထမဆုံး main က a ကိုခေါ်တဲ့အတွက် stack ထဲမှာ a ကိုအရင်ထည့်ပါတယ်။ ထည့်တယ်ဆိုတဲ့နေရာမှာ function တစ်ခုရဲ့ return address, parameter pass ပေးလိုက်ရင် ပေးလိုက်တဲ့ param/argument, function ထဲက local variable တွေ စတာတွေကိုပါ stack frame တစ်ခုအနေနဲ့ဆောက်ပြီး push ပေးလိုက်တာပါ။​ ရှေ့ဆက်ပြီးတော့ အလွယ် function name သီးသန့်ပဲရေးသွားပါမယ်။

main() is calling a()

|   |
+---+
| a | <- push a
+---+

a ထဲမှာက b ကို ခေါ်တယ် ပြီးမှ print “A” ဆိုတာကို ထုတ်တယ်။ Code တွေက line by line အလုပ်လုပ်တဲ့အတွက် print “A” တန်းထုတ်လို့မရသေးဘူး b ကိုအရင်ခေါ်ရဦးမယ်။ အဲ့တာဆို stack ထဲမှာဒီလိုဖြစ်သွားပါပြီ။

|   |
+---+
| b | <- push b
+---+
| a | TODO: print("A")
+---+

b ကလည်း c ကိုအရင်ခေါ်ထားတဲ့အတွက် function ခေါ်တိုင်း stack အပေါ် push ရပါတယ်။

|   |
+---+
| c | <- push c
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

c က d ကိုခေါ်တော့ ဒီလိုထပ်ဖြစ်သွားပါတယ်။

|   |
+---+
| d | <- push d
+---+
| c | TODO: print("C")
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

d ကိုရောက်တဲ့အခါမှာ တစ်ခြား function ကို ထပ်ခေါ်ထားတာမရှိတဲ့အတွက် stack ပေါ် push စရာမလိုပါဘူး။ d မှာဆုံးတဲ့အတွက် အရင်ဆုံး stack ရဲ့အပေါ်ဆုံး frame က စ pop လုပ်ပြီး execute လုပ်ပါတယ်။ အဲ့အခါ d ထဲက print(“D”) ကိုရောက်တဲ့အတွက် console ထဲကို “D” အရင်စ print ထွက်ပါတယ်။

> Pop d from stack, and execute

|   |
+---+
| c | TODO: print("C")
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
+---------------------------+

Stack ပေါ်မှာ c, b နဲ့ a ကျန်ပါတယ် အဲ့လို stack empty မဖြစ်မချင်း stack frame တစ်ခုစီကို pop လုပ်သွားတဲ့အခါ အခုလိုထွက်လာပါတယ်။

> Pop c from stack, and execute

|   |
+---+
| b | TODO: print("B")
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
+---------------------------+

> Pop b from stack, and execute

|   |
+---+
| a | TODO: print("A")
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
| B                         | 
+---------------------------+

> Pop a from stack, and execute

|   | 
|   | 
+---+

+---------------------------+
| </> Output                |
+---------------------------+
| D                         |
| C                         |
| B                         | 
| A                         |
+---------------------------+

“A” ကို print ထုတ်အပြီးမှာ နောက်ဆုံး stack က empty ဖြစ်သွားပြီးတော့ func a() ထဲမှာ print(“A”) အပြင် ထပ်မရှိတော့တဲ့အတွက် main function ထဲကြည့်မယ်ဆိုရင်လည်း a() ကလွဲပြီး ကျန်တာမရှိတော့တဲ့အတွက် ဒီမှာတင် program exit ဖြစ်သွားပါတယ်။

အပေါ်ကလို stack ပုံစံနဲ့ဆွဲကြည့်တာမျိုးကို recrusive stack လို့ခေါ်ပါတယ်။ Recursion ကိုနားလည်ဖို့ဆိုရင် မျက်စိထဲမြင်အောင်ပုံဖော်တဲ့ visualisation က တအားအရေးကြီးပါတယ်။ အခု article ကိုဖတ်နေရင်းနဲ့ recursive stack ကို လိုက်ဆွဲကြည့်ပါ။ Function တွေ stack ထဲတစ်ခုချင်းစီ push တာကနေ နောက်ဆုံးတစ်ခုစီပြန် pop တဲ့ထိ လက်နဲ့ချဆွဲပြီးနားလည်လားကြည့်ပါ။

Recursive stack ပြီးရင် recursive tree ကိုဆွဲကြည့်ကြပါမယ်။ Tree data structure ကိုသိထားရင် ပိုနားလည်ရလွယ်မှာဖြစ်ပေမယ့် tree က လည်း recursion ရမှ ပိုမြင်သာမှာမို့လို့ ကြက်ဥ ကြက်မ ပြသနာလိုတော့ဖြစ်နေပါတယ်။ ဒါပေမယ့် အတတ်နိုင်ဆုံး နားလည်လွယ်အောင်ရှင်းပြကြည့်ပါမယ်။ အပေါ်မှာဆွဲခဲ့တဲ့ recursive stack နဲ့ အခုဆက်ဆွဲကြမယ့် recursive tree ဆို တစ်ကယ်တော့ recursion သဘောတရားကို မြင်လာအောင် visualise လုပ်တဲ့ နည်းတွေဖြစ်ပါတယ်။

အပေါ်က stack frame ကို tree အနေနဲ့မြင်ကြည့်မယ်ဆိုရင် ပြောင်းပြန်ဖြစ်သွားပါမယ်။

  f(a)
  / 
f(b)
  \
  f(c)
  /
f(d)

Function a (notation အရ f(a) လို့ရေးပါမယ်) ကနေ f(b), f(b) to f(c), f(c) to f(d) သွားတဲ့ပုံစံကို tree ပုံစံ ရေးပြထားတာဖြစ်ပါတယ်။ နောက်ဆုံး f(d) မှာဆုံးတဲ့အချိန်ကျတော့မှ stack ပေါ်ကနေ တစ်ဆင့်ချင်းစီပြန် pop တာကို ဒီလိုမြင်ကြည့်လို့ရပါတယ်။

f(a)<----+ print("A")
  /      |
f(b)<----+ print("B")
  \      |
  f(c)<--+ print("C")
  /      |
f(d)-----+ print("D")

အောက်ဆုံး leaf node ကိုရောက်ပြီးတော့မှ parent ကို ပြန်တက်တာပါ။ ဒါကို backtracking လုပ်တယ်လို့ခေါ်ပါတယ်။ ဒီအပိုင်းကိုတော့ နောက်ပိုင်းမှာဆက်ပြောပါမယ်။

ဒီသဘောကိုမြင်တယ်ဆိုရင် ကျွန်တော် code ကိုနည်းနည်းပြောင်းပြီး စာမေးပွဲစစ်ကြည့်ပါမယ်။

func a() {
  print("A")  
  b()
}

func b() {
  print("B")
  c()
}

func c() {
  print("C")
  d()
}

func d() {
  print("D")
}

func main() {
  a()
}

အပေါ်က code ဆိုရင်ရော “ABCD” ထွက်မလား? “DCBA” ထွက်မလား? ဘာကြောင့်လဲ? ကိုယ့်ဘာသာ recursive stack ရော recursive tree ပါဆွဲပြီး dry run လုပ်ကြည့်ပါ။ မရသေးရင် code ကို copy ယူပြီး run ကြည့်ပါ။​ ပြီးရင် break point တွေထောက်ပြီး တစ်ဆင့်ချင်းစီလိုက်ကြည့်ပါ။

နောက်တစ်ခါ အပေါ်က foo ဆိုတဲ့ function ကိုလည်း recursive stack/tree ဆွဲပြီး လေ့ကျင့်ကြည့်ပါဦး။

ဒီလောက်ဆိုရင်တော့ recursion ကို နည်းနည်းလောက်တော့မျက်စိထဲမြင်လာပြီထင်ပါတယ်။

Recursion in Action

အရိုးရှင်းဆုံး recursion function တစ်ခုကိုရေးဖို့ လိုအပ်ချက် နှစ်ခုရှိပါတယ်။

Base case လို့ခေါ်တဲ့ ဘယ်အချိန်မှာ recursion ဆုံးမလဲဆိုတဲ့ case ရှိရပါမယ်။
ပြသနာတစ်ခုရှိရပါမယ်။ အဲ့ပြသနာကိုလည်း သေးသေးလေးတွေ စိတ်ပိုင်းပြီးဖြေရှင်းနိုင်ရပါမယ်။ (ဒါကို နားမလည်သေးရင် ခဏထားထားလိုက်ပါ)
အပေါ်က a, b, c, d ထုတ်တဲ့ function မှာဆိုရင် d ကိုရောက်တဲ့အခါမှာ recursion ဆုံးပါတယ်။ တစ်ခါ ၁ ကနေ ၅ အထိ ထုတ်တဲ့ foo function ကိုပြန်ကြည့်ပါ။

func foo(_ i: Int = 1) {
  if i > 5 { return }
  print(i)
  foo(i + 1)
}

ဒီ function မှာဆိုရင်လည်း if i > 5 { return } ဆိုတာက base case ဖြစ်ပါတယ်။ i က ၅ ထက်ကြီးတာနဲ့ တစ်နည်းပြောရရင် ၆, ၇ … ဖြစ်တာနဲ့ recursive stack ကပြီးသွားမှာဖြစ်ပြီးတော့ အပေါ်ဆုံး stack frame ကနေ pop လုပ်သွားမှာပါ။ Recursive function တစ်ခုမှာ base case မရှိရင်ဘာဖြစ်လဲဆိုတော့ stack overflow ဖြစ်ပါတယ်။ Coding problem တွေမေးကြဖြေကြတဲ့ forum ကိုပြောတာမဟုတ်ဘူးနော်။ Base case မရှိတော့ stack ပေါ်ကို function တွေအဆုံးအစမရှိ တင်နေရင်းနဲ့ ကွန်ပျူတာရဲ့ stack memory ပြည့်သွားတဲ့အတွက် stack frame တွေထပ်သိမ်းလို့မရတော့လို့ error တက်တာကို stack overflow လို့ခေါ်တာပါ။ Stackoverflow website ကလည်း အဲ့အသုံးအနှုန်းကနေ ဖြစ်လာတာပါ။

ပြသနာတစ်ခုကို သေးသေးလေးတွေ စိတ်ပိုင်းပြီးဖြေရှင်းနိုင်ရမယ်ဆိုတဲ့ အချက်ကို ဥပမာပုစ္ဆာနဲ့ ရှင်းကြည့်ပါမယ်။ Factorial ရှာတဲ့ပုစ္ဆာပါ။ Factorial ကို သင်္ချာ notation အရ (n!) လို့ရေးပါတယ်။ “n” ဆိုတဲ့နေရာမှာ natural number တွေဝင်ပါတယ်။ Factorial ရဲ့ formular ကတော့ အောက်ပါအတိုင်းဖြစ်ပါတယ်။

n! = n x (n - 1) x (n - 2) x ... 1

Factorial အကြောင်း အသေးစိတ်တော့မရှင်းပြတော့ပါဘူး။ သိချင်ရင် ရှာဖတ်ပါ။ လိုရင်းကိုဆက်သွားပါမယ်။ ဥပမာ five factorial (5!) ဆိုပါစို့။ အဲ့တာဆိုရင်

5! = 5 x 4 x 3 x 2 x 1
   = 120

ဆိုပြီးထွက်ပါတယ်။ အဲ့တော့ 5! ဆိုတာ 120 ပါ။​ အဲ့တော့ 5! ကို တစ်ခါတည်းအကုန်မစဥ်းစားဘဲနဲ့ ပြသနာသေးသေးလေးတွေ စိတ်ပိုင်းကြည့်ရင်

5! = 5 x 4!

လို့ မြင်လို့ရပါတယ်။ ကောင်းပြီ 4! ဆိုတာကလည်း

4! = 4 x 3!

ဖြစ်ပါတယ်။ ဒါဆိုရင် 5! ကို ပြသနာသေးသေးလေးတွေစိတ်ပိုင်းပြီး factorial ပြုတ်တဲ့အထိ ဆင့်ပွားကြည့်ရအောင်။

5! = 5 x 4!
     |   |
     |   4 x 3!
     |   |   |
     |   |   3 x 2!
     |   |   |   |
     |   |   |   2 x 1!
     |   |   |   |   |
     5 x 4 x 3 x 2 x 1

ဒီမှာ base case ဘယ်မှာဆုံးမှာလဲဆိုတာ ပြန်ပါလာပါပြီ။ Factorial သဘောတရားအရ 0! က 1 ပါ။ 1! ကလည်း 1 ပါ။ ဆိုတော့ f(n) ရဲ့ base case ကိုပြောပါဆိုရင် n == 0 || n == 1 လို့ပြောလို့ရပါတယ်။

ဒါဆိုရင် ကျွန်တော်တို့ factorial ရှာတဲ့ recursive function အတွက် လိုအပ်တဲ့အချက်နှစ်ချက်ထွက်ပါပြီ။

Function အခွံအရင်ရေးကြည့်ပါမယ်။

func factorial(of n: Int) -> Int {
}

Base case ကိုဆက်ရေးပါမယ်။ Recursive function တွေမှာ ဘာ logic မှမရေးခင် အမြဲ base case ကို ထိပ်ဆုံးကရေးပါမယ်။ ဒီအချက်အရေးကြီးပါတယ်။ သေချာမှတ်ပါ။ ကျန်တာက recursion က သူ့ဘာသာဆက်လုပ်သွားပါလိမ့်မယ်။

func factorial(of n: Int) -> Int {
  if n == 0 || n == 1 {
    return 1
  }
}

ပြသနာအကြီးကြီးကို ပြသနာသေးသေးလေးတွေ စိတ်ပိုင်းကြည့်တဲ့အခါ

n! = n x (n - 1)!

ဆိုတာကို သွားတွေ့ရပါတယ်။ ဒါကို recurrance relation လို့လည်းခေါ်ကြပါတယ်။ ဒါဆိုရင် အဲ့ formula ကို code အနေနဲ့ရေးကြည့်ရအောင်။

func factorial(of n: Int) -> Int {
  if n == 0 || n == 1 {
    return 1
  }
  
  return n * factorial(of: n - 1)
}

အပေါ်ကကောင်ကို run ကြည့်ရင် factorial ကို မှန်မှန်ကန်ကန်တွက်ပေးနိုင်တာကို တွေ့ရပါလိမ့်မယ်။

အပေါ်က factorial function ကို recursive tree ဆွဲကြည့်ပါမယ်။ Recursive stack ကိုတော့ ကိုယ့်ဘာသာဆွဲကြည့်ပါ။ ကျွန်တော့်အတွက် recursive tree က ပိုပြီးမျက်စိထဲမြင်လွယ်တဲ့အတွက် recursive tree ကိုပဲ နောက်ပိုင်းဆက်ဆွဲသွားပါမယ်။ 5! ကိုရှာတဲ့ recursive tree တစ်ခုဆွဲကြည့်ရအောင်။

              f(5) [n = 5]
               /
         5 * f(4)
                \
             4 * f(3)
                 /
             3 * f(2)
                  \
             2 * f(1)
                  /
                 1

f(1) ကိုရောက်တဲ့အခါမှာ base case ကိုရောက်သွားတဲ့အတွက် 1 ပြန်ပါတယ်။ အဲ့လိုကနေ အောက်ဆုံး resolve ဖြစ်သွားတဲ့ value ကနေ အပေါ်ကိုတစ်ဆင့်ချင်းတက်ပြီး မြှောက်သွားရင်းနဲ့ နောက်ဆုံး 5! ထွက်သွားပါတယ်။

ဒီပုစ္ဆာကိုနားလည်တယ်ဆိုရင် နောက်တစ်ခုဖြေရှင်းကြည့်ပါမယ်။

Fibonacci number ရှာတဲ့ပုစ္ဆာပါ။ ထုံးစံအတိုင်း တွက်ပုံတွက်နည်းကိုမသိရင်တော့ ကိုယ့်ဘာသာပြန်ဖတ်ပါ။ လွယ်ပါတယ်။ Formula က

let the nths fibonacci number be f(n),

f(n) = f(n - 1) + f(n - 2)

အဲ့တော့ ထားပါတော့ 5th fibonacci number ဆိုရင်

f(5) = f(4) + f(3)

ပေါ့။ အဲ့တာဆိုရင် base case စစဥ်းစားရအောင်, f(0) က 0, f(1) ကလည်း 0 ဆိုတော့ n က 0 ဒါမှမဟုတ် 1 ဖြစ်ခဲ့ရင် ကျွန်တော်တို့ n ကို return ပြန်ပေးလိုက်လို့ရတယ်။

ဒါဆို base case လေးပဲအရင်ရေးကြည့်ရအောင်။

func fib(of n: Int) -> Int {
  if n <= 1 { // n == 0 || n == 1
    return n
  }
}

ပြီးရင် သူ့ formula ကို ထည့်ပေးလိုက်ရင် ကိစ္စပြီးတာပါပဲ။ formula က f(n) = f(n — 1) + f(n-2) ဒါဆိုရင် ဒီလို return ပြန်လိုက်ရင်ရပါပြီ။

func fib(of n: Int) -> Int {
  if n <= 1 { // base case: n == 0 or n == 1
    return n
  }
  
  return fib(of: n - 1) + fib(of: n - 2)
}

ဒီ code ကို ကျွန်တော်တို့ ထုံးစံအတိုင်း recursive tree ဆွဲကြည့်ပါမယ်။​

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
    f(2) + f(1)
    / \
f(1) + f(0)

အပေါ်ကမှာ bold လုပ်ထားတဲ့ step တွေက လက်ရှိ calculate လုပ်နေတဲ့ node ကို ပြထားတာပါ။ ကျွန်တော်နဲ့အတူ ထိပ်ဆုံး f(5) ကနေစကြည့်ရအောင်။ f(5), n = 5, n က 1 ထက်ကြီးတဲ့အတွက် base case မရောက်သေးဘူး အဲ့တော့ f(4) + f(3) ဖြစ်တယ်။ ဒါပေမယ့် code က left to right ဖတ်တာဖြစ်တဲ့အတွက် ဘယ်ဘက်အစွန်ဆုံးက f(4) ကဘာလဲမသိသေးဘူး မသိတော့ ညာဘက်က f(3) ကျန်သေးတယ်နော် (ကျန်နေတာကို regular font နဲ့ပြထားတာ) ကျန်နေတာကိုခဏထား ဘယ်ဘက်က recursive function call ကိုဆက်ရှင်းရတယ်။ ဟုတ်ပြီ f(4) ကို ရှင်းတော့ f(3) + f(2) ဒီမှာလည်း f(2) နဲ့ပေါင်းဖို့အတွက် f(3) တန်ဖိုးမသိသေးဘူး မသိတော့ အောက်ဆက်ဆင်းရမယ် f(3) က f(2) + f(1), f(2) ကိုဆက်ရှင်းတော့ f(1) + f(0) ဒီမှာ base case ရောက်သွားတော့ f(1) = 1, f(0) = 0, အဲ့ကနေ f(2) တန်ဖိုးရတယ် ဒီလိုပေါ့

f(1) = 1
f(0) = 0
f(2) = f(1) + f(0)
     = 1 + 0
     = 1

အဲ့လို f(2) ရပြီဆိုရင် recursive tree က ဒီလိုဖြစ်သွားပြီ။

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
       1 + f(1)

ညာဘက်အခြမ်းက f(1) က base case ဆိုတော့ 1

ဒါဆိုရင် f(3) ရသွားပြီ

f(3) = 1 + f(1)
     = 1 + 1
     = 2

အဲ့လို f(3) ရပြီဆိုရင် recursive tree က ဒီလိုဖြစ်သွားပြီ။

              f(5)
              /  \
           f(4) + f(3)
            / \
           2 + f(2)

f(2) က base case မဟုတ်တော့ မသိသေးဘူး။ ကျွန်တော်တို့ကတော့ သိပြီပေါ့ အပေါ်မှာတွက်ထားပြီးသားဆိုတော့။ ဒါပေမယ့် code က မသိဘူး။ မသိတော့ ဒီလို branch ထပ်ခွဲရတယ်။

              f(5)
              /  \
           f(4) + f(3)
            / \
           2 + f(2)
               /  \
            f(1) + f(0)

အဲ့မှာ f(1) က base case ဆိုတော့ 1, f(0) က 0, အဲ့မှာ f(2) က 1 + 0 ဆိုတော့ 1

              f(5)
              /  \
           f(4) + f(3)
            / \
           2 + f(2)
                / \
               1 + 0

အဲ့လို f(2) ရပြီဆိုတော့ f(4) က

f(4) = 2 + f(2)
     = 2 + 1 + 0
     = 3

ဖြစ်သွားပြန်ရော။​ ဒါဆိုရင် recurisve tree က ဒီလိုဖြစ်လာပြီ။

              f(5)
              /  \
             3 + f(3)

အဲ့တော့ ဘယ်ဘက်က 3 ကသိပြီ ညာဘက်က သူနဲ့ပေါင်းမယ့် f(3) ကိုမသိနေဘူး ကျွန်တော်တို့ကတော့ သိပြီ ရှေ့မှာတွက်ပြီးသား computer က မသိဘူး မသိတော့ တစ်ခါ f(3)​ ကို ထပ်ပြီး branch ထပ်ခွဲရပြန်သဗျ။ အဲ့တာတော့ ရှည်လို့ မဆွဲပြတော့ဘူး။​ ဒီလောက်ဆိုမျက်စိထဲမြင်ပြီထင်ပါတယ်။ ဒါဆို f(3) က ဘယ်လောက်ရလဲဆိုတော့ 2, အဲ့တာဆို နောက်ဆုံး f(5) ကိုတွက်လို့ရပြီ ဒီလိုဖြစ်သွားမယ်။

              f(5)
              / \
             3 + 2

ဒါဆိုရင် 5th fibonacci number f(5) က 3 + 2 ဆိုတော့ 5 ရတာပေါ့။

ဒီ algorithm ကို optimisie လုပ်လို့ရတယ်။ f(2), f(3) ကို ရှေ့က ဘယ်ဘက်အစွန်ဆုံးက node တွေကို တွက်ခဲ့တဲ့အချိိန်တုန်းက အဖြေသိပြီးသားကို တဖြည်းဖြည်း ညာဘက်ရောက်လာတော့ ညာဘက်ကကောင်တွေမှာမှာ တွက်ပြီးသားကို အစကပြန်တွက်နေရတယ်။ အဲ့လိုကောင်မျိုးတွေကိုကျတော့ ကျွန်တော်တို့က cache ဖမ်းထားပြီး cache ထဲရှိရင် ရှိပြီးသားဟာပြန်ပြလိုက်တယ်။ Memorisation လို့ခေါ်တယ်။ ဒါကိုတော့ ဒီ article မှာ မပြောသေးဘူး။​ ဒီအတိုင်း ဗဟုသုတရအောင်ပြောပြတာ။

ဒီလောက်ဆိုရင် recursive logic တွေ ကိုယ့်ဘာသာမရေးတတ်ရင်တောင် recursion ဘယ်လိုဖြစ်နေလဲဆိုတာတော့ သဘောပေါက်လောက်ပြီလို့ထင်ပါတယ်။

Thinking in recursion

အပေါ်က ပုစ္ဆာနှစ်ပုဒ်ကို နားလည်ပြီဆိုရင်တော့ ကိုယ့်ဘာသာ recursion တွေ ဘယ်လိုရေးမလဲဆိုတာကို ဆက်ပြီးလေ့လာကြပါမယ်။

Recursion တစ်ခုဖြစ်ဖို့ အခြေခံလိုအပ်ချက်နှစ်ခုရှိတယ်လို့ အပေါ်မှာပြောခဲ့ပါတယ်။

  • Base case aka ဘယ်အချိန်မှာ recursion ပြီးမလဲ

  • ပြသနာကို ဘယ်လိုစိတ်ပိုင်းမလဲ ဘယ်လိုပြန် ပေါင်းပြီးအဖြေထုတ်မလဲ
    ဒီနှစ်ချက်အပြင် နောက်ထပ်နှစ်ချက်ကို ထပ်စဥ်းစားရပါမယ်။

  • ဘယ်လိုဟာမျိုးကို return ပြန်မလဲ

  • ဘယ်လိုဟာမျိုးကို parameter အနေနဲ့လက်ခံမလဲ/pass ပေးမလဲ
    အဲ့တော့ ဘယ်လိုဟာမျိုးကို return ပြန်မလဲဆိုတော့ intermediate value တစ်နည်းပြောရရင် child recursive frame ကနေ parent recursive frame ကို ပြန်ပေးချင်တဲ့ value မျိုးတွေကို return အနေနဲ့ပြန်ပါတယ်။ အပေါ်က Fibonacci ပုစ္ဆာကို ဥပမာအနေနဲ့ကြည့်ရအောင်ပါ။ Recursive tree ဆိုတဲ့အတိုင်း left, right node တွေလည်းရှိတော့ ပိုမြင်သာအောင်လို့ပါ။

              f(5)
              /  \
           f(4) + f(3)
            / \
        f(3) + f(2)
        / \
    f(2) + f(1)
    / \
f(1) + f(0)

အပေါ်က tree မှာ ကျွန်တော် bold လုပ်ပြထားတဲ့ နှစ်ကောင်သည် leaf node ပါ။ သူ့အောက်မှာ child node မရှိတာကို leaf node လို့ခေါ်ပါတယ်။ Recursive stack အရပြောမယ်ဆိုရင် stack ရဲ့ထိပ်ဆုံးကိုရောက်ပြီး ပြန် pop လုပ်ရမယ့်နေရာပါ။ ကောင်းပြီ ဒါဆိုရင် f(1) နဲ့ f(0) ရဲ့ parent node ကဘယ်သူလဲ? f(2) မဟုတ်ဘူးလား?​ အဲ့တာကြောင့်မို့လို့ f(2) ကို သူ့ရဲ့ child node aka child recursive frame ဖြစ်တဲ့ f(1) နဲ့ f(2) ကနေ သူတို့ value ကို ပြန်ပေးချင်တဲ့အတွက် return ကိုသုံးပါတယ်။ အဲ့လို f(1) နဲ့ f(2) ရဲ့ value နှစ်ခုကို return ပြန်ခြင်းအားဖြင့် f(5) ရဲ့ အဖြေတွက်ထုတ်လို့ရအောင် တစ်စိတ်တစ်ပိုင်း ကူညီတာဖြစ်ခြင်းကြောင့် ဒီလိုပြန်တဲ့ value ကို intermediate value လို့လည်းခေါ်ပါတယ်။

ဒီအထိရှင်းလားမသိဘူး။​ မရှင်းရင် သေသေချာချာလေးနှစ်ခါပြန်ဖတ်ပါ။ ဒီအပိုင်းလေးအရေးကြီးပါတယ်။ ဒုတိယအချက်ဖြစ်တဲ့ ဘယ်လိုဟာမျိုးကို parameter အနေနဲ့လက်ခံသလဲဆိုတာကို နောက်ဆက်ရှင်းပါမယ်။ အခုပထမအချက်ကိုသုံးပြီးတော့ ပုစ္ဆာတစ်ခု ထပ်တွက်ကြည့်ရအောင်ပါ။

Integer array တစ်ခုကို ပြောင်းပြန်လှန်တဲ့ code ကို recursion နဲ့ရေးပါမယ်။Array က [1, 2, 3, 4, 5] ဆိုရင် ကျွန်တော်တို့က [5, 4, 3, 2, 1] ဆိုပြီး ပြန်ရေးပါမယ်။

ပထမဆုံး base case စဥ်းစားပါမယ်။ ဘယ်အချိန်မှာရပ်မလဲ? Array index နောက်ဆုံးရောက်တဲ့အချိန်မှာရပ်ပါမယ်။

if arr.isEmpty { return }

ပြသနာကိုဘယ်လိုစိတ်ပိုင်းမလဲ? အလွယ်ကူဆုံးကတော့ Array ရဲ့ နောက်ဆုံး element တိုင်းကို drop လုပ်ပြီး rearrange လုပ်ရင် ဖြစ်နိုင်ပါတယ်။

reverse(arr) = [last element] + reverse(all elements except last)

f([1, 2, 3, 4]) = [4] + f([1, 2, 3])
                = [4] + [3] + f([1, 2])
                = [4] + [3] + [2] + f([1])
                = [4] + [3] + [2] + [1]
                = [4, 3, 2, 1]

ဒီလိုဆိုရင် base case နဲ့ recursion ကနေပြီးတော့ နောက်နှစ်ချက်ကိုထပ်စဥ်းစားမယ်။ Recursion ကနေ ဘယ်ဟာကို return ပြန်ပေးကြမလဲ? အပေါ်က function notation ကိုကြည့်ရင် intermediate value တွေ child ကနေ parent ကို merge လုပ်ဖို့ပြန်ပေးရမယ့် value တွေက int array ဖြစ်နေတယ်ဆိုတာကို တွေ့ရတယ်။ ဒါဆိုရင် int array ကို return ပြန်ပေးရမှာပေါ့။ အဲ့သုံးချက်ကို တစ်ဆင့်ချင်းစဥ်းစားပြီးတဲ့အခါ အခုလို recursive function ထွက်လာတယ်။

func reverseArray(_ arr: [Int]) -> [Int] {
  // base case
  if arr.isEmpty { return [] }  
  
  let element = arr.last!
  
  // recursive step
  return [element] + reverseArray(Array(arr.dropLast()))
}

Child က intermediate value ကို parent ကိုပြန်ပေးတာက ဒီနေရာပါ။

return [element] + reverseArray(Array(arr.dropLast()))

ပြန်ပေးလိုက်တဲ့ value ကို ပြန် merge လုပ်တာဆို​ရင် ဒါပါ။

return [element] + reverseArray(Array(arr.dropLast()))

အပေါ်က ရေးထားတဲ့ code ကို ကိုယ့်ဘာသာ recursive tree ဆွဲကြည့်ပါ။ ကျွန်တော်ပြောတဲ့ child -> parent value pass တာကို ပိုမြင်လာလိမ့်မယ်ထင်ပါတယ်။

ဒါလေးနားလည်ပြီဆိုရင် ဒုတိယစဥ်းစားရမယ့်အချက်ဖြစ်တဲ့ ဘယ်လိုအရာတွေကို parameter အနေနဲ့ လက်ခံမလဲ/pass မလဲဆိုတာကို ဒီ array reverse လုပ်တဲ့ပုစ္ဆာကိုတည်ပြီးတော့ပဲ ရှင်းပြပါမယ်။ ဒီတစ်ခါ array reverse လုပ်တဲ့ပုစ္ဆာကို ကန့်သတ်ချက်တစ်ခုထည့်ပါမယ်။ Reverse in-place လုပ်ရပါမယ်။ ဆိုလိုချင်တာက [element] + reverseArray(Array(arr.dropLast())) လိုမျိုး copy ယူပြီးမှ ပြန် merge တာမျိုး လုပ်လို့မရတော့ပါဘူး။ Original လာတဲ့ array ကို in-place reverse လုပ်ရမှာမျိုးပါ။

အဲ့တော့ ပထမအချက် base case က အပြောင်းအလဲရှိနိုင်သလားဆိုတာစဥ်းစားဖို့အတွက် ဒုတိယအချက်ကို အရင်တွေးကြည့်ပါမယ်။ ဒုတိယအချက် ဘယ်လိုပြသနာကို သေးသေးလေးတွေစိတ်ပိုင်းကြမလဲဆိုတာက အခက်ဆုံးအပိုင်းပါ။ ဒီဒုတိယအချက်ကိုတွေးနိုင်ရင် တတိယနဲ့ စတုတ္ထအချက်က ပိုလွယ်ပါတယ်။ ဒုတိယအချက်ရရင်ကို recursion ရေးလို့ရဖို့ တော်တော်နီးစပ်ပါပြီ။ အဲ့တော့ ဒီပုစ္ဆာမှာ array index နှစ်ခုကို in place swap လုပ်ဖို့လိုပါတယ်။ Swift ရဲ့ standard library မှာ swatAt(startIndex:endIndex) ဆိုတာ ရှိပါတယ်။ အဲ့တော့ ကျွန်တော်တို့က array ရဲ့ start index ကို ထိပ်ဆုံး (index 0) ကနေစပြီးတော့ end index ကို နောက်ဆုံး index (arr.count — 1) ကိုယူ ပြီးရင် သူတို့နှစ်ခုကို swap လုပ်၊ ပြီးတာနဲ့ start index ကို တစ်တိုး last index ကို တစ်လျှော့ ဒီလိုသွားမယ်ဆိုရင် ဖြစ်နိုင်စရာရှိပါတယ်။ ဒါဆိုရင် ဘယ်အချိန်မှာ base case ဖြစ်မလဲဆိုတော့ start index နဲ့ end index တူသွားရင် အလယ်ကိုရောက်သွားတာဖြစ်တဲ့အတွက် ဆက်ပြီး reverse လုပ်စရာမလိုပါဘူး။ နားလည်အောင် ပုံဆွဲပြပါမယ်။

let i = 0, j = arr.count - 1
[1, 2, 3, 4, 5]
 |           |           
 i           j           
                         
swap i and j
[5, 2, 3, 4, 1]          
 |           |           
 i           j           
                        
i += 1, j -= 1          
[5, 2, 3, 4, 1]         
    |     |             
    i     j             

swap i and j                        
[5, 4, 3, 2, 1]         
    |     |             
    i     j

i += 1, j -= 1
[5, 4, 3, 2, 1]         
       |  
       |             
      i,j

အဲ့တော့ base case ကို မြင်ပြီထင်ပါတယ်။ ဒါဆိုရင် ဘယ်ကောင်တွေကို parameter အနေနဲ့ယူမလဲ ကြည့်ရအောင်။ Start index i နဲ့ end index j ကို parameter အနေနဲ့ ယူထားဖို့လိုတယ်။ တစ်နည်းပြောရမယ်ဆိုရင် recursion မှန်မှန်ကန်ကန်အလုပ်လုပ်ဖို့အတွက် parent node (parent recursive stack frame) ကနေ child node (child recursive stack frame) ကို ပေးရမယ့် state ကို function parameter အနေနဲ့ ယူပါတယ်။ ပြောရမယ်ဆိုရင် recursion လုပ်တိုင်း လက်ရှိ parent frame ရဲ့ first index ကတော့ဘယ်လောက် last index ကတော့ဘယ်လောက်ဖြစ်သွားပြီ နောက်တစ်ခါ recursion ဖြစ်ရင် ဘယ်လိုဆိုတာမျိုးကို function parameter အနေနဲ့ထည့်ပေးရပါတယ်။ Function parameter အနေနဲ့မထည့်ပေးချင်ရင် function scope ရဲ့အပြင်မှာ variable အနေနဲ့လည်း ထိန်းလို့ရသေးတယ် ဒါကိုတော့ ဒီမှာမပြောတော့ဘူး။

ရှုပ်သွားလား။ ရှုပ်သွားရင် code ကိုကြည့်။

func reverseInPlace(_ arr: inout [Int], startIndex i: Int, endIndex j: Int) {
  if i >= j { return }
  arr.swapAt(i, j)
  reverseInPlace(&arr, i + 1, j - 1)
}

Swap လုပ်ပြီးတာနဲ့ start index pointer, end index pointer နှစ်ခုကို opposite direction ဆွဲခြုံလာတာ နောက်ဆုံး နှစ်ခု overlap ဖြစ်တဲ့အထိပဲ။ အဲ့တာကို recursive tree ရေးကြည့်ပါမယ်။

f(arr = [1, 2, 3, 4, 5], i = 0, j = 4)
 |
f(arr = [5, 2, 3, 4, 1], i = 1, j = 3)
 |
f(arr = [5, 4, 3, 2, 1], i = 2, j = 2)
 |
Now, it is base case, so pop the stack.
Since the function returns void by default, there is nothing to merge.
Array is now mutated in place by means of pass-by-reference (inout param in Swift).
Tree ဆိုပေမယ့်လို့ ဒီမှာ branch မခွဲရတော့ ဒီအတိုင်း single node ပဲဖြစ်နေတာပါ။

ဒါဆိုရင်တော့ recursive function ရေးဖို့အတွက် အခြေခံလိုအပ်ချက် နှစ်ချက်နဲ့ ဒီနှစ်ချက်အပေါ်မူတည်ပြီး ထပ်စဥ်းစားရမယ့်နှစ်ချက် ပေါင်းလေးချက်ကို နားလည်ပြီထင်ပါတယ်။​ စဥ်းစားတတ်ဖို့ကတော့ ဒီလို recursion နဲ့ပတ်သက်တဲ့ problem sets တွေ solution တွေ များများကြည့် များများလေ့လာ ကြည့်ရုံနဲ့ဒီအတိုင်းမနေဘဲ ကိုယ့်ဘာသာ recursive tree ချဆွဲကြည့် return ဘာကြောင့်ပြန်ရသလဲ ဘာကြောင့် parameter တွေ ထည့်ပေးရသလဲ ကိုယ့်ဘာသာမေးခွန်းထုတ်ကြည့် ဒီလိုလုပ်သွားရင် အချိန်တစ်ခုရောက်တဲ့အခါ ဒီသဘောတရားတွေက ကိုယ့်ခေါင်းထဲရောက်နေပြီး တစ်ခုခုဆို အလိုလိုထွက်လာပါလိမ့်မယ်။

ဒီလေးချက်လုံးကိုသုံးပြီး စဥ်းစားရမယ့်ပုစ္ဆာတစ်ပုဒ် ထပ်တွက်ကြည့်ပါမယ်။ ပေးထားတဲ့ string က palindrome ဟုတ်မဟုတ် စစ်တဲ့ပုစ္ဆာပါ။ Palindrome ဆိုတာ အတည့်ဖတ်ဖတ် ပြောင်းပြန်ဖတ်ဖတ် ဒီစာလုံးပဲထွက်တာကို palindrome လို့ခေါ်ပါတယ်။

func isPalindrome(_ str: String) -> Bool {
  fatalError("Unimplemented")
}

ဒါက code စရေးရမယ့် အခွံပါ။

ဥပမာ “hello” ရဲ့ပြောင်းပြန်က “olleh” ဖြစ်တဲ့အတွက် palindrome မဟုတ်ပါဘူး။ “madam” ဆိုရင်တော့ သူ့ပြောင်းပြန်လဲ “madam” ဖြစ်တဲ့အတွက် palindrome ဟုတ်ပါတယ်။

တစ်ကယ်လို့များ အင်တာဗျူးမှာ ဒီလိုမေးခွန်းလွယ်လွယ်လေးမျိုးမေးလာခဲ့ရင် တစ်ခုကြိုမေးထားရမှာက case sensitive လား case insensitive လားဆိုတာပါ။ ဒါမှမဟုတ်ရင် အကုန်လုံးက uppercase or lowercase နဲ့ချည်းပဲလာမှာလားဆိုတာ တစ်ခါတည်း clarify လုပ်ရပါမယ်။

ကဲ အဲ့တော့ ပထမ base case ကို စဥ်းစားဖို့အတွက် ဒုတိယ ဘယ်လို recursion လုပ်ကြမလဲဆိုတာကို စဥ်းစားရပါမယ်။ စဥ်းစားတတ်ရင် အပေါ်က array ကို ပြောင်းပြန်လှန်တဲ့ပုစ္ဆာနဲ့ဆင်ပါတယ်။ First index, last index ထားထားပြီး first index က char နဲ့ last index က char တူသလားစစ်ရမှာပါ။

ဒါဆိုရင် base case က first index နဲ့ last index overlap ဖြစ်တဲ့အချိန်ရပ်ရပါမယ်။ ဒါပေမယ့် တစ်ခုထပ်စဥ်းစားကြည့်ရအောင် တစ်ကယ်လို့များ first index နဲ့ last index က character နှစ်ခုကမတူခဲ့ဘူးဆိုရင် ဆက်ပြီးစစ်နေစရာမလိုတဲ့အတွက် တစ်ခါတည်းတန်းပြီး ရပ်လိုက်လို့ရပါတယ်။​ တစ်ခုမှားလည်းမှားတာပါပဲ။ ဥပမာ “motor”​ဆိုရင် “m” နဲ့ “r” မတူတဲ့အတွက် သူ့နောက်မှာ “o” နှစ်ခုတူပေမယ့် ဆက်မကြည့်ပါဘူး။ Invalid ဖြစ်ပါတယ်။

ဒါဆိုရင် base case လည်းရပြီ recursive logic လည်းရပြီဆိုတော့ တတိယအချက် return ပြန်စရာရှိရမလား ဆက်ကြည့်ပါမယ်။ ဆက်ကြည့်တဲ့အခါမှာ true/false return ပြန်လို့ရတာကိုသွားတွေ့ရပါတယ်။ ဘာကြောင့်လဲဆိုတော့ ပုစ္ဆာမှာလည်း bool return ပြန်ထားပြီး valid palindrome ဟုတ်မဟုတ် true/false နဲ့ သတ်မှတ်လို့ရလို့ဖြစ်ပါတယ်။ တစ်ကယ်လို့သာ true/false ပြန်ခိုင်းတဲ့ပုစ္ဆာမဟုတ်ရင် return ပြန်စရာလိုချင်မှလိုပါမယ်။

စတုတ္ထအချက် ဘာကို parameter အနေနဲ့လက်ခံရမလဲ စဥ်းစားကြည့်တော့ ကျွန်တော်တို့ array ကို ပြောင်းပြန်လှန်တုန်းကလို start index, end index ကို maintain လုပ်နေဖို့လိုပါတယ်။ တစ်နည်းပြောရရင် ကိုယ်က အခုဘယ် index တွေရောက်နေပြီလဲဆိုတာ သိရပါမယ်။

ဒီလေးချက်ကိုသိပြီဆိုရင် ဒီလို recursive code မျိုး ရေးလို့ရပါတယ်။

func isPalindrome(_ str: String) -> Bool {
  let chars = Array(str)
  return check(0, chars.count - 1)
}

// 4. Parameter i and j to get the parent recursive frame's state
private func check(_ i: Int, _ j: Int) -> Bool {
  // 1. Base case
  if i >= j { return true }
  if chars[i] != chars[j] { return false }
    
  // 2. Recursive logic and 3. return value
  return check(i + 1, j - 1)
}

အရင်ဆုံ String ကို char array ပြောင်းရပါတယ်။ ပြီးတော့ helper function အဖြစ် check ကိုထုတ်ရေးလိုက်ပါတယ်။ ဒါပါပဲ။ ဒါလေးကိုလည်း ကိုယ့်ဘာသာ recursive tree လေး ရေးကြည့်ပါဦး။

Outro

ဒီတစ်ခါမှာတော့ recursion နဲ့ပတ်သက်ပြီးတော့ သိဖို့လိုအပ်တာတွေကို အတတ်နိုင်ဆုံး နားလည်လွယ်အောင် ရှင်းပြပေးထားပါတယ်။ Recursion ကိုလေ့လာတဲ့အခါမှာ အပေါ်မှာပြောခဲ့သလို visualise လုပ်တတ်ဖို့ တအားအရေးကြီးပါတယ်။ မျက်စိထဲမြင်သွားရင်လည်း tree/graph traverse လုပ်တာတွေ back tracking တွေ permutation, combination, dynamic programming စတဲ့ ရှုပ်ထွေးသယောင်ထင်ရတဲ့ ပုစ္ဆာတွေကို ဖြေရှင်းတဲ့နေရာမှာ အများကြီးအသုံးတည့်ပါတယ်။ နောက်တစ်ပိုင်းကတော့ backtracking ဖြစ်ပါမယ်။

Until next time!