递归幂函数:方法 [英] Recursive power function: approach

问题描述

我现在编程有一段时间了(初学者)，递归函数对我来说是一个有点抽象的概念.我不会说我卡住了，程序运行良好，我只是想知道是否可以在代码中没有 pow 函数的情况下编写函数本身(但仍然完全按照问题的建议进行操作)

I'm programming for a while now(beginner), and recursive functions are a somewhat abstract concept for me. I would not say I'm stuck, program works fine, I'm just wondering if the function itself could be written without the pow function in the code (but still doing exactly what the problem suggests)

问题: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);但是执行失败了，我还在回溯原因.

I've tried doing this: power(power(x, n - 1), 2); but execution failed, and I'm still backtracking why.

推荐答案

在重写函数时，不要忽视递归在这种情况下的主要好处，即减少所需的乘法运算次数.例如，如果 n = 8，那么将 x * x 计算为 val1，然后将 val1 * val1 计算为 val2，将最终答案计算为 val2 * val2(3 次乘法)比计算 x * x * x * 要高效得多x * x * x * x * x(7 次乘法).

When rewriting your function, don't lose sight of the main benefit of recursion in this case, which is to reduce the number of multiplication operations required. For example, if n = 8, then it is much more efficient to compute x * x as val1, then val1 * val1 as val2, and the final answer as val2 * val2 (3 multiplications) than to compute x * x * x * x * x * x * x * x (7 multiplications).

这个区别对于小整数来说是微不足道的，但是如果你把这个操作放在一个大循环中，或者如果你用非常大的数字表示或者可能是巨大的矩阵来替换整数，这很重要.

This difference is trivial for small integers but matters if you put this operation inside a big loop, or if you replace the integers with very large number representations or maybe ginormous matrices.

这是一种在不消除递归效率的情况下摆脱 pow() 函数的方法:

Here's one way to get rid of the pow() function without getting rid of the recursion efficiency:

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

这篇关于递归幂函数:方法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！