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
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
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
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
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.