Help needed with lesson on recursion
Here are several approaches to compute $x^n$ from smaller powers of $x$:


doing $x \times x^{n-1}$. The former is $P(1)$ the latter is $P(n-1)$.
doing $x^2 \times x^{n-2}$. The former is $P(2)$, the latter $P(n-2)$.


But we don't need to use $P(1)$ and $P(2)$ at each step, right? we can use any $P(k)$ with $k&lt;n$. So how about,


doing $x^{n/2} \times x^{n/2}$?
(or in general $x^{k} \times x^{n-k}$)


Now, assume each multiplication takes $M$ time. Which approach is the fastest?



EDT after comments:

the main idea of recursion (somewhat similar to induction), is that we can "solve" some problem by using the solutions of smaller problems.

So $P(n)$ can be easily computed by $P(n/2) \times  P(n/2)$ (assuming $n$ is even and above 2). But how do we compute $P(n/2)$? well, that's the magic, the above idea works for any number $n$ and specifically also for the number $n/2$ (as long as it is even and above 2); So how do we compute $P(n/2)$? We recurse!


  $P(n/2)  = P( (n/2)/2) \times P( (n/2)/2) $


Why does it work? because eventually ((n/2)/2)...)/2 will be either 1 or 2, and this is $P(1)$ or $P(2)$ that we know how to solve.

To sum up, the recursion will look like this:

function P(n):
if n=1 or n=2  return ....
else
   if n is even, return P(n/2) * P(n/2)
   if n is odd, return  ..... (very similar)...


I leave you to work out the details.

This is of course the faster way. The slower way, but maybe simpler to understand, is to do the recursion step by step. The function in this case will look like:

function P(n):
if n=1 or n=2  return ....
else
   return P(n-1) * x


This one works for any number $n$ and returns $x^n$. The last line just instantiates the function again with a smaller parameter.