0

我只是想编写一些代码，利用函数递归来提高基础。我知道递归不是在 C++ 中做事的最正确方法，但我只是想稍微探索一下这个概念。该程序要求用户提供一个基数和一个指数，然后控制台输出答案。这是我编写的程序：

#include <iostream>
#include <math.h>
using namespace std;

int raisingTo(int, int);
int main()
{
    int base, exponent;
    cout << "Enter base value: ";
    cin >> base;
    cout << "Enter exponent value: ";
    cin >> exponent;
    int answer = raisingTo(base, exponent);
    cout << "The answer is: " << answer << endl;
    char response;
    cin >> response;
    return 0;
}

int raisingTo(int base, int exponent)
{
    if (exponent > 0)
        return 1;
    else if (exponent = 0)
    {
        int answer = (int) pow((double)base, raisingTo(base, (exponent - 1)));
        return answer;
    }
}

有趣的是，当我运行这个程序时，它一直返回答案为“1”！有人可以帮我吗？

4

5 回答 5

8 
int raisingTo(int base, unsigned int exponent)
{
    if (exponent == 0)
        return 1;
    else
        return base * raisingTo(base, exponent - 1);
}

你有3个主要问题：

  • 您不必使用 pow 功能
  • 要比较数字，您应该使用分配==而=不是比较。
  • 你错过了如果指数等于 0 你应该返回 1。
于 2012-02-19T12:04:36.493 回答
2

为了使它成为一个实际的 C++ 答案——这是您可以考虑将其作为模板函数的任务，因为它应该适用于任何类型的数字类型。

递归实际上是一个好主意，但前提是您要利用它可以提供的好处：它可以通过从指数中分解出低数字来避免一些乘法。

template <typename NumT>
NumT raiseTo(NumT base, unsigned exponent) {
  if (exponent == 1) return base;
  if (exponent == 0) return 1;
  if (exponent%2 == 0) { NumT ressqrt = raiseTo(base,exponent/2)
                       ; return ressqrt*ressqrt;                  }
  if (exponent%3 == 0) { NumT rescubrt = raiseTo(base,exponent/3)
                       ; return rescubrt*rescubrt*rescubrt;       }
  else return base * raiseTo(base, --exponent);
}

一个例子，这可以节省多少计算：假设你想将一个数字提高到 19。如果你使用天真的循环方法，那就是 18 次乘法。有了这个解决方案，会发生什么

  • 19 不能被 2 或 3 整除，所以计算b ⋅ b e -1，即
  • 18 . _ 现在 18 可以被 2 整除，所以我们将b e/2平方，即
  • b 9。其中 9 可以被 3 整除，所以我们立方b e/3，即
  • 乙3 . 其中 3 可以被 3 整除，所以我们立方b e/3，即
  • b 1，即 b。

那只是 1+1+2+2 = 6 次乘法，是循环方法所需数量的 1/3！但是，请注意，这并不一定意味着代码会执行得更快，因为检查因素也需要一些时间。特别是，%3on unsigneds 可能并不比 s 上的乘法快int，所以NumT==int它一点也不聪明。但是对于更昂贵的浮点类型来说它是complex聪明的，更不用说乘法可能非常昂贵的线性代数矩阵类型了。

于 2012-02-19T12:18:54.810 回答
1

你的问题在这里

if (exponent > 0)
    return 1;
else if (exponent = 0)

首先，您已经反转了条件（如果指数等于零，它应该返回），其次，您正在分配而不是与第二个比较if。

于 2012-02-19T12:04:55.057 回答
1

这是一个复杂度更高的版本（O(lg exponent)，而不是O(exponent)），它在概念上类似于 leftroundabout 的版本。

int raisingTo(int base const, unsigned int const exponent, int scalar = 1)
{
    if (exponent == 0)
        return scalar;

    if (exponent & 1) scalar *= base;
    return raisingTo(base * base, exponent >> 1, scalar);
}

它还使用尾递归，这通常会导致更好的优化机器代码。

于 2012-02-19T16:33:00.540 回答
0

这是一个更简洁的解释，复杂度为 O(log n)

public int fastPower(int base , int power){

if ( power==0 )
  return 1 
else if(power %2 == 0 )
  return fastPower(base*base,power/2)
else
 return base * fastPower(base,power-1)
}

该算法遵循简单的指数规则

base^0 = 1
base^power = base*base^(power-1)
base^(2*power) = (base^2)^power

因此，在每个级别， n 的值要么是原来的一半，要么略小于 n 。因此，递归将永远是最糟糕的1+log n水平

信息来源

于 2014-06-14T13:41:44.337 回答