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?

Solution 1

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

Solution 2

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);
}

Solution 3

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);
}

Solution 4

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.

View more solutions

Comments

[Loïc Faure-Lacroix]

Well the truth is that your n is never changing. It probably is doing infinite recursion until your stacks get filled.

[Alexander Scholz]

Isn't that a infinite loop?

[user3002211]

@LoïcFaure-Lacroix Well, it shouldn't change, why should it? I want to multiply the number n for k times.

[jcm]

I think that you want to check k and not n, am I wrong?

[Loïc Faure-Lacroix]

@AlexanderScholz no because the recursion isn't tail recursive

[Loïc Faure-Lacroix]

If the function is tail recursive, it might be able to recurse idefinitely without using more memory than the function really need.

[ScarletAmaranth]

@LoïcFaure-Lacroix Correct, you could eliminate the call and reuse the stack frame, I just wanted to give him an idea of what's happening if there is no base case.

[Jonathan Leffler]

Don't you need return n; when k == 1 in your revision of the original code?

[jcm]

may you mean 3 int instead of 3 byte?

[Jonathan Leffler]

Using two functions seems a little unnecessarily complex.

[Loïc Faure-Lacroix]

Yeah, I added my tail call optimizable version. While having k bigger than MAX_INT might not create a stackoverflow with my version, it should give unexpected results at some points if the numbers are too high for ints.

[Loïc Faure-Lacroix]

@jcm yeah we're not using 8bit chips anymore... :(

[Loïc Faure-Lacroix]

@JonathanLeffler then only use the first one with 3 parameters. The second function is just a shorthand and isn't necessary. That's the price you have to pay to have tail recursive functions.

[ScarletAmaranth]

@LoïcFaure-Lacroix I am not sure about this and too lazy to look up but I think that C++ doesn't actually enforce this "optimization" (unlike Haskell and probably other functional languages) - So meh :). (Yes, there is even difference in semantic implications should such optimization be preset, but yes, meh.)

[jcm]

I give you one up vote because we proposed the solution in comments before it was available as an actual response :-(

[Loïc Faure-Lacroix]

As far as I know, the language doesn't enforce it but most compiler might be already doing such kind of optimization for a long time. I'm pretty sure GCC does it by default.

[jcm]

@LoïcFaure-Lacroix ;-)

[Zac Howland]

@JonathanLeffler No, because the return statement will handle it: n * stepem(n, 0) will equate to n * 1. The only exit condition you need is for k == 0.

[Zac Howland]

The only issue I have with this is the <=0 check. If k is negative, the return value (mathematically) would be a fraction, not 1. The safer solution is to prevent negative numbers for the exponent, altogether (unless the desire is to actually handle floating point numbers).

[Zac Howland]

@JonathanLeffler Oh, if you mean the first code block, I just corrected the conditional checks to show how the algorithm is wrong. The corrected code is in the second block (which does not have the k == 1 check at all).

[Jonathan Leffler]

The first block was what I was referring to. It is a legitimate algorithm and works correctly if the second return is changed to return n; — even though it would also work correctly (but slightly more expensively) if the else if (k == 1) return n; condition were removed, as in your second version of the code. The difference is one less function call vs one more test — not huge.

[Zac Howland]

I didn't fix that part in the first code block because I wanted to show that returning 1 from that block was mathematically wrong.

[jcm]

@ZacHowland I agree that, being strict, using negative exponential, would mean return a fraction but, taking into account proposed function signature, I assumed that only positive values are expected. I would update it to support negative exponents ;-)