Использование рекурсии для поднятия базы до ее степени - C ++

Question

Я просто хочу написать некоторый код, который использует рекурсию функций, чтобы поднять базу до ее уровня.Я знаю, что рекурсия - не самый правильный способ сделать что-то в C ++, но я просто хочу немного изучить концепцию.Программа запрашивает у пользователя базу и показатель степени, а затем утешает ответ.Вот программа, которую я написал:

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

Самое смешное, что когда я запускаю эту программу, она возвращает ответ как «1»!Может кто-нибудь помочь мне в этом?

Answer 1

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

У вас есть 3 основные проблемы:

• Вам не нужно использовать функцию Pow
• Чтобы сравнить число, вы должны использовать ==, так как = isназначение не сравнивается.
• Вы пропустили, что если показатель степени равен 0, вы должны вернуть 1.

Answer 2

Чтобы сделать это реальным ответом на C ++ - это та задача, в которой вы могли бы подумать о том, чтобы сделать ее функцией шаблона, поскольку она должна работать с любым типом чисел.

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

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

Пример того, сколько вычислений можно сэкономить: предположим, что вы хотите поднять число до 19. Это 18 умножений, если вы используете наивный циклоподобный подход. При таком решении получается

• 19 не делится ни на 2, ни на 3, поэтому рассчитайте b ⋅ b ^{e -1} , то есть
• б ¹⁸ . Теперь 18 делится на 2, поэтому мы возводим в квадрат b ^{e / 2} , что составляет
• б ⁹ . Где 9 делится на 3, поэтому мы куб b ^{e / 3} , что составляет
• б ³ . Где 3 делится на 3, поэтому мы куб b ^{e / 3} , что составляет
• b ¹ , то есть b.

Это было только 1 + 1 + 2 + 2 = 6 умножений, 1/3 от необходимой суммы для циклического подхода! Однако обратите внимание, что это не обязательно означает, что код будет выполняться гораздо быстрее, поскольку проверка факторов также занимает некоторое время. В частности, %3 на unsigned с, вероятно, не быстрее, чем умножение на int с, поэтому для NumT==int это не совсем умно. Но он является умным для более дорогих типов с плавающей запятой, complex, не говоря уже о типах матриц линейной алгебры, для которых умножение может быть чрезвычайно дорогим.

Answer 3

Вот версия с лучшей сложностью (O(lg exponent), вместо O(exponent)), которая концептуально похожа на версию leftroundabout.

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

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

Answer 4

Ваша проблема заключается здесь

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

во-первых, вы инвертировали условное выражение (если показатель равен нулю, оно должно возвращаться), во-вторых, вы присваиваете, а не сравниваете со вторым if.

Answer 5

Вот более понятное объяснение сложности O (log n)

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

Этот алгоритм работает по следующим простым правилам показателя

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

Таким образом, на каждом уровне значение nлибо половина того, что было, либо немного меньше п.Таким образом, самая низкая рекурсия - это 1+log n уровни

информация источник