遞歸到指數的遞歸解決方案

Question

嘿，我有一個問題，我必須以多種方式解決x^n。其中之一涉及使用遞歸公式，給我一個很難的時間。這樣的方法之一我用遞歸對於x^N對於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它只是返回基地。但是對於我的下一個，我必須使用三個公式來解決它。

• X = 1
• X ^Ñ如果n是偶數= [X ^N/2]
• X ^Ñ如果n是奇數= X * [ X ^n/2個]

小號Ø我有什麼到目前爲止

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

所以我只是試圖讓偶數先工作，當我設置X = 2和N = 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您的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))因爲我們現在得到甚至是一個例子。

我們基本上只是做這兩個步驟1.我認爲我的解釋聽起來有點奇怪，但希望它有幫助。