Repetitive squaring (python) [closed]

Question

Closed. This question does not meet Stack Overflow guidelines. It is not currently accepting answers.

---

Questions asking for code must demonstrate a minimal understanding of the problem being solved. Include attempted solutions, why they didn't work, and the expected results. See also: Stack Overflow question checklist

Closed 8 years ago.

Improve this question

I implemented the exponentiation by squaring algorithm in Python

    (x,n)=(input(),input())

    def exp_itr(x,n):
        r=1
        while n!=0:
          if n%2==1:
            r=r*x
            n=n-1
          x=x*x
          n=n/2
    return r

And now, I need the recursive algorithm. How can I do it?

Answer 1

Here's a Python version of the pseudocode mentioned in comments

def exp(x, n):
    if n < 0:
        return exp(1 / x, -n)
    elif n == 0:
        return 1
    elif n == 1:
        return x
    elif n % 2 == 0:
        return exp(x * x, n / 2)
    else:
        return x * exp(x * x, (n - 1) / 2)