পাইথনে রিকারসিভ ফাংশন তৈরি করার পদ্ধতি

রিকারসন (Recursion) হলো এমন প্রোগ্রামিং পদ্ধতি যেখানে একটি ফাংশন নিজে নিজে কল করে। প্রতিটি রিকারসিভ কল সমস্যাকে ছোট করে এবং একটি বেস কেস (Base Case)-এ পৌঁছায় যেখানে রিকারসন থামে।

উদাহরণ: প্রথম n সংখ্যার যোগফল

def sum_n(n):
    if n == 0:
        return 0          # বেস কেস
    else:
        return n + sum_n(n - 1)  # রিকারসিভ কেস

print(sum_n(100))   # 5050
print(sum_n(500))   # 125250

রিকারসিভ ফাংশনের কাঠামো

1. বেস কেস: রিকারসন থামানোর শর্ত (বাইনারি টার্মিনেশন)।
2. রিকারসিভ কেস: ফাংশন নিজে কল করে, সমস্যাকে সাব-প্রব্লেমে ভাগ করে।
3. প্রগ্রেশন: প্রতিটি কল বেস কেসের দিকে এগিয়ে যেতে হয়।

সতর্কতা: ইনফিনিট রিকারসন

def bad_recursion(n):
    return bad_recursion(n)  # বেস কেস নেই!

bad_recursion(1)  # RecursionError: maximum recursion depth exceeded

পাইথনের ডিফল্ট রিকারসন লিমিট ~১০০০ (sys.getrecursionlimit())।

অপ্টিমাইজেশন: টেইল রিকারসন (Python-এ অপ্টিমাইজ হয় না)

def sum_n_tail(n, acc=0):
    if n == 0:
        return acc
    return sum_n_tail(n - 1, acc + n)

পাইথন টেইল কল অপ্টিমাইজেশন (TCO) করে না, তাই স্ট্যাক ওভারফ্লো রিস্ক থাকে।

বিকল্প: memoization / iterative

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)