# Complexity of iterative exponentiation

I've watched multiple videos and read articles about recursion but I'm still confused. I've got this problem here but I'm unsure how to answer it:

The following function calculates $$x^n$$ recursively. How many multiplications does the function make to calculate exp_rec(2, 64)?

def exp_rec(x, n):
if n==1:
return x
else:
p = exp_rec(n, x-1)
return x*p


Could someone help explain?

• Python-specific questions are off-topic here. – Yuval Filmus Sep 10 at 21:16

Alternatively, you can write a recurrence equation for the number of multiplications. Let us denote the number of multiplications when the argument is $$n$$ by $$M(n)$$. Then $$M(1) = 0$$ and $$M(n) = M(n-1) + 1$$ for $$n > 1$$. If you solve this recurrence, then you will be able to answer your question.