Recursive function simulating a number elevated to a power

Question

How to simulate the elevation of a number to a power using the recursion (and Python)?`

Answer 1

Knowing I have to use the recursion, the first thing to find is the base case. In this case, the base case is:

to⁰ = 1

as you probably already know about the math lessons. Where to is the basis.

What is the recursive step after all?

From the math lessons, we know that:

to^{n + 1} = toⁿ * to

or is our basis to high the power of n + 1 is equal to the same basis to raised to n, times our base to (I just translated it into words).

And how do we solve toⁿ?

Exactly, here comes the crucial point, where we apply the definition of recursion:

toⁿ = to^{n - 1} * to

And so on, applying successively to recursion to:

to^{n - 1}

I think you’ve figured out how to solve.

Translating in Python (in this case):

def power_r(base, power, show_steps=True):
    """show_steps serve só para dizer 
    se amostrar os passos recursivos escritos ou não."""
    if power == 0: # caso base
        if show_steps:
            print(base, "^{0} = 1", sep="")        
        return 1
    else: # passo recursivo
        if show_steps:
            print(base, "^{", power, "} = ", base, " * ", base, "^{", power - 1, "}", sep="")
        return base * power_r(base, power - 1, show_steps)

Trying now to apply this function:

print(power_r(4, 3))

using as a basis 4 and as a power 3, the result is:

4^{3} = 4 * 4^{2}
4^{2} = 4 * 4^{1}
4^{1} = 4 * 4^{0}
4^{0} = 1
64