c++中不使用全局变量的递归函数中的加法次数

Question

我必须实现一个计数器来计算这个递归函数中的加法次数，但我不允许使用全局变量。你知道怎么做吗？例如，如果函数必须在空闲时间调用自身，那么我的计数器必须在函数末尾 return 之前设置为 3。

long lindh(unsigned int n) {

  long lin = 0;
  if (n == 1 || n == 2) {
    lin = 1;
  } else {
    lin = 1 * lindh(n - 1) + 3 * lindh(n - 2);
  }

  return lin;
}

int main() {
  long b = 0;
  b = lindh(24);

  cout << "lindhauer " << b << endl;

  return 0;
}

Answer 1

您可以将函数签名更改为：

long lindh(unsigned int n, int &count)

在初始调用和每个递归调用中，将您希望计数结束的变量传递给它。在适当的地方增加count。

Answer 2

您可以定义一个带两个参数的重载 lindh 函数。重载函数有两个参数，而从 main 调用的版本是 "base" 函数，它只是委托给重载函数。

此外，由于您需要 return 一个 lin 值和 count，您可以 return 一个 std::pair<long, int> 来表示 lin 值和计数。这消除了对全局变量的需要，

这是一个例子：

#include <utility>
#include <iostream>


long lindh(unsigned int n, int &count) 
{
  long lin = 0;
  if (n == 1 || n == 2) {
    lin = 1;
  } else {
    ++count;
    lin = 1 * lindh(n - 1, count) + 3 * lindh(n - 2, count);
  }
  return lin;
}

std::pair<long,int> lindh(unsigned int n) 
{  
   int count = 0;
   return {lindh(n, count), count};
} 

int main() 
{
   auto b = lindh(24);
   std::cout << "lindhauer = " << b.first << "\ncount = " << b.second << std::endl;
}

Live Example

c++中不使用全局变量的递归函数中的加法次数

Number of additions in a recursive function without using global variables in c++

c++

recursion

counter

pointers

function-pointers