使用递归乘以幂

Question

我正在寻找一种方法来编写一个仅使用递归循环将整数乘以指数的程序。我对递归的理解非常有限，但已经能够编写一些代码来给出阶乘：

int fac2(int n)
{
    if (n == 1){
        return 1;
    } else {
        return n*fac2(n-1);
    }
}

我已经有办法找到幂，但它使用 for 循环：

int my_power(int x, int e)
{
    int i, total;
    total = 1;
    for (i = 1; i <= e; i++){
    total *= x;
    }
    return total;
}

我怎样才能替换它for循环使用递归？

Answer 1

int my_power (int x, int e) {
  if (e == 0) return 1;

  return x * my_power(x, e-1);
}

Answer 2

请记住，递归函数会调用自身，直到实现某些基本情况。您的基本情况是什么？计算一个数的幂就像说你要乘以某个数 x 次。提示是调用递归函数，将幂减一，直到达到所需的基本情况。

Answer 3

使用戴夫·安德森（Dave Anderson）作为基础，但也要考虑以下特殊情况：

1) x is 0 
2) e is negative.

同样，没有代码，因此您可以尝试自己弄清楚:-)

更新：确保创建许多测试用例，并且确保每个人都按照您认为应该的方式工作。一旦测试通过，您就会知道递归幂函数工作正常。

示例：有时间自己弄清楚后，我想我会提出一个带有测试的解决方案：

int main(void)
{
    // n = 0 special case
    test(0, 0, 1);
    test(4, 0, 1);
    test(-5, 0, 1);

    // x = 0 special case
    test(0, 0, 1);
    test(0, 2, 0);

    // normal use
    test(4, 1, 4);
    test(4, -1, 0.25);
    test(-4, 3, -64);
    test(8, 2, 64);
    test(2, 3, 8);
    test(2, -3, 0.125);
    test(2, -5, 0.03125);

    // Invalid input tests
    std::cout << std::endl << "Invalid input tests" << std::endl;
    test (0, -2, NULL);
    test(0, -4, NULL);


    // Negative Tests
    std::cout << std::endl << "Negative tests (expect failure)" << std::endl;
    test(4, 0, 4);
    test(2, 1, 1);
    test(2, -5, 0.0313);

    return 0;
}

double power(int x, int n)
{
    // check for invalid input
    if (n == 0)
    {
        return 1;
    }

    if (n > 0)
    {
        return x * power(x, n - 1);
    }
    else if (n < 0)
    {
        return 1 / (x * power(x, -n - 1));
    }
}

bool test(int x, int n, double expected)
{
    if (x == 0 && n < 0)
    {
        std::cout << "Testing " << x << "^" << n << ", result = 'Invalid input'." <<  std::endl;
        return false;
    }

    double result = power(x, n);
    std::cout << "Testing " << x << "^" << n << ", result = " << result << ". Expected " << expected << " - test " << ((result == expected) ? "PASSED" : "FAILED") <<  std::endl;
    return true;
}

输出：

Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 4^0, result = 1. Expected 1 - test PASSED
Testing -5^0, result = 1. Expected 1 - test PASSED
Testing 0^0, result = 1. Expected 1 - test PASSED
Testing 0^2, result = 0. Expected 0 - test PASSED
Testing 4^1, result = 4. Expected 4 - test PASSED
Testing 4^-1, result = 0.25. Expected 0.25 - test PASSED
Testing -4^3, result = -64. Expected -64 - test PASSED
Testing 8^2, result = 64. Expected 64 - test PASSED
Testing 2^3, result = 8. Expected 8 - test PASSED
Testing 2^-3, result = 0.125. Expected 0.125 - test PASSED
Testing 2^-5, result = 0.03125. Expected 0.03125 - test PASSED

Invalid input tests
Testing 0^-2, result = 'Invalid input'.
Testing 0^-4, result = 'Invalid input'.

Negative tests (expect failure)
Testing 4^0, result = 1. Expected 4 - test FAILED
Testing 2^1, result = 2. Expected 1 - test FAILED
Testing 2^-5, result = 0.03125. Expected 0.0313 - test FAILED

Answer 4

做你想做的事情的正确方法是注意：

• xⁿ = (x^n/2)²，如果 n 是偶数
• x ⁿ = x * (x^⊦n/2⫞)²，如果 n 为奇数
• x¹ = x
• x⁰ = 1

其中“⊦n/2⫞”表示 n/2 的整数部分（当 n 是整数变量时，这就是 n/2 在 C 中给出的值）。

与阶乘相反，阶乘为

• n! = n * (n - 1)!，如果 n > 0
• 0！ = 1

您应该能够编写一个基于阶乘的递归程序来求幂。

Answer 5

有一种思考这个问题的方法需要我们走出C-land，但它的核心如此简单且强大，非常值得考虑。

递归和迭代并不像乍看起来那么不同。在一定水平 ，实际上很难区分它们。我们不会完全去那里，但考虑一下 for“循环”的递归实现（没有特定的语言）：（

for (i, n, f, a) = 
  if (i > n) {
    return a
  } else {
    return for (i+1, n, f, f(a, i))
  }

a，顺便说一句，被称为“累加器”，因为它累积每个“循环”的值）

您可能会感到陌生的一件事是，上面将函数视为任何其他数据类型，这就是所谓的“一流函数"。这通常不是您在 C 中执行的操作（您可以通过传递函数指针以有限的方式执行此操作），但它是一个非常强大的概念，非常值得学习。

使用上面的 for 定义，我们将阶乘函数编写为：

mult(a,b) = a*b
fac(n) = for (1, n, mult, 1)

此推杆将每个 i 乘以累加器。

另一个强大的概念（遗憾的是，C 根本不支持）是匿名函数，它只是创建的没有名称的函数。我将使用语法 e ->; ... 对于匿名函数，其中 ... 是某个表达式（例如 x -> x+1），而 (a, b) 对于一对变量。在 C 中，匿名函数可能看起来毫无用处，但如果您可以像传递数字一样轻松地传递函数，则可以将 fac 简化为一行：

fac(n) = for (1, n, (a,i) -> a*i, 1)

pow 可以写成：

pow(x, e) = for(1, e, (a,i) -> a*x, 1) 

展开for，你就得到了pow的递归定义。

尽管这为您提供了递归函数，但还有另一种实现（实际上是 Alexandre 的）更省时。

Answer 6

据我所知，此函数对于任何可能的情况（不太可能将“asdfj”设置为 x 或 e）都有效。

#include <stdio.h>

double my_power(int x, int e)
{
    if (x == 0)
    {
        return 0;
    }
    if (e == 0)
    {
        return 1;
    }
    if (e > 0)
    {
        return x * my_power(x, e-1);
    }
    if (e < 0)
    {
        return 1/(x*my_power(x, -e-1));
    }
}

Answer 7

这是给您的伪代码：

FUNCTION mypower(number, exponent)
    IF exponent == 0 THEN:
        RETURN 1
    ELSE IF exponent > 0 THEN:
        RETURN number * mypower(number, exponent - 1)
    ELSE:
        RETURN 1 / mypower(number, -(exponent))

哦，返回值应该是double。

这是实际的代码：

double mypower(int n, int e) {
    if (e == 0)
        return 1;
    else if (e > 0)
        return n * mypower(n, e - 1);
    else
        return 1 / mypower(n, -e);
}