0
$\begingroup$

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.

  1. Since the game rules are that I can only use multiplication and subtraction operators, so how can I divide $X$?
  2. If I know that $N-I=2$, how can I solve $P2$ directly, it's $X \times X \times X$, meaning two multiplications?
  3. Is each $P$ a separate recursion?
$\endgroup$
  • 1
    $\begingroup$ @DavidRicherby I've already got my answer, but anyway I've updated my question. $\endgroup$ – Shimmy Aug 16 '15 at 13:20
2
$\begingroup$

Here are several approaches to compute $x^n$ from smaller powers of $x$:

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

  2. 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<n$. So how about,

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

$\endgroup$
  • $\begingroup$ Obviously the 3rd. But still I haven't figured out how it's clear from what I'm learning in the lecture, have you read 3.2 in it? Can you help me expand my fiddle to include what you said? Is each P a separate recursion? $\endgroup$ – Shimmy Aug 16 '15 at 2:24
  • $\begingroup$ Sorry, I'm not doing programming (this is not the purpose of this site; try Stack Overflow instead). But if you understand 3 is the fastest, try to program it. it should be very straightforward: check if $n=1$ or $2$. If not and $n$ is even just compute $P(n/2) * P(n/2)$. If it is odd, add another $x$ to the party. If you still have questions about the concepts of recursion - ask here. $\endgroup$ – Ran G. Aug 16 '15 at 2:28
  • $\begingroup$ In the beginning of the lecture, it defines the rules: "You may use only two operations: multiplication, subtraction.", so I'm not sure how to calculate $P(n/2)$. Please read that article section (3.2), I'm sure it won't take you long. I wanna focus on understanding the article literally, because it's part of an online CS course I'm taking step by step. I understand about not involving programming, that's fine. And BTW, is each $P$ a separate recursion? $\endgroup$ – Shimmy Aug 16 '15 at 2:32
  • 1
    $\begingroup$ Thanks for the suggestion of what I should do with my time. I changed the answer to give more details on the idea of recursion. I hope it helps. $\endgroup$ – Ran G. Aug 16 '15 at 2:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.