Recursion function to find power of number

Question

I'm writing a recursion function to find the power of a number and it seems to be compiling but doesn't output anything.

#include <iostream>

using namespace std;

int stepem(int n, int k);

int main()
{
    int x, y;

    cin >> x >> y;

    cout << stepem(x, y) << endl;

    return 0;
}

int stepem(int n, int k)
{
    if (n == 0)
        return 1;
    else if (n == 1)
        return 1;
    else
        return n * stepem(n, k-1);
}

I tried debugging it, and it says the problem is on this line : return n * stepem(n, k-1);

k seems to be getting some weird values, but I can't figure out why?

Answer 1

int stepem(int n, int k)

{
    if (k == 0)   //not n cause you have to vary y i.e k if you want to find x^y
        return 1; 
    else if (k == 1)
        return n;  //x^1=x,so when k=1 it should be x i.e n
    else
        return n * stepem(n, k-1);
}

Answer 2

sorry i changed your variable names but i hope you will understand;

#include <iostream>
using namespace std;

double  power(double , int);// it should be double because you also need to handle negative powers which may cause fractions

int main()
{
 cout<<"please enter the number to be powered up\n";
 double number;
 cin>>number;
 cout<<"please enter the number to be powered up\n";
 int pow;
 cin>>pow;
 double result = power(number, pow);
 cout<<"answer is "<<result <<endl;
}

 double power( double x, int n)
{

if (n==0)
    return 1;
if (n>=1)
    /*this will work OK even when n==1 no need to put additional condition as n==1
    according to calculation it will show x as previous condition will force it to be x;
    try to make pseudo code on your note book you will understand what i really mean*/
    if (n<0)
    return x*power(x, n-1);
   return 1/x*power(x, n+1);// this will handle negative power as you should know how negative powers are handled in maths
}

Answer 3

your Program is wrong and it Does not support negative value given by user, check this one

int power(int n, int k){
'if(k==0)
 return 1;
 else if(k<0)
 return ((x*power(x,y+1))*(-1));
 else
 return n*power(n,k-1);
 }

Answer 4

// Power.cpp : Defines the entry point for the console application.
//


#include <stream>

using namespace std;

int power(int n, int k);

void main()
{
    int x,y;

    cin >>x>>y;

    cout<<power(x,y)<<endl;


}

int power(int n, int k)
{
    if (k==0)
        return 1;
    else if(k==1) // This condition is working :) //
        return n;
    else
        return n*power(n,k-1);
}

Answer 5

Well, just to post an answer according to my comment (seems I missed adding a comment and not a response :-D). I think, mainly, you have two errors: you're checking n instead of k and you're returning 1 when power is 1, instead of returning n. I think that stepem function should look like:

Edit: Updated to support negative exponents by @ZacHowland suggestion

float stepem(int n, int k)
{
    if (k == 0)
        return 1;
    else
        return (k<0) ?((float) 1/n) * stepem(n, k+1)  :n * stepem(n, k-1);
}

Answer 6

Didn't test it but I guess it should give you what you want and it is tail recursive.

int stepemi(int result, int i int k) {
    if (k == 0 && result == i)
        return 1;
    else if (k == 0)
        return result;
    else
        return stepem(result * i, i, k-1);
}

int stepem(int n, int k) {
   return stepemi(n, n, k);
}

The big difference between this piece of code and the other example is that my version could get optimized for tail recursive calls. It means that when you call stepemi recursively, it doesn't have to keep anything in memory. As you can see, it could replace the variable in the current stack frame without having to create a new one. No variable as to remain in memory to compute the next recursion.

If you can have optimized tail recursive calls, it also means that the function will used a fixed amount of memory. It will never need more than 3 ints.

On the other hand, the code you wrote at first creates a tree of stackframe waiting to return. Each recursion will add up to the next one.

Answer 7

You should be checking the exponent k, not the number itself which never changes.

int rPow(int n, int k) {
    if (k <= 0) return 1;
    return n * rPow(n, --k);
}

Your k is getting weird values because you will keep computing until you run out of memory basically, you will create many stack frames with k going to "-infinity" (hypothetically).

That said, it is theoretically possible for the compiler to give you a warning that it will never terminate - in this particular scenario. However, it is naturally impossible to solve this in general (look up the Halting problem).

Answer 8

Your algorithm is wrong:

int stepem(int n, int k)
{
    if (k == 0) // should be k, not n!
        return 1;
    else if (k == 1) // this condition is wrong
        return 1;
    else
        return n * stepem(n, k-1);
}

If you call it with stepem(2, 3) (for example), you'll get 2 * 2 * 1 instead of 2 * 2 * 2 * 1. You don't need the else-if condition:

int stepem(int n, unsigned int k) // unless you want to deal with floating point numbers, make your power unsigned
{
    if (k == 0)
        return 1;
    return n * stepem(n, k-1);
}