使用带有一个参数函数的递归来找到数字的平方 [英] Find the square of a number using recursion with one parameter function

问题描述

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

Below is a (trivial) C++ function which returns the square of its parameter (a non-negative integer):

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

您的工作：编写一个也返回n ^2的函数，但受以下限制：

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

• 您不能使用乘法运算符 *


• 您不能使用除法运算符 /


• 您不能有任何循环


• 您不能向该函数添加任何其他参数


• 您的函数必须是自包含的：没有辅助函数！


• 您不能使用任何全局变量


• 您不能使用任何静态变量


• 您不能使用任何 bit twiddling操作-无移位等。

• You cannot use the multiplication operator *
• You cannot use the division operator /
• You cannot have any loops
• You cannot add any additional parameters to the function
• Your function must be self-contained: no helper functions!
• You cannot use any globals
• You cannot use any static variables
• You cannot use any "bit twiddling" operations -- no shifts, etc.

但是，…

• 您可以使用递归


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

• You can use recursion
• You can use the + and - operators.

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

So far I have tried getting the square using the n(n+n+n+...), but for that I need something that keeps track of the recursive cycle, but because the function can only have one parameter I need another way to tackle this problem.

推荐答案

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

In order to implement the square operation as a recursive function, you need first to express the operation in terms of itself:

（n-1） ² = n ² -2n +1 -> n ² =（n-1） ² + 2n-1

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

然后，为避免运算符 * ：

2n = n + n

因此， n ² =（n-1） ² + n + n-1

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

请记住，您可以轻松地将 square（）实现为不使用运算符的递归函数 * ：

With that in mind, you can easily implement square() as a recursive function that does not use the operator *:

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 ² 为零。

n equal to zero is the base case (i.e., when the recursion stops). It returns zero for this case, since 0² is zero.

这篇关于使用带有一个参数函数的递归来找到数字的平方的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！