# 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 '19 at 21:16

You are unsure how to answer the question.

When you are unsure: I method that does usually not work is trying to think about the problem very hard and waiting for inspiration. It doesn't come.

A method that works quite well is using pen and paper and trying it out. And you'll find that f (2, 64) calls f (64, 1) which doesn't make any further calls.

Now try f (10, 64) -> f (64, 9) -> f (9, 63) -> ... -> f (3, 57) -> f (57, 2) -> f (2, 56) -> f (56, 1). It should be easy to figure out the exact number of multiplications.

But then you need to check for the cases where the recursion doesn't end, and that is when we miss the test "n = 1" altogether because n < 1. If n < 1 then we call f (n, x-1). If x-1 < 1 as well then the recursion never ends. So that is the case when n < 1 and x ≤ 1.

PS. This function does not calculate x^n.

Here is an easy way to answer this kind of question. Modify the function so that it counts the number of multiplications it performs. This can be done in various ways, which I'll let you figure out.

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.

• Actually, this function doesn't calculate x^n. It is quite possible that the function he found in some article did, but this function doesn't. – gnasher729 Feb 9 at 9:14