Как я могу использовать формулу рекурсии, чтобы получить мощность без ошибки сегментации?

Question

Я работаю в лаборатории для своего класса C, и мы выполняем рекурсии и функции. Я искал помощи и пытался сделать это, чтобы получить ответ, но когда я набираю свои данные, он возвращает только ошибку сегментации.

Я пытался изменить расположение переменных и функций и даже типов int / float, но, похоже, ничего не работает, и я всегда получаю одну и ту же ошибку.

#include <stdio.h>

float power(float, int);

int main(void)
{
    float n;
    int k;

    printf("Please enter n = ");
    scanf("%f", &n);
    printf("Please enter k = ");
    scanf("%d", &k);

    printf("Sum = %f", power(n, k));

    return 0;
}

float power(float n, int k)
{
    return n * power(n, k - 1);
}

Я ожидал3 ** 3 - это 27, но вместо этого появляется ошибка сегментации: (

Answer 1

Ваша рекурсия называет себя бесконечно - она ​​делает power(3, 3), power(3, 2), power(3, 1), power(3, 0), power(3, -1) ... и т. Д.

Любое число в степени0 равно 1,0 - это ваш базовый случай, поэтому вы возвращаетесь туда.

Чтобы немного перехватить ошибку, вы также можете увидеть, слишком ли мала передаваемая мощность, чтобы быть действительной.

float power(float n, int k)
{
    if(k > 0) {
        return n * power(n, k - 1);
    }
    if(k == 0) {
        return 1.0;
    }
    return 1.0 / power(n, -k);
}

Answer 2

Вы должны признать, что рекурсия неверна и нарушена и никогда не должна использоваться.

Например, если вы добавите что-то для остановки рекурсии (например, if(k == 0) return 1;) , это все равно вызоветошибки сегментации для больших значений k (например, если вы делаете x = power(1.0, INT_MAX)).

Для этого случая тривиально преобразовать его в простой цикл;как:

    float power(float n, int k) {
        float result = 1.0;
        while(k > 0) {
            result *= n;
            k--;
        }
        return result;
    }

Однако, несмотря на то, что это больше не ужасно плохо из-за рекурсии, это все же не хорошо, потому что алгоритм неэффективен (особенно для больших значений k).

Более эффективный алгоритм выглядит примерно так:

    float power(float n, unsigned int k) {
        float result = 1.0;
        while(k > 0) {
            if( (k & 1) != 0) {
                result *= n;
            }
            k >>= 1;
            n *= n;
        }
        return result;
    }

Для этой версии с большим значением k, например, 50000, цикл будет выполняться только 16 раз вместо 49999 раз, что делает его значительно быстрее.

Конечно, вы можете сделать эффективную версию снова плохой, используя рекурсию, например:

    float power(float n, unsigned int k) {
        float result = 1.0;

         if(k > 1) {
             result = power(n*n, k >> 1);
         }
         if( (k & 1) != 0) {
            result *= n;
         }
         return result;
    }

В этом случае (вместо того, чтобы быть значительно более эффективным, потому что он зацикливается намного меньше)это будет значительно более эффективно, потому что рекурсивно будет намного меньше (а затем немного менее эффективно, потому что рекурсия отстой);и "намного меньше рекурсий" важно, потому что это означает, что гораздо менее вероятно, что большие значения k приведут к сбою.