递归功能函数：方法

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