使用带有一个参数函数的递归来找到数字的平方

一尘不染

algorithm

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

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

您的工作：编写一个也返回n 2但具有以下约束的函数：

但是……

到目前为止，我已经尝试使用n（n + n + n +
…）求平方，但是为此，我需要一些可以跟踪递归周期的东西，但是由于函数只能有一个参数，因此我需要另一种方法解决这个问题。

阅读 298

2020-07-28

共1个答案

一尘不染

为了将平方运算实现为递归函数，您需要首先根据自身来表示该运算：

第（n-1） 2 = N 2 - 2N + 1 _ --> _ñ 2 =（N-1）2 + 2N - 1

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

2n = n + n

因此， n 2 =（n-1）2 + 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 2为零。

2020-07-28