Why does my recursive function in C cause a stack overflow?

Question

I'm trying to make a function calculating x to the power n (where x could be a double, n must be an int). A recursive algorithm would be this one, but implementing it in C gave me the stack-overflow error.

I tried finding my answer here, but the closest I found was this, which didn't satisfy my needs.

Here is my code:

double power_adapted(double x, int n) {
    if (n == 0)
        return 1;
    else if (n == 1)
        return x;
    else if (n % 2 == 0)
        return power_adapted(power_adapted(x, n / 2), 2);
    else
        return x * power_adapted(power_adapted(x, (n - 1) / 2), 2);
}

Maybe it is called too often; every call to a function generates a seperate stack frame on, well, the stack. Then it's probably time to find a better algorithm. — cadaniluk
– cadaniluk, Commented Nov 25, 2015 at 18:17

DBug · Accepted Answer · 2015-11-25 18:53:01Z

5

The recursive calls always pass 2 as n, so they will always trigger another recursive call.

I think you misinterpreted the formula. I would interpret it as:

else if (n % 2 == 0) {
    double v = power_adapted(x, n / 2);
    return v * v;
}
else {
    double v = power_adapted(x, (n - 1) / 2);
    return x * (v * v);
}

edited Nov 25, 2015 at 18:53

answered Nov 25, 2015 at 18:18

DBug

2,5661 gold badge14 silver badges26 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

Martijn Luyckx Over a year ago

I found that I missed multiplying by X once, would that fix it?

DBug Over a year ago

doubt it, As long as the value for n is not altered and > 1, it will recurse forever

Martijn Luyckx Over a year ago

Since I know for sure the picture of the algorithm is right (got it from my teacher), where am I mistaken when translating it to C?

DBug Over a year ago

I think it's your use of the "double recursion". See answer update above

Community · Accepted Answer · 2020-06-20 09:12:55Z

3

I don't think what you're trying to accomplish makes sense.

If you take a look at this part of code,

else if (n % 2 == 0)
    return power_adapted(power_adapted(x, n / 2), 2);
else
    return power_adapted(power_adapted(x, (n - 1) / 2), 2);

While the nested calls may present no problem (as a statement), the call on the outside always has n = 2 and the base cases depend on n.

Solving the problem:

By taking a look at the formula provided, I think you should have a base case for n == 2 to return x * x (this is the simplest change to the algorithm). So, the algorithm could be stated as follows:

double power_adapted(double x, int n) {
    if (n == 0)
        return 1;
    else if (n == 1)
        return x;
    else if (n == 2)
        return x * x;
    else if (n % 2 == 0)
        return power_adapted(power_adapted(x, n / 2), 2);
    else
        return x * power_adapted(power_adapted(x, (n - 1) / 2), 2);
}

edited Jun 20, 2020 at 9:12

CommunityBot

11 silver badge

answered Nov 25, 2015 at 18:21

anon

5 Comments

Martijn Luyckx Over a year ago

I'm sure the algorithm (picture in question) is right (got it from my teacher). How is my code not a translation of that? I can't seem to find my mistake.

anon Over a year ago

Change the outer power_adapted call to pow which is a function of math.h or add a base case for n == 2 to return x * x.

Martijn Luyckx Over a year ago

I will try to add that base case (I'm not allowed to use math.h). Could you tell my anyway where I made my mistake when translating that screenshot to C?

Alex Celeste Over a year ago

@MartijnLuyckx The screenshot is also "wrong" for the same reason. Perhaps your teacher wanted you to solve the error, perhaps it's just badly-expressed. Either way the algorithm in the image assumes you have a separate way of handling x^2.

Martijn Luyckx Over a year ago

Thanks! Marked as corrrect

Collectives™ on Stack Overflow

Why does my recursive function in C cause a stack overflow?

2 Answers 2

4 Comments

Solving the problem:

5 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

4 Comments

Solving the problem:

5 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related