使用单参数函数递归求数字的平方[关闭]

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

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

Your job: write a function which also returns n² but with the following constraints:

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

然而， …

• 您可以使用递归
• 您可以使用+ and -运营商。

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

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

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

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

2n = n + n

Therefore, n² = (n-1)² + n + n - 1

考虑到这一点，您可以轻松实施square() as a 递归函数不使用运算符*:

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 equal to zero is the base case (i.e., when the recursion stops). It returns zero for this case, since 0² is zero.