Recursion සිංහලෙන් | Functions, Call Stack, Base Case | SC Coding Guide

සෙට් එකට කොහොමද යාළුවනේ? අද අපි කතා කරන්න යන්නේ software engineering වල තියෙන ටිකක් සංකීර්ණ වගේ පෙනුනත්, හරි තේරුම් ගත්තොත් පුදුමාකාර විදියට ප්‍රශ්න විසඳන්න පුළුවන්, ඊටත් වඩා අපේ code එක ලස්සන කරන්න පුළුවන්, සුපිරි concept එකක් ගැන – ඒ තමයි Recursion.

Recursion කියන වචනේ ඇහුනම සමහර අයට 'අනේ මට මේක තේරෙන්නේ නෑ' කියලා හිතෙනවා ඇති. තවත් සමහර අයට 'මේක මොකටද?' කියලා හිතෙනවා ඇති. හැබැයි මේ post එක කියවලා ඉවර වෙනකොට ඔයාලට Recursion ගැන හොඳ අවබෝධයක් ලැබෙයි, ඒ වගේම ඔයාලාගේ programming skill එක තවත් අඩියක් ඉස්සරහට යයි කියලා මට විශ්වාසයි.

අපි මේක ටිකක් ලංකාවේ ස්ටයිල් එකට, සරලව තේරුම් ගමු. මොකද මේවා පොතේ තියෙන විදියටම ඉගෙන ගන්නවට වඩා, ප්‍රායෝගිකව තේරුම් අරගෙන use කරන එක තමයි වැදගත්.

Recursion කියන්නේ මොකද්ද? (What is Recursion?)

සරලවම කිව්වොත්, Recursion කියන්නේ තමන්වම නැවත නැවතත් කැඳවන function එකක් (A function that calls itself repeatedly). හිතන්නකෝ ඔයාලා ගෙදර කණ්නාඩි දෙකක් එකිනෙකට මුහුණලා තියෙන විදියට තිබ්බහම, අර රූපේ ගොඩක් දුරට යටට යටට යනවා වගේ පේනවා නේද? Recursion කියන්නෙත් එහෙම දෙයක්. එකම ප්‍රශ්නය නැවත නැවතත් පොඩි පොඩි කොටස් වලට කඩලා විසඳන ක්‍රමයක්.

ඕනෑම Recursive function එකකට ප්‍රධාන කොටස් දෙකක් අනිවාර්යයෙන්ම තියෙන්න ඕනේ:

Recursive Step (පුනරාවර්තී පියවර)

මේක තමයි function එක තමන්වම call කරගන්න තැන. හැබැයි මෙතනදී වැදගත්ම දේ තමයි, function එක තමන්වම call කරගන්නේ මුල් ප්‍රශ්නයට වඩා පොඩි, සරල කොටසක් විසඳන්න. හැම recursive call එකක්ම base case එකට ලං වෙන විදියට යොමු වෙන්න ඕනේ.

Base Case (මූලික අවස්ථාව)

මේක තමයි recursion එක නතර වෙන තැන. මේක නැත්නම් ඉවරයි! අනන්ත loop එකක් (infinite loop) වගේ, function එක දිගටම call වෙවී ගිහින් crash වෙනවා. මේක තමයි අපේ recursive problem එකේ තියෙන සරලම, කෙලින්ම විසඳන්න පුළුවන්ම කොටස.

ඔන්න ඔය දෙක තමයි Recursion වලට තියෙන මූලිකම දේවල්.

ප්‍රායෝගික උදාහරණ (Practical Examples)

දැන් අපි මේක practical විදියට බලමු. මේවා ලියන්න වෙනත් ක්‍රම තිබුණත්, අපි recursion වලින් ලියන විදිය බලමු.

Factorial (ක්‍රමාරෝපිතය)

Factorial කියන්නේ ගණිතයේදී ගොඩක් use වෙන දෙයක්. උදාහරණයක් විදියට, 5! කියන්නේ 5 * 4 * 3 * 2 * 1 = 120. මේක recursion වලින් කොහොමද ලියන්නේ කියලා බලමු. මේකේ තියෙන මූලික රීතිය තමයි n! = n * (n-1)! කියන එක.

• Base Case: 0! = 1. මේක තමයි අපේ නවතින්න තියෙන තැන.
• Recursive Step: n * factorial(n - 1). මෙතනදී අපි n කියන අගය අරගෙන, ඒක (n-1) වල factorial එකෙන් වැඩි කරනවා.

def factorial(n):
    # Base Case
    if n == 0 or n == 1: # 0! is 1, and 1! is 1
        return 1
    # Recursive Step
    else:
        return n * factorial(n - 1)

# Test the function
print(f"5! = {factorial(5)}")   # Output: 5! = 120
print(f"0! = {factorial(0)}")   # Output: 0! = 1
print(f"7! = {factorial(7)}")   # Output: 7! = 5040

මේක වැඩ කරන විදිය ටිකක් හිතන්න. අපි factorial(5) කියලා call කරාම:

• factorial(5) -> 5 * factorial(4)
• factorial(4) -> 4 * factorial(3)
• factorial(3) -> 3 * factorial(2)
• factorial(2) -> 2 * factorial(1)
• factorial(1) -> 1 (මෙතනදී base case එකට එනවා, recursion එක නවතිනවා)

දැන් මේ return වෙච්ච අගයන් ආපස්සට යනවා:

• 2 * 1 = 2
• 3 * 2 = 6
• 4 * 6 = 24
• 5 * 24 = 120

පැහැදිලියි නේද?

Fibonacci Sequence (ෆිබොනාච්චි අනුක්‍රමය)

Fibonacci sequence කියන්නේත් ගණිතයේ ගොඩක් ජනප්‍රිය දෙයක්. මේකේ හැම අංකයක්ම හැදෙන්නේ කලින් අංක දෙකේ එකතුවෙන්. උදාහරණය: 0, 1, 1, 2, 3, 5, 8, 13, ....

• Base Cases: F(0) = 0 සහ F(1) = 1. මේවා තමයි අපේ මුල්ම අගයන්.
• Recursive Step: F(n) = F(n-1) + F(n-2). මෙතනදී function එක තමන්වම දෙපාරක් call කරනවා.

def fibonacci(n):
    # Base Cases
    if n <= 1:
        return n
    # Recursive Step
    else:
        return fibonacci(n - 1) + fibonacci(n - 2)

# Test the function
print(f"Fibonacci(0): {fibonacci(0)}") # Output: 0
print(f"Fibonacci(1): {fibonacci(1)}") # Output: 1
print(f"Fibonacci(7): {fibonacci(7)}") # Output: 13 (0, 1, 1, 2, 3, 5, 8, 13)

මේ Fibonacci උදාහරණය recursion වලින් ලියන්න පුළුවන් වුණාට, මේකේ පොඩි ගැටලුවක් තියෙනවා. ඒ තමයි performance එක. fibonacci(5) call කරනකොට fibonacci(3) දෙපාරක් ගණනය කරනවා. fibonacci(4) සහ fibonacci(3) දෙකම call කරනකොට ඒ දෙක ඇතුලෙම fibonacci(2), fibonacci(1) වගේ දේවල් නැවත නැවත ගණනය කරනවා. මේක විශාල n අගයක් දුන්නොත් ගොඩක් වෙලා යන වැඩක්. මේකට විසඳුම් විදියට Memoization (කලින් ගණනය කරපු අගයන් save කරගෙන use කරන එක) වගේ දේවල් use කරන්න පුළුවන්. ඒ ගැන අපි පස්සේ කතා කරමු.

Call Stack සහ RecursionError (Call Stack and RecursionError)

දැන් අපි බලමු මේ recursion කියන එක computer එක ඇතුලේ කොහොමද වැඩ කරන්නේ කියලා. හැම function call එකක්ම, ඒවායේ තියෙන variables වගේ දේවල් save වෙන්නේ Call Stack කියලා එකක.

Call Stack

Call Stack එක හිතන්න පොත් ගොඩක් උඩින් උඩට තියනවා වගේ. මුලින්ම තියන පොත උඩටම ගන්න බෑ, උඩින්ම තියෙන පොත තමයි ඉස්සෙල්ලාම අයින් කරන්න වෙන්නේ. මේකට කියන්නේ LIFO (Last In, First Out) කියලා. ඒ කියන්නේ අන්තිමට stack එකට ආපු එක තමයි මුලින්ම එළියට යන්නේ.

Recursive function එකක් call වෙන හැම වෙලාවෙම, ඒ function call එකට අදාළ තොරතුරු (parameters, local variables, return address) අලුත් “stack frame” එකක් විදියට call stack එකට එකතු වෙනවා. Base case එකට reach වෙලා function එක return වෙනකොට, ඒ stack frame එක call stack එකෙන් අයින් වෙනවා. මේක හැම stack frame එකක්ම ඉවර වෙනකම් සිද්ධ වෙනවා.

RecursionError (Stack Overflow)

දැන් මේ call stack එකට දරාගන්න බැරි තරම් function calls ගානක් එකතු වුණාම, ඒ කියන්නේ stack එක පිරිලා ඉතිරිලා ගියාම තමයි අපිට RecursionError කියන error එක එන්නේ. Python වල මේකට RecursionError: maximum recursion depth exceeded කියලා පණිවිඩයක් එනවා. මේකට පොදුවේ Stack Overflow කියලා කියනවා.

මේක වෙන්නේ ඇයි?

1. Base Case එකක් නැති වුණාම: අපි මුලින්ම කිව්වා වගේ base case එකක් නැත්නම්, function එක අනන්තවම call වෙනවා. Stack එකට calls එකතු වෙවී ගිහින් stack overflow වෙනවා.
2. Base Case එකට කවදාවත් නොපැමිණීම: සමහර වෙලාවට base case එක තියෙන්න පුළුවන්, හැබැයි recursive step එක ලියලා තියෙන්නේ base case එකට කවදාවත් ළඟා නොවෙන විදියට. උදාහරණයක් විදියට, factorial(n + 1) කියලා call කරොත්. මේකත්無限 loop එකක් වගේ.
3. Call stack එකේ උපරිම සීමාවට ළඟා වීම: හැම programming language එකකම call stack එකට තියෙන limit එකක් තියෙනවා (default recursion depth). Python වල මේක සාමාන්‍යයෙන් 1000ක් විතර. ඒ සීමාවට වඩා call ගානක් ගියොත් error එක එනවා.

කොහොමද මේක හොයාගන්නේ සහ හදාගන්නේ?

• Base Case එක හරිද කියලා බලන්න: මේක තමයි මුලින්ම බලන්න ඕනේ දේ. Base case එක පැහැදිලිව තියෙනවද? ඒක නිවැරදිව වැඩ කරනවද?
• Recursive step එකෙන් හැම වෙලේම base case එකට ළඟා වෙනවද කියලා බලන්න: recursive call එක හැම වෙලේම ප්‍රශ්නය පොඩි කරලා base case එක දෙසට යනවාද කියලා බලන්න. n අගය හැම වෙලේම අඩු වෙනවද වගේ.
• ප්‍රශ්නය recursion වලින් විසඳන්නම ඕනද කියලා බලන්න: සමහර වෙලාවට recursion වලින් විසඳන එකේ වාසි අඩුයි. සරල loop එකකින් (iterative approach) විසඳන්න පුළුවන් නම් ඒක තමයි වඩාත් හොඳ.

හොඳම පුරුදු සහ කවදා භාවිතා කරන්නද? (Best Practices & When to Use?)

දැන් ඔයාලට Recursion ගැන හොඳ අදහසක් ඇති. හැබැයි හැම තැනම මේක use කරන්න බෑ. හරියට තැනට use කරන එක තමයි වැදගත්.

කවදා භාවිතා කරන්නද?

Recursion use කරන්න හොඳම අවස්ථා කීපයක් තියෙනවා:

• ගැටලුව ස්වභාවයෙන්ම recursive නම්: උදාහරණයක් විදියට, ගස් ව්‍යූහයක් (Tree Data Structure) හෝ ප්‍රස්තාරයක් (Graph) traverse කරනකොට (ගමන් කරනකොට). මේ වගේ දේවල් වලට recursion ස්වභාවිකවම ගැලපෙනවා. Folder structure එකක් scan කරනකොටත් recursion use කරන්න පුළුවන්.
• Recursion නිසා code එක කියවන්න ලේසි වෙනවා නම්, සරල වෙනවා නම්: සමහර ගැටලු iterative loop එකකින් ලියනවට වඩා recursive විදියට ලිව්වම code එක ගොඩක් සරලයි, කියවන්න ලේසියි.
• Divide and Conquer Algorithms: Merge Sort, Quick Sort වගේ algorithms වලදී ප්‍රශ්නය පොඩි කොටස් වලට කඩලා විසඳනවා. මේවාට recursion හොඳටම ගැලපෙනවා.

කවදා භාවිතා නොකරන්නද?

Recursion use නොකර ඉන්න හොඳ අවස්ථාත් තියෙනවා:

• සරල loop එකකින් විසඳන්න පුළුවන් ප්‍රශ්න වලට: උදාහරණයක් විදියට 1 සිට 100 දක්වා එකතු කරන එක. මේකට recursive function එකක් ලියනවට වඩා for loop එකක් ලියන එක ගොඩක් හොඳයි, performance අතින් වගේම readabilty අතින්.
• Performance critical අවස්ථාවලදී: Recursion වලදී හැම function call එකකටම පොඩි overhead එකක් තියෙනවා (function call එකක් memory එකට add කරන, remove කරන process එක). ඒ වගේම call stack එකේ memory එකක් අවශ්‍යයි. ඒ නිසා ඉතා විශාල calls ප්‍රමාණයක් තියෙන අවස්ථාවලදී, හෝ performance ගොඩක් වැදගත් අවස්ථාවලදී iterative solution එකක් හොඳ වෙන්න පුළුවන්.

හොඳම පුරුදු (Best Practices):

• හැම විටම පැහැදිලි Base Case එකක් තියන්න: මේක තමයි recursion වල ජීවය. මේක නැත්නම් කිසි දෙයක් වැඩ කරන්නේ නෑ.
• Recursive call එකෙන් ප්‍රශ්නය කුඩා කොටසකට කඩා Base Case එක දෙසට ගමන් කරන බවට වග බලා ගන්න: හැම recursive call එකකින්ම ප්‍රශ්නය පොඩි වෙන්න ඕනේ, එහෙම නැත්නම් infinite loop එකක් හැදෙනවා.
• Memoization / Caching ගැන හිතන්න: විශේෂයෙන්ම Fibonacci වගේ problems වලට, කලින් ගණනය කරපු අගයන් save කරගෙන නැවත ගණනය නොකර ඉන්න පුළුවන් නම්, performance එක ගොඩක් වැඩි කරගන්න පුළුවන්. මේක Dynamic Programming වලදී ගොඩක් use කරන දෙයක්.

Conclusion

ඉතින් යාළුවනේ, recursion කියන්නේ සංකීර්ණ වගේ පෙනුනත්, හරි තේරුම් ගත්තොත් සුපිරි power tool එකක්. Tree structure, Graph algorithms වගේ දේවල් වලදී මේක නැතුවම බෑ. මුලින් ටිකක් අමාරු වගේ දැනෙයි, හැබැයි practice කරනකොට ලේසි වෙයි. ගොඩක් ප්‍රශ්න වලට recursion විසඳුම සරල විදියට ඉදිරිපත් කරන්න උදව් වෙනවා.

මතක තියාගන්න: "Base Case එක හොඳට තේරුම් ගන්න!" ඒක තමයි ඔයාලාගේ recursive function එක බේරගන්නේ.

ඔයාලට මේ post එක ගැන මොනවා හරි අදහස් තියෙනවා නම්, මේ ගැන තව දැනගන්න ඕන නම්, නැත්නම් ඔයාලා use කරපු සුපිරි recursive examples තියෙනවා නම්, පහළ තියෙන comment section එකේ කියන්න. තව මොන වගේ topics ගැනද දැනගන්න ඕන? අපි ඒ ගැනත් කතා කරමු!

හැමෝටම සුභ දවසක්!