Help needed with lesson on recursion I'm studying CS online, and I'm reading this lecture on recursion, see "3.2. A Mathematical Example".

I understood the beginning and I even made a program that calculates $X$ to the power of $N$ using recursion.

Reading on, I quote from the lesson's content:


  Find an algorithm for raising a number $X$ to the power $N$, where $N$ is a positive integer. You may use only two operations: multiplication, subtraction. We would like to multiply $N$ copies of $X$ all at once, but, like the piles of books, we do not have an operation that directly allows us to do that: we can only multiply two numbers at a time. In other words, the problems we can solve directly are these:
  
  Raise $X$ to the power $1$: answer = $X$.
  Raise $X$ to the power $2$: answer = $X \times X$.
  Any other problem we have to solve indirectly, by breaking it down into smaller and smaller problems until we have reduced it to one of these base cases.
  So, if $N &gt; 2$, we split the original problem into two subproblems:
  
  $P1$: raise $X$ to the power $I$. The answer to this is $S1$.
  $P2$: raise $X$ to the power $N-I$. The answer to this is $S2$.
  To get the final answer, $S$, combine $S1$ and $S2$: $S = S1 \times S2$.
  
  How do we solve $P1$ and $P2$? They are problems of exactly the same type as original problem, so we can apply to them exactly the same strategy that we applied to the original problem. We check to see if we can solve them directly... if $I=1$ or $I=2$ we can solve $P1$ directly; if $N-I=1$ or $N-I=2$ we can solve $P2$ directly. The problems we cannot solve directly, we solve recursively, as just described. An interesting feature of this strategy is that it works no matter how we split up $N$.


What I don't understand is, how I'm supposed to split it up into bigger chunks to achieve greater speed.  


Since the game rules are that I can only use multiplication and subtraction operators, so how can I divide $X$?
If I know that $N-I=2$, how can I solve $P2$ directly, it's $X \times X \times X$, meaning two multiplications?
Is each $P$ a separate 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.