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