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
        p = exp_rec(n, x-1)
        return x*p

Could someone help explain?

  • 1
    $\begingroup$ Python-specific questions are off-topic here. $\endgroup$ – Yuval Filmus Sep 10 at 21:16

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.