CODEWITHSUNDEEP
c++recursionpow
Ram Sidharth
Ram Sidharth

Reputation: 183

Using Recursion to raise a base to its exponent - C++

I simply want to write some code that makes use of recursion of functions to raise a base to its power. I know that recursion is not the most right way to do things in C++, but I just want to explore the concept a bit. The program asks the user for a base and an exponent and then console outs the answer. Here's the program I've written:

#include <iostream>
#include <math.h>
using namespace std;

int raisingTo(int, int);
int main()
{
    int base, exponent;
    cout << "Enter base value: ";
    cin >> base;
    cout << "Enter exponent value: ";
    cin >> exponent;
    int answer = raisingTo(base, exponent);
    cout << "The answer is: " << answer << endl;
    char response;
    cin >> response;
    return 0;
}

int raisingTo(int base, int exponent)
{
    if (exponent > 0)
        return 1;
    else if (exponent = 0)
    {
        int answer = (int) pow((double)base, raisingTo(base, (exponent - 1)));
        return answer;
    }
}

The funny thing is, when I run this program, it keeps returning the answer as '1'! Can someone please help me on this?

Upvotes: 0

Views: 29219

Answers (5)

ip_x
ip_x

Reputation: 172

Here's a cleaner explanation with O(log n) complexity 

public int fastPower(int base , int power){

if ( power==0 )
  return 1 
else if(power %2 == 0 )
  return fastPower(base*base,power/2)
else
 return base * fastPower(base,power-1)
}

This algo works on following simple rules of exponent

base^0 = 1
base^power = base*base^(power-1)
base^(2*power) = (base^2)^power

Thus at each level, value of n is either half of what it was or it is little less than n . Thus the deppest the recursion will ever go is 1+log n levels

Information source

Upvotes: 0

Ben Voigt
Ben Voigt

Reputation: 283893

Here's a version with better complexity (O(lg exponent), instead of O(exponent)), which is conceptually similar to leftroundabout's version.

int raisingTo(int base const, unsigned int const exponent, int scalar = 1)
{
    if (exponent == 0)
        return scalar;

    if (exponent & 1) scalar *= base;
    return raisingTo(base * base, exponent >> 1, scalar);
}

It also uses tail recursion, which generally leads to better optimized machine code.

Upvotes: 1

leftaroundabout
leftaroundabout

Reputation: 120751

To make this an actual C++ answer – this is the kind of task where you might consider making it a template function, as this should work with any kind of number type.

Recursion is in fact a good idea, but only if you make use of the benefits it can offer: it can avoid some of the multiplications, by factoring out low numbers from the exponent.

template <typename NumT>
NumT raiseTo(NumT base, unsigned exponent) {
  if (exponent == 1) return base;
  if (exponent == 0) return 1;
  if (exponent%2 == 0) { NumT ressqrt = raiseTo(base,exponent/2)
                       ; return ressqrt*ressqrt;                  }
  if (exponent%3 == 0) { NumT rescubrt = raiseTo(base,exponent/3)
                       ; return rescubrt*rescubrt*rescubrt;       }
  else return base * raiseTo(base, --exponent);
}

An example how many calculation this can save: suppose you want to raise a number to 19. That's 18 multiplications if you use the naïve loop-like approach. With this solution, what happens is

  • 19 isn't divisible by either 2 or 3, so calculate b ⋅ be-1, which is
  • b18. Now 18 is divisible by 2, so we square be/2, which is
  • b9. Where 9 is divisible by 3, so we cube be/3, which is
  • b3. Where 3 is divisible by 3, so we cube be/3, which is
  • b1, which is b.

That was only 1+1+2+2 = 6 multiplications, 1/3 of the necessary amount for the loop-like approach! However, note that this doesn't necessarily mean the code will execute much faster, as the checking of factors also takes some time. In particular, the %3 on unsigneds is probably not faster than multiplication on ints, so for NumT==int it's not really clever at all. But it is clever for the more expensive floating point types, complex, not to speak of linear algebra matrix types for which multiplication may be extremely expensive.

Upvotes: 2

Necrolis
Necrolis

Reputation: 26181

Your problem lies here

if (exponent > 0)
    return 1;
else if (exponent = 0)

firstly, you've inverted the conditional (if the exponent is equal to zero, it should return), secondly, you are assigning and not comparing with the second if.

Upvotes: 1

Seagull
Seagull

Reputation: 3610

int raisingTo(int base, unsigned int exponent)
{
    if (exponent == 0)
        return 1;
    else
        return base * raisingTo(base, exponent - 1);
}

You have 3 main problems:

  • You don't have to use pow function
  • To compare number you should use == as = is an assignment not compare.
  • You missed that if exponent is equal 0 you should return 1.

Upvotes: 8

Related Questions