Recursion ও Divide and Conquer — ছোট নিজেকে ডাকা

লক্ষ্য: একই সূত্রের তিন implementation-এর call-count আর depth পাশে পাশে দাঁড় করানো — recursion-এর খরচ-মডেল হাতে-কলমে অনুভব।

def power_naive(x: float, n: int, ctr=None) -> float:
    """O(n) multiplications, depth O(n) — সোজাসাপ্টা"""
    if ctr: ctr.enter()
    try:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / power_naive(x, -n, ctr)
        return x * power_naive(x, n - 1, ctr)
    finally:
        if ctr: ctr.exit()


def power_divide(x: float, n: int, ctr=None) -> float:
    """O(log n) multiplications, depth O(log n) — fast exponentiation"""
    if ctr: ctr.enter()
    try:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / power_divide(x, -n, ctr)
        half = power_divide(x, n // 2, ctr)
        if n % 2 == 0:
            return half * half          # x^(2k)   = (x^k)^2
        return x * half * half          # x^(2k+1) = x·(x^k)^2
    finally:
        if ctr: ctr.exit()


def power_memo(x: float, n: int, ctr=None, _m={}) -> float:
    """divide-এর memo মেখানো রূপ — এখানে subproblem unique, তাই লাভ শূন্য"""
    if ctr: ctr.enter()
    try:
        if n == 0:
            return 1.0
        if n < 0:
            return 1.0 / power_memo(x, -n, ctr, _m)
        key = (x, n)                    # base-ভিত্তিক key — ভিন্ন x ভিন্ন ঘর!
        if key in _m:
            return _m[key]
        half = power_memo(x, n // 2, ctr, _m)
        r = half * half if n % 2 == 0 else x * half * half
        _m[key] = r
        return r
    finally:
        if ctr: ctr.exit()


class Counter:
    def __init__(self):
        self.calls = 0
        self.depth = 0
        self.cur = 0
    def enter(self):
        self.calls += 1
        self.cur += 1
        self.depth = max(self.depth, self.cur)
    def exit(self):
        self.cur -= 1


if __name__ == '__main__':
    # ---------- correctness ----------
    tests = [(2.0, 10), (3.0, 0), (5.0, 1), (2.0, 63), (-2.0, 7),
             (2.0, -3), (0.0, 5)]
    for x, n in tests:
        results = {name: fn(x, n) for name, fn in
                   [('naive', power_naive), ('divide', power_divide),
                    ('memo', power_memo)]}
        assert len({round(v, 9) for v in results.values()}) == 1, (x, n)
        print(f'{x}^{n:<3} = {results["divide"]:>12.4f}   (তিন সংস্করণ একমত)')

    # ---------- cost comparison ----------
    import sys
    sys.setrecursionlimit(2000)   # naive-এর depth 1025 — default 1000 ছাড়িয়ে যেত!
    print(f'\n{"version":<8} {"calls":>8} {"max_depth":>10}   n=1024')
    for name, fn in [('naive', power_naive), ('divide', power_divide),
                     ('memo', power_memo)]:
        c = Counter()
        fn(2.0, 1024, c)
        print(f'{name:<8} {c.calls:>8} {c.depth:>10}')

প্রত্যাশিত output:

2.0^10  =     1024.0000   (তিন সংস্করণ একমত)
3.0^0   =        1.0000   (তিন সংস্করণ একমত)
5.0^1   =        5.0000   (তিন সংস্করণ একমত)
2.0^63  = 9223372036854775808.0000   (তিন সংস্করণ একমত)
-2.0^7  =     -128.0000   (তিন সংস্করণ একমত)
2.0^-3  =        0.1250   (তিন সংস্করণ একমত)
0.0^5   =        0.0000   (তিন সংস্করণ একমত)

version     calls  max_depth   n=1024
naive        1025       1025
divide         12         12
memo           10         10

পড়ার বিষয়: naive-এর depth 1025 — Python default limit-এর ভয়ের জায়গা; divide-এর 11 — log₂(1024)+1। Memo এখানে কোনো লাভ দেখায় না, কারণ divide-chain-এ প্রতিটা subproblem একবারই আসে (unique chain: 1024 → 512 → 256 …) — memoization-এর শর্ত overlapping subproblems, যা এখানে নেই। এই negative result-টাই পরের লেসনের DP-র প্রবেশদ্বার।

নিজে বাড়ান:

১. Modular exponentiation (x^n) mod m-এ extend করুন — RSA-র মূল primitive, প্রতিটা গুণের পরে mod নিলে number ফুলে ওঠে না। ২. Iterative bitwise সংস্করণ (binary exponentiation, loop-এ) যোগ করুন — depth O(1), n-এর binary bits scan করে। ৩. Matrix exponentiation-এ generalize করে O(log n)-এ fibonacci বের করুন — পরের লেসনের DP-র সাথে তুলনার জন্য।