遞歸功能函數：方法

Question

我正在編程一段時間（初學者），遞歸函數對我來說是一個有點抽象的概念。我不敢說我​​卡住了，程序工作正常，我只是想知道，如果函數本身可以無代碼pow函數被寫入（但仍然做題暗示什麼）

問題： http://prntscr.com/30hxg9

我的解決辦法：

#include<stdio.h> 
#include<math.h> 

int power(int, int); 

int main(void) 
{ 
    int x, n; 
    printf("Enter a number and power you wish to raise it to: "); 
    scanf_s("%d %d", &x, &n); 
    printf("Result: %d\n", power(n, x)); 
    return 0; 
} 

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

我試着這樣做：功率（功率（X，N - 1），2）; 但執行失敗，我仍然在回溯原因。

Answer 1

當你重寫功能，不要在這種情況下，這是減少所需的乘法運算的次數忽視遞歸的主要好處的。例如，如果n = 8，那麼將x * x計算爲val1，然後將val1 * val1計算爲val2，並將最終答案計算爲val2 * val2（3個乘法）比計算x * x * x * x * x * x * x * x（7次乘法）。

這個區別對於小整數來說是微不足道的，但是如果你把這個操作放在一個大循環中，或者如果用非常大的數字表示或者巨大的矩陣替換整數，

下面就來擺脫POW（）函數沒有擺脫的遞歸效率的一種方法：

#include<stdio.h> 
#include<math.h> 

int power(int, int); 

int main(void) 
{ 
    int x, n; 
    printf("Enter a number and power you wish to raise it to: "); 
    scanf_s("%d %d", &x, &n); 
    printf("Result: %d\n", power(x, n)); 
    return 0; 
} 

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

Answer 2

對於冪函數（比方說，X的n次冪），你有兩種情況：

exponent=0 
exponent=n 

對於第一種情況，你只需要返回1.在另一種情況下，你需要返回x爲n減1的冪。在那裏，你只是遞歸地使用了函數。

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

Answer 3

代碼：

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

不起作用，因爲當n爲偶數電源被稱爲n = 2，這是偶數，然後調用n = 2的功率，這是偶數，然後調用n = 2的功率直到堆棧溢出！

簡單的解決方案：乘法

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

Answer 4

簡單，但確實n個。上面的例子是更有效，因爲他們組兩個操作在一個迭代

int power(int x, int n) 
{ 
    if (n == 0) return 1; 

    return x * power(x, n-1); 
} 

Answer 5

double result = 1; 
int count = 1; 

public double power(double baseval, double exponent) { 
    if (count <= Math.Abs(exponent)){ 
    count++; 
    result *= exponent<0 ?1/baseval:baseval; 
    power(baseval, exponent); 
    } 
    return result; 
} 

這適用於正，負，和0值

Answer 6

這裏是紅寶石一個解決方案，適用於負指數以及

# for calculating power we just need to do base * base^(exponent-1) for ex: 
# 3^4 = 3 * 3^3 
# 3^3 = 3 * 3^2 
# 3^2 = 3 * 3^1 
# 3^1 = 3 * 3^0 
# 3^0 = 1 

# --------------------------------------------------------------------------- 
# OPTIMIZATION WHEN EXPONENT IS EVEN 
# 3^4 = 3^2 * 3^2 
# 3^2 = 3^1 * 3^1 
# 3^1 = 3^0 
# 3^0 = 1 
# --------------------------------------------------------------------------- 

def power(base, exponent) 
    if(exponent.zero?) 
    return 1 
    end 
    if(exponent % 2 == 0) 
    result = power(base, exponent/2) 
    result = result * result 
    else 
    result = base * power(base, exponent.abs-1) 
    end 

    # for handling negative exponent 
    if exponent < 0 
    1.0/result 
    else 
    result 
    end 
end 

# test cases 
puts power(3, 4) 
puts power(2, 3) 
puts power(0, 0) 
puts power(-2, 3) 
puts power(2, -3) 
puts power(2, -1) 
puts power(2, 0) 
puts power(0, 2) 

Answer 7

我的C++方法只適用於非負數。

#include <iostream> 
using namespace std; 

long long power(long long x, long long y) { 
if (y == 0) { 
    return 1; 
} 
else { 
    y--; 
    return x*power(x,y); 
} 
} 
main() { 
long long n, x; 
cin >> n >> x; 
cout << power(n,x); 
} 

Answer 8

int pow(int a, int n) { 
    if(n == 0) return 1; 
    if(n == 1) return a; 
    int x = pow(a, n/2); 
    if(n%2 == 0) { 
     return x*x; 
    } 
    else { 
     return a*x*x; 
    } 
}