递归功率函数:方法

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

我试过这样做:power(power(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

代码：

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 调用 power，这是偶数，然后用 n = 2 调用 power，这是偶数，然后用 n = 2 调用 power ... 直到 ... 堆栈溢出！

简单的解决方案：

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