Recursive solution?

This is a discussion on Recursive solution? within the C++ Programming forums, part of the General Programming Boards category; I've been tasked to come up with a recursive solution to X^n = (X^(n/2))^ 2 if n is even X^n ...

  1. #1
    Registered User
    Join Date
    Sep 2007
    Posts
    10

    Recursive solution?

    I've been tasked to come up with a recursive solution to

    X^n = (X^(n/2))^ 2 if n is even

    X^n = (X * ((X^(n/2))^2)) if n is odd

    now here's the function i've written so far

    Code:
    double RecursivePower3(double& baseValue, double expPower, double powerValue){
    
        if (expPower == 0)
    		return 1;
    	if (expPower == 2)
    		return baseValue;
        if (fmod(expPower, 2) == 0){           //then it's even
    		powerValue = pow(pow(baseValue,floor(expPower / 2)), 2);
                    return powerValue;
        }
        else{
                    powerValue = (baseValue * pow(pow(baseValue,floor(expPower / 2)), 2);
                    return powerValue;
        } 
    }
    where baseValue = X and expPower = n and are values entered in by the user.

    can anyone tell me how this can be solved recursively?

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    You're trying to efficiently compute a nonnegative integer power n of x? Basically just picture the binary representation of n, and which power of x each digit corresponds to. You don't have to do it recursively - there's a fairly simple iterative solution (if you're allowed to use it).

  3. #3
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    we're supposed to write a recursive solution implementing that equation i gave at the beginning. The code I gave gives the right answers, it's just not the method wanted.

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Your recursive function should be declared something like
    Code:
    double power(double x, unsigned int n)
    (I think that's enough of a hint). You definitely don't want to call pow(), which is expensive. The recursive function doesn't need to do anything more than squaring and/or multiplying.

    Edit: If you want, you could extend the function to negative powers by having it call itself if n is negative, and then take the reciprocal.
    Last edited by robatino; 09-20-2007 at 01:37 AM.

  5. #5
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    I still don't understand where I should call the function inside the function to make it recursive.

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Xanz1441 View Post
    I still don't understand where I should call the function inside the function to make it recursive.
    Yes, a recursive function is calling itself, that is what makes it recursive.

    Say for example you have factorial, which is fac(n) = fac(n - 1) * n, and fac(0) = 1, then you have the following code:
    Code:
    int fac(int n)
    {
       if (n == 0) return 1;
       else 
          return n * fac(n - 1);
    }
    You should be able to do the same thing for your function, although it is a little bit more complex.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    so i tried this

    Code:
    double RecursivePower3(double& baseValue, double expPower){
    
    	if (expPower == 0)
    		return 1;
    	if (expPower == 2)
    		return baseValue;
        if (fmod(expPower, 2) == 0){           //then it's even
                    return (RecursivePower3(baseValue, expPower) / 2);
        }
    	else
    		return baseValue * (RecursivePower3(baseValue, expPower) / 2);
    
    }
    but it doesn't work.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    In your formula you have:

    X^n = (X^(n/2))^ 2
    X^n = (X * ((X^(n/2))^2))

    In your code you have:

    X^n = (X^n) / 2
    X^n = X * (X^n) / 2


    Also, don't forget that for some value num, num^2 is the same as num*num.

  9. #9
    Registered User
    Join Date
    Sep 2007
    Posts
    10
    Ok, now i've got this

    Code:
    double RecursivePower3(double& baseValue, double expPower){
    
    	double powerValue;
    
    	if (expPower == 0)
    		return 1;
    	if (expPower == 2)
    		return baseValue;
        if (fmod(expPower, 2) == 0){   //then it's even
                    return ((RecursivePower3(baseValue, expPower / 2)) * (RecursivePower3(baseValue, expPower / 2)));
        }
    	else
    		return (baseValue * ((RecursivePower3(baseValue, expPower / 2)) *(RecursivePower3(baseValue, expPower / 2))));
    }
    and for an even numbered expPower, it's outputting the power value of X ^ n/2 only, not squaring it

    like for 3 ^ 32 it's outputting 43046721

    and for the odd numbers it's not even outputting anything at all

  10. #10
    Registered User
    Join Date
    Jul 2005
    Posts
    14
    You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

    Code:
    X^n = X * X * ... {n times total} ... * X
    (why did I need code-tags to be able to submit this?)

    Study matsp's example.

    Edit: added a line.
    Last edited by cyph1e; 09-20-2007 at 03:32 PM.

  11. #11
    Registered User
    Join Date
    Jan 2005
    Posts
    7,319
    I think the problem might be your base cases. You have a base case of 2 returning the basevalue. But what that means is that basevalue^2 = basevalue. That of course is not right.

    I would think the only base you would need would be 0.

    Actually, the other problem I see is that you are using a double for the exponent. Are you sure that should be a double? The formulas look like they use integer math. You might never get to a base case with floating point math because that's not exact and you are using ==.

    Change the exponent to an integer and remove the second base case and I think you might have it right.

  12. #12
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by cyph1e View Post
    You do realize that (X^(n/2))^2 = X^n and (X * ((X^(n/2))^2)) = X^(n+1)? No need to overcomplicate things. However, if n is an integer, both will be X^n. Are you sure that is not the case? It seems like you should solve this by only using multiplication.

    Code:
    X^n = X * X * ... {n times total} ... * X
    (why did I need code-tags to be able to submit this?)

    Study matsp's example.

    Edit: added a line.
    Yes, but the solution is supposed to be done slightly differently - by squaring the result of a previous power calculation, you don't need so many steps. If we use the "brute force method"
    Code:
    double power(double x, int n)
    { 
       if (n == 0) return 1.0;
       else return d * power(d, n - 1);
    }
    For 2 ^5, this takes 6 recursions.

    If instead, we take the original formula:

    x^5 = x * ((x ^ 2) ^ 2), you only half the number of recursions.

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  13. #13
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Here's my obfuscated solution:
    Code:
    	if(!I)return 1.0;{double l=rp(i,I>>1);return(I&1)?(i*l*l):(l*l);}
    Note that I don't want to give the full solution, so this is just the function body.

    --
    Mats
    Last edited by matsp; 09-20-2007 at 05:37 PM. Reason: Not quite obfuscated enough.
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    835
    Here's the iterative solution:
    Code:
    double power(double x, unsigned int n) {
      double xn = 1.;
      while (n) {
        if (n & 1) xn *= x;
        n >>= 1;
        x *= x;
      }
      return xn;
    }
    Last edited by robatino; 09-20-2007 at 08:17 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. difference between recursive and iterative
    By Micko in forum C Programming
    Replies: 33
    Last Post: 07-06-2004, 09:34 PM
  2. Algorithm help (Changing from Recursive to Non Recursive)
    By Thantos in forum C++ Programming
    Replies: 1
    Last Post: 04-25-2004, 07:27 PM
  3. Request for comments
    By Prelude in forum A Brief History of Cprogramming.com
    Replies: 15
    Last Post: 01-02-2004, 09:33 AM
  4. Recursive Solution to Any Maze And Stack Overflow Problems
    By PunkyBunny300 in forum C Programming
    Replies: 14
    Last Post: 12-14-2002, 06:00 PM
  5. How to change recursive loop to non recursive loop
    By ooosawaddee3 in forum C Programming
    Replies: 1
    Last Post: 06-24-2002, 08:15 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21