使用带一个参数函数的递归求数字的平方

Question

下面是一个（平凡的）C++ 函数，它返回其参数的平方（一个非负整数）：

unsigned int square(unsigned int n) {
    return n*n;
}

你的工作：编写一个函数，它也返回 n ²但有以下约束：

• 您不能使用乘法运算符 *
• 您不能使用除法运算符 /
• 你不能有任何循环
• 您不能向函数添加任何其他参数
• 你的函数必须是自包含的：没有辅助函数！
• 您不能使用任何全局变量
• 您不能使用任何静态变量
• 您不能使用任何“位旋转”操作——没有移位等。

然而， …

• 您可以使用递归
• 您可以使用+和-运算符。

到目前为止，我已经尝试使用 n(n+n+n+...) 来获得平方，但是为此我需要一些可以跟踪递归循环的东西，但是因为该函数只能有一个参数，所以我需要另一种方法来解决这个问题。

Answer 1

为了将平方运算作为递归函数来实现，您首先需要用运算本身来表示：

(n-1) ² = n ² - 2n + 1 --> n ² = (n-1) ² + 2n - 1

然后，为了避免操作员*：

2n = n + n

因此，n ² = (n-1) ² + n + n - 1

考虑到这一点，您可以轻松实现square()为不使用运算符的递归函数*：

unsigned int square(unsigned int n) {
   if (n == 0)
      return 0; // base case

   return square(n-1) + n + n - 1; // recursive case
}

或者只是使用三元运算符的单个语句：

unsigned int square(unsigned int n) {
   return n? square(n-1) + n + n - 1: 0;
}

n等于 0 是基本情况（即，当递归停止时）。对于这种情况，它返回零，因为 0 ²为零。