Рекурсивное решение для числа, поднятого до экспонента

Question

Эй У меня проблема: мне нужно решить x^n несколькими способами. Один из них предполагает использование формулы рекурсии, и это дает мне трудное время. Поэтому один из способов я использовал рекурсию для х^п при п> = 0

int power2(int base, int power){ 
    if (power == 0) 
     return 1; 
    else if (power == 1) 
     return base; 
    else 
     return (base * power2(base, power - 1)); 
} 

это имеет смысл для меня Так что, когда я установить X = 2 и N = 4, то снижается мощность, которая действует как счетчик, и делает силу 2x2 поднятой до 3, 4 * 2, мощность повышена до 2, 8 * 2 = 16. Чем мощность повышена до 1, и у меня есть базовый случай, если мощность повышена до 1 просто возвращает базу. Однако для моего следующего я должен решить его, используя три формулы.

• х = 1
• х ^п, если п четно = [х ^п/2]
• х ^п, если п нечетно = х * [ х ^п/2]

S о чем я до сих пор является

int power3(int base, int power){ 
    if(power == 0){ 
     return 1; 
    } 
    else if (power == 1) 
     return base; 
    // if power is even 
    if (power % 2 == 0){ 
     return base*(power3(base,(power/2))); 
    } 
    // if power is odd 
    else{ 
     return 0; 
    } 
} 

Так им просто пытаются получить даже номера работать первым, и когда я установил х = 2 и п = 4 она возвращает 8. Какой смысл для меня, так как, когда мощность 4/2 будет зацикливаться только на> 1. Поэтому я действительно пытаюсь выяснить способ заставить это зациклиться еще раз, оставаясь верным формуле, которую мне дали. И когда я добавил нечетный базовый случай, программа будет работать до n^5, но n^6 возвращается 32

Answer 1

У вас есть небольшая проблема с интерпретацией формулы.
x^n if n is even = [x^n/2]2 не означает:

base*(power3(base,(power/2))) //meaning x * [x^n/2] 

, а вы бы

(power3(base,(power/2))) * 2 

глядя на вашу формулу снова не исправить даже и должно быть x^n if n is even = [x^n/2]^2

так как код:

(power3(base,(power/2))) * (power3(base,(power/2))) 

или:

(power3(base * base,(power/2))) 

Ваша целая функция должна, вероятно, будет так:

int power3(int base, int power){ 
    if(power == 0){ 
     return 1; 
    } 
    else if (power == 1) // you don't really need this case, 
     return base;  // power == 0 is enough as base case 
     // if power is even 
    if (power % 2 == 0){ 
     return (power3(base * base,(power/2))); 
    } 
    // if power is odd 
    else{ 
     return base * (power3(base * base,(power/2))); 
    } 
} 

Хорошо, так как вы, кажется, по-прежнему следует путать с нечетными степенями.
Ваша power переменная равна int, поэтому вы получаете целочисленное деление, означающее 3/2 = 1 вместо 1.5 (все за десятичной точкой усекается).

Теперь давайте посмотрим на нечетном случае в функции:

return base * (power3(base * base,(power/2))); 

позволяет предположить base == 4 и power == 5

return 4 * (power3(4 * 4,(5/2))); // 5/2 evaluates to 2 

то же самое, как говорят return 4 * (power3(4, 5 - 1)) , а затем получить обратно (power3(4 * 4, 4 /2)), так как мы теперь получили четный случай.

Мы в основном просто делаем эти 2 шага как 1. Я думаю, что мое объяснение звучит немного странно, но надеюсь, что это поможет.