Q: Just my 2 cents but I think the algorithm can be simplier : ``` var power = function(x,n) { if(n === 0) { return 1; } if(n < 0) { return 1 / (power(x, abs(n))); //Make sure it's float AND abs } return x * power(x, n-1); } ``` (Check Cameron answer) There's no need for this odd / even thing or does it make the algorithm faster? I can't get why then... As far as I can tell my algorithm works. Actually, by the Big Theta theory it's seems to me that both my algorithm and the challenge are Θ(n). Still, I do understand that it's dividing the recursive call by 2 when is even, which is pretty smart.

For convenience, let's call the algorithm that you have proposed Algorithm A, and the algorithm proposed in the article Algorithm B. Algorithm A is O(n) while Algorithm B is, in fact, O( log(n) ). This makes a big difference if n is large. The difference between Algorithm A and Algorithm B are analogous to the differences between linear search and binary search. Algorithm A and linear search only reduce the size of their problem by 1 after each iteration/recursion. On the other hand, Algorithm B and binary search, roughly speaking, reduce the size of their problem in half each iteration/recursion. But Algorithm B doesn't always reduce its problem size in half. It only reduces it in half when n is even. So how can we claim that is O(log(n)) ? If n was a power of 2 then we would halve the problem every recursion. It would take: log(n) multiplications If the number is odd we have to perform 1 extra multiplication, to make our problem even, before we can reduce our problem size in half. So even if, after every time we reduce our problem in half, the exponent was odd, it would only take: 2 * log(n) multiplications But 2 * log(n) is still O(log n) (For the sake of accuracy, I should mention that, in the above analysis I used pseudo asymptotic times for sake of clarity. For the real asymptotic time, the value of n, should be measured in bits required to represent the decimal value of n) Hope this makes sense

Q: Why not also use `x^n=x^(n-1) x` for when *n* is positive and even,why does the recursive case *need* to be different?

*Short Answer* : We don't want to use x^n = x^(n-1) * x for the positive even case, because it is inefficient. *Long Answer* : If we use: x^n = x^(n-1) * x Then: -we use 1 multiplication -we reduce the size of our problem by 1 (we still have to figure out the value of x^(n-1)) If we use x^n = x^(n/2) * x^(n/2) Then: -we use 1 multiplication -we reduce the size of our problem in half (we still have to figure out the value of x^(n/2)) We can quickly see that if n was a power of two then: -the top method would require ~n multiplications -the bottom method would only require ~log_2(n) multiplications e.g. n=8 Top method: x^8= x^7 * x (need to find x^7) x^7= x^6 * x (need to find x^6) x^6= x^5 * x (need to find x^5) x^5= x^4 * x (need to find x^4) x^4= x^3 * x (need to find x^3) x^3= x^2 * x (need to find x^2) x^2= x^1 * x (need to find x^1) x^1= x^0 * x (need to find x^0) x^0 = 1 Bottom method: x^8= x^4 * x^4 (need to find x^4) x^4= x^2 * x^2 (need to find x^2) x^2= x^1 * x^1 (need to find x^1) x^1= x^0 * x (need to find x^0) x^0 = 1 We can see that the bottom method is much more efficient than the top method. Hope this makes sense

Q: When implementing the _negative part_ of *Recursive powers challenge* , I did this : ``` if( n < 0 ) { return 1 / (x * power(x, n+1)); } ``` and got the expected output but did not pass the test until I did this: ``` if( n < 0 ) { return 1 / ( power(x, -1*n) ); } ``` *Why is that? *

The first method is inefficient since it only reduces the problem size by 1 each recursive call. The second method is fast (if you did the code for positive exponents correctly), since it reduces the problem size by ~1/2 its current size each recursive call. So for something like x^-32 the first method would require 32 calls, but the second would require 6 calls.

Q: It seems hard to spot when you could implement the principle of recursion. The rules for when it works are simple, but heck if I could easily spot the opportunity to use it. Any tips?

Some problems that may be solved by using recursion: -You have a large problem , which you could solve if only you had a magic box which would give you the answer to smaller problems of the same form as the larger problem e.g. factorials I could solve factorial(n), if I had the answer to factorial(n-1), because: factorial(n)= n * factorial(n-1) Note: larger problem, solved by smaller problem of the same form This is a good candidate for recursion e.g. searching for a number in a sorted array I could find the index of a target value in a sorted array if I had the results of searches for the target value on the lower half of the array, and the upper half of the array This is a recursive version of a binary search When recursion may be a bad idea: -If the combined effort of solving the sub problems is more effort than solving the larger problem e.g. Fibonacci numbers

Q: I have a question concerning the efficiency of this recursive function relative to the iterative version of it. So if this is a recursive function, it should perform with O(log(n)) complexity while iterative function should have O(n) complexity, if I am not mistaken. But when I try to write both programs in java measuring the time of the execution with System.nanoTime();, it appears that iterative function is 1000 times quicker than the recursive function(iterative=roughly 500 nanoseconds, recursive=roughly 400 000 nanoseconds). My iterative function looks like: ```private static long computePowerIteratively(int pow, int num) { long startTime = System.nanoTime(); long result = 1; if (pow == 0) { return 1; } else if (pow<0) { for (int i = 1; i <= -pow; i++) { result *= num; } long endTime = (System.nanoTime() - startTime); System.out.println("Spent " + endTime + " nanoseconds"); System.out.println(num + " to the power of " + pow + " is " + 1/result); return 1/result; } else { for (int i = 1; i <= pow; i++) { result *= num; } long endTime = (System.nanoTime() - startTime); System.out.println("Spent " + endTime + " nanoseconds"); System.out.println(num + " to the power of " + pow + " is " + result); return result; } }```

Often, for small values of n, simple algorithms which have poor asymptotic complexity will outperform complex algorithms which have good asymptotic complexity. Asymptotic complexity only says how an algorithm will preform for large values of n. To properly analyze the running times you need to plot two curves (one for each algorithm) of the running time vs. n. The data also will likely be noisy , so instead of using the time for the function to run only once for that n, you should run it 100s or 1000s of times for that size (or possibly more if the data remains noisy), and average the time to get reliable values. Once you plot those curves you should see the iterative one is linear and the recursive one is logarithmic. Remember that in this case, for the n is the power. ( Note: For accuracy I will mention that the algorithms are not really O(n) and O(log n), as they are, in fact, pseudo-logarithmic and pseudo-linear, because n should be measured in their size in bits. However, this does not detract from the discussion above ) Hope this makes sense

Q: Why is x^n written as x^{n/2} . x^{n/2} ? I can also write it as x^{n/4} . x^{n/4}. x^{n/4}. x^{n/4} . How to do the complexity analysis ?

You could only do x^{n/4} . x^{n/4}. x^{n/4}. x^{n/4} . if n is evenly divisible by 4. In the worst case n is odd. In either case you need at most 2 steps to reduce the size of n in half (1st step is the odd step and the 2nd is the even step). If the time require to complete the code in the odd step and the even step is constant, c1 we have the cost is c1 * log_2(n) So we could say O(log(n) ) for a pseudo asymptotic time. (the size of the problem n is supposed to be measured in bits, so it is actually O(n) for asymptotic time)

Q: Not sure about negative case..

Perhaps an example will help. Suppose want to compute 3^-2. Then we would say: 3^-2 is the same as 1/(3^2) So, if we know what the value of 3^2 is, then 3^-2 is 1/(that value) 3^-2 = 1/(3^2) = 1/(9) = 1/9

Q: i m stuck in 2nd step hear is my power function ```var power = function(x, n) { println("Computing " + x + " raised to power " + n + "."); // base case if(n===0){ return 1; } // recursive case: n is negative // recursive case: n is odd if(isOdd(n)){ return power(x,n-1); } // recursive case: n is even }; ```

Let's use an example. If we want to compute 2^5 then x=2 and n=5 Since n is odd it's going to return us the result for 2^4. But we didn't ask for the result for 2^4, we asked for the result to 2^5. So, there must be something else we need to do. Hint: 2 * 2^4 = 2^5

Q: Doesn't `x^n = x^(n - 1) * x` work even for even numbers? Like ``` 2^4 = 2^3 * 2 2^3 = 2^2 * 2 2^2 = 2^1 * 2 2^1 = 2^0 * 2 2^0 = 1 2^1 = 2 2^2 = 4 2^3 = 8 2^4 = 16 ```

It works, but it isn't as efficient as calculating: x^n= x^(n/2) * x^(n/2) (O(n) vs O(log n) ) We want our algorithms to produce the correct result and to be efficient. (For the sake of accuracy, I should mention that, in the above analysis I used pseudo asymptotic times for sake of clarity. For the real asymptotic time, the value of n, should be measured in bits required to represent the decimal value of n)

Question 1

I understand we are trying to learn how to do recursive functions (so practicing it is worthwhile no matter what), but in this case is the use of a recursive function beneficial? In other words, is this simply an exercise, or is the recursive implementation actually better than the alternatives?

(An alternative could be to just loop through n, multiplying by x each time)

(An alternative could be to just loop through n, multiplying by x each time)

Accepted Answer

Multiplying x n times will require n steps, but the recursion only requires log_2(n) steps.

That being said, this recursion (as is the case with all recursions) can be converted to an iterative algorithm. And (as is the case with all recursions) the iterative version will save time and memory.

Basically, the iterative version is:
1) multipiier  = x
2) result = 1
3) Start at the rightmost bit in the binary representation of n
4) If the bit in the binary representation of n is set then result=result * multiplier
5) multiplier= multiplier * multiplier 
6) Move left 1 bit. If no more bits left, then exit and return result
7)  Go to step 4

Recursive versions of algorithms are usually easy to write, but if we are worried about speed or memory we try to convert them to iterative versions. One big concern is the recursion depth (how many times the algorithm calls itself) . If the depth is small, recursive algorithms are often a good solution. If the recursion depth is large, then running out of stack memory becomes a real concern.

Question 2

Just my 2 cents but I think the algorithm can be simplier :

```
var power = function(x,n) {
    if(n === 0) {
        return 1;
    }

if(n < 0) {
        return 1 / (power(x, abs(n))); //Make sure it's float AND abs
    }

return x * power(x, n-1);
}
```
(Check Cameron answer) There's no need for this odd / even thing or does it make the algorithm faster? I can't get why then... As far as I can tell my algorithm works. Actually, by the Big Theta theory it's seems to me that both my algorithm and the challenge are Θ(n). Still, I do understand that it's dividing the recursive call by 2 when is even, which is pretty smart.

Accepted Answer

For convenience, let's call the algorithm that you have proposed Algorithm A, and the algorithm proposed in the article Algorithm B.

Algorithm A is O(n) while Algorithm B is, in fact, O( log(n) ). 
This makes a big difference if n is large.

The difference between Algorithm A and Algorithm B are analogous to the differences between linear search and binary search.
Algorithm A and linear search only reduce the size of their problem by 1 after each iteration/recursion.
On the other hand, Algorithm B and binary search, roughly speaking, reduce the size of their problem in half each iteration/recursion.

But Algorithm B doesn't always reduce its problem size in half. It only reduces it in half when n is even. So how can we claim that is O(log(n)) ?
If n was a power of 2 then we would halve the problem every recursion.  It would take:
log(n) multiplications   
If the number is odd we have to perform 1 extra multiplication, to make our problem even,  before we can reduce our problem size in half. So even if, after every time we reduce our problem in half, the exponent was odd, it would only take:
2 * log(n) multiplications
But 2 * log(n) is still O(log n)

(For the sake of accuracy, I should mention that, in the above analysis I used pseudo asymptotic times for sake of clarity. For the real asymptotic time, the value of n, should be measured in bits required to represent the decimal value of n)

Hope this makes sense

Question 3

Why not also use `x^n=x^(n-1) x` for when *n* is positive and even,why does the recursive case *need* to be different?

Accepted Answer

*Short Answer* :
We don't want to use x^n = x^(n-1) * x for the positive even case, because it is inefficient.

*Long Answer* :

If we use: x^n = x^(n-1) * x 
Then:
-we use 1 multiplication
-we reduce the size of our problem by 1 (we still have to figure out the value of x^(n-1))

If we use x^n = x^(n/2) * x^(n/2)
Then:
-we use 1 multiplication
-we reduce the size of our problem in half  (we still have to figure out the value of x^(n/2))

We can quickly see that if n was a power of two then: 
-the top method would require ~n multiplications
-the bottom method would only require ~log_2(n) multiplications

e.g. n=8
Top method:
x^8= x^7 * x (need to find x^7)
x^7= x^6 * x (need to find x^6)
x^6= x^5 * x (need to find x^5)
x^5= x^4 * x (need to find x^4)
x^4= x^3 * x (need to find x^3)
x^3= x^2 * x (need to find x^2)
x^2= x^1 * x (need to find x^1)
x^1= x^0 * x (need to find x^0)
x^0 = 1

Bottom method:
x^8= x^4 * x^4 (need to find x^4)
x^4= x^2 * x^2 (need to find x^2)
x^2= x^1 * x^1 (need to find x^1)
x^1= x^0 * x   (need to find x^0)
x^0 = 1

We can see that the bottom method is much more efficient than the top method.

Hope this makes sense

Question 4

When implementing the _negative part_ of  *Recursive powers challenge* , I did this :
```
if( n < 0 ) {
    return 1 / (x * power(x, n+1));
}
```
and got the expected output but did not pass the test until I did this:
```
if( n < 0 ) {
    return 1 / ( power(x, -1*n) );
}
```
*Why is that? *

Accepted Answer

The first method is inefficient since it only reduces the problem size by 1 each recursive call.
The second method is fast (if you did the code for positive exponents correctly), since it reduces the problem size by ~1/2 its current size each recursive call.
So for something like x^-32 the first method would require 32 calls, but the second would require 6 calls.

Question 5

It seems hard to spot when you could implement the principle of recursion.  
The rules for when it works are simple, but heck if I could  easily spot the opportunity to use it.  Any tips?

Accepted Answer

Some problems that may be solved by using recursion:
-You have a large problem , which you could solve if only you had a magic box which would give you the answer to smaller problems of the same form as the larger problem

e.g. 
factorials
I could solve factorial(n), if I had the answer to factorial(n-1), because:
factorial(n)= n * factorial(n-1)
Note: larger problem, solved by smaller problem of the same form
This is a good candidate for recursion

e.g. 
searching for a number in a sorted array
I could find the index of a target value in a sorted array if I had the results of searches for the target value  on the lower half of the array, and the upper half of the array
This is a recursive version of a binary search

When recursion may be a bad idea:
-If the combined effort of solving the sub problems is more effort than solving the larger problem
e.g. Fibonacci numbers

Question 6

I have a question concerning the efficiency of this recursive function relative to the iterative version of it. So if this is a recursive function, it should perform with O(log(n)) complexity while iterative function should have O(n) complexity, if I am not mistaken. But when I try to write both programs in java measuring the time of the execution with System.nanoTime();, it appears that iterative function is 1000 times quicker than the recursive function(iterative=roughly 500 nanoseconds, recursive=roughly 400 000 nanoseconds). 
My iterative function looks like:
 ```private static long computePowerIteratively(int pow, int num) {
        long startTime = System.nanoTime();

long result = 1;
        if (pow == 0) {
            return 1;
        } else if (pow<0) {
            for (int i = 1; i <= -pow; i++) {
                result *= num;
            }
            long endTime = (System.nanoTime() - startTime);
            System.out.println("Spent " + endTime + " nanoseconds");
            System.out.println(num + " to the power of " + pow + " is " + 1/result);
            return 1/result;
        } else {
            for (int i = 1; i <= pow; i++) {
                result *= num;
            }
            long endTime = (System.nanoTime() - startTime);
            System.out.println("Spent " + endTime + " nanoseconds");
            System.out.println(num + " to the power of " + pow + " is " + result);
            return result;
        }
    }```

Accepted Answer

Often, for small values of n, simple algorithms which have poor asymptotic complexity will outperform complex algorithms which have good asymptotic complexity. Asymptotic complexity only says how an algorithm will preform for large values of n.

To properly analyze the running times you need to plot two curves (one for each algorithm) of the running time vs. n. The data also will likely be noisy , so instead of using the time for the function to run only once for that n, you should run it 100s or 1000s of times for that size  (or possibly more if the data remains noisy), and average the time to get reliable values. Once you plot those curves you should see the iterative one is linear and the recursive one is logarithmic.

Remember that in this case, for the n is the power.
( Note: For accuracy I will mention that the algorithms are not really O(n) and O(log n), as they are, in fact, pseudo-logarithmic and pseudo-linear, because n should be measured in their size in bits. However, this does not detract from the discussion above  )

Hope this makes sense

Question 7

Why is x^n written as x^{n/2} . x^{n/2} ?
I can also write it as x^{n/4} . x^{n/4}. x^{n/4}. x^{n/4} .
How to do the complexity analysis ?

Accepted Answer

You could only do x^{n/4} . x^{n/4}. x^{n/4}. x^{n/4} . if n is evenly divisible by 4.
In the worst case n is odd. 
In either case you need at most 2 steps to reduce the size of n in half (1st step is the odd step and the 2nd is the even step).

If the time require to complete the code in the odd step and the even step is constant, c1 we have the cost is c1 * log_2(n)

So we could say O(log(n) ) for a pseudo asymptotic time.
(the size of the problem n is supposed to be measured in bits, so it is actually O(n) for asymptotic time)

Question 8

Not sure about  negative case..

Accepted Answer

Perhaps an example will help.
Suppose want to compute 3^-2.
Then we would say: 3^-2 is the same as 1/(3^2)
So, if we know what the value of 3^2 is, then  3^-2 is 1/(that value)

3^-2 = 1/(3^2) = 1/(9) = 1/9

Question 9

i m stuck in 2nd step hear is my power function
```var power = function(x, n) {
    println("Computing " + x + " raised to power " + n + ".");
    // base case
    if(n===0){
        return 1;
    }
    // recursive case: n is negative 
    // recursive case: n is odd
    if(isOdd(n)){
        return power(x,n-1);
    }
    // recursive case: n is even
};
```

Accepted Answer

Let's use an example.
If we want to compute 2^5 then x=2 and n=5
Since n is odd it's going to return us the result for 
2^4. But we didn't ask for the result for 2^4, we asked for the result to 2^5. So, there must be something else we need to do.

Hint:
2 * 2^4 = 2^5

Question 10

Doesn't `x^n = x^(n - 1) * x` work even for even numbers? Like
```
2^4 = 2^3 * 2
2^3 = 2^2 * 2
2^2 = 2^1 * 2
2^1 = 2^0 * 2
2^0 = 1
2^1 = 2
2^2 = 4
2^3 = 8
2^4 = 16
```

Accepted Answer

It works, but it isn't as efficient as calculating:
x^n= x^(n/2) * x^(n/2)  
(O(n) vs O(log n) )
We want our algorithms to produce the correct result and to be efficient.

(For the sake of accuracy, I should mention that, in the above analysis I used pseudo asymptotic times for sake of clarity. For the real asymptotic time, the value of n, should be measured in bits required to represent the decimal value of n)

Course: Computer science theory > Unit 1

Computing powers of a number

Want to join the conversation?