In this lesson, we will try to solve another problem using recursion and the problem is

that given two positive numbers - X and N, we want to calculate x to the power n and

x to the power n is nothing but n times x multiplied to itself.

So, there are n Xs, lets say in this expression and to calculate x to the power n, we perform,

if we simply keep on multiplying with x all the time, exactly n -1 multiplications.

And if we want to write a program to calculate x to the power n , the simplest thing that

comes to our mind is that we can start with a variable, say we want to start with a variable

result, initialize it to 1 and then we can simply run a loop from 1 to n and keep multiplying

result with x.

So, result becomes result*x.

In this case you are performing n multiplications because you are initiating the variable to

1 instead of x, but it also takes care of the condition when n is equal to 0 and as

we know x to the power 0 or any number to the power 0 is 1.

And as we can see for an input n, we are running the loop, we are running just one loop n times,

so it should be pretty evident that the time taken here in this particular case would be

proportional to n or we can also say that the time complexity of this algorithm would

be O(n).

Now, Albert and Pinto and two students of MyCodeSchool and they have been given the

assignment to calculate x to the power n using recursion.

So, once again Albert and Pinto come up with two different solutions and let us see what

their solutions are.

To solve a problem using recursion, we first need to define a recurrence relation or a

recursive definition.

So, Albert says that hey, x to the power n can be written as x*x^(n-1) and this is true

for all n greater than 0.

For n = 0, x to the power 0 is simply equal to 1.

So, x to the power n being equal to x into x to the power n-1 is a recurrence relation

because x^n is expressed in the form of x^(n-1) and this second condition is our base condition.

So, let us see what Albert's implementation is.

Albert writes a function Pow that takes two arguments - x and n and we are only writing

pseudo-code here and the function goes like - if n is 0, then simply return 1, else return

x into and we make a recursive call here to calculate x to the power n minus one.

So, we pass arguments x and n-1.

And this is Albert's implementation.

And this will work fine for all n greater than or equal to 0.

So, using this algorithm, if you want to calculate say x to the power 8, we make a recursive

call first to calculate x^7, and then x^7 goes on to make a recursive call to calculate

x^6.

And we keep on making recursive calls till X^0 and X^0 simply returns 1 and at this stage

the recursion terminates.

Now, let us see Pinto's solution.

And Pinto is a little smarter.

He says that x^n can be written as x^(n/2)* x^(n/2) if n is an even number.

And X^n is equal to x*x^(n-1) if n is odd.

And X^n is equal to 1 for the simple case or the base case of n = 0.

So, we kind of have 2 different recurrence relations for two different cases.

And let us see how the program looks like.

So, Pinto also writes a method Pow that takes two arguments x and n.

And his program also goes like if n is zero, then return 1, else if n is even and we can

also say , if n modulo 2 is 0, then first calculate x^(n/2) and then store it in a variable.

So let's say we have a variable y in which we store x^(n/2) by making a recursive call

to calculate x^(n/2).

So, this is a recursive call.

And we return y*y.

Now, instead of writing these 2 statements here, we could also have simply written that

return pow(x,n/2)* pow(x,n/2) but that would have been very bad because in that case, we

would make two different calls to calculate the same value which will be unnecessary redundancy.

So, if we would want to calculate x^8, we would make 2 calls to calculate x^4 and then

multiply them.

So, we make just one call and store it and then simply multiply it to calculate the square.

And finally,. if n is odd which will be our final condition, then we simply return x*x^(n-1)

and this also works fine for all n >= 0.

So, now when we want to calculate x^8, then we make a call to x^4 , so instead of reducing

this to x^7, we reduce the problem to calculate x^4 and further x^4 recursively makes a call

to calculate x^2 and then we go on like x^1 and x^0.

So, while Albert's program goes kind of nine steps here in this structure called the recursion

tree, Pinto's program only goes 5 steps in this recursion tree and if we analyze the

recurrence relation of these 2 algorithms, then Albert's algorithm , the time taken by

it is proportional to n or it is bi-oh of n or order of n in terms of time complexity

and Pinto's program is order of log of n in terms of time complexity.

How Albert's program is order of n algorithm and how Pinto's program is order of log n

algorithm is something that we will explain in another lesson, we will try to deduce it

mathematically, but as we can see that Pinto's program which is order of log n is lot more

efficient than Albert's program.

Now couple of things here.

When we are trying to calculate exponents, then in a real program, an integer variable

which is stored in 32 bits is able to store decimal numbers of only 9-10 digits while

x^n can be really really large.

So, lets for the sake of algorithmic understanding, assume that we have a machine where all this

storage and calculations, arithmetical calculations is not a problem.

So, this was exponentiation.

In another lesson, we will try to solve a very similar problem, modular exponentiation

and we will also mathematically deduce the time complexity of these recursive algorithms.