这种递归方法有什么问题？计算 2 个向量中同一索引中的匹配元素的数量

Question

我正在尝试调试这个程序，以找到在两个不同向量中出现在同一索引处的匹配元素的数量。要求是不使用任何环路

在线编译器上的代码：http://cpp.sh/8rvtj

#include <iostream>
#include <vector>
using namespace std;
int calls=0;
int matchCount(const vector<int>& v1, const vector<int>& v2, int i=0)
{
calls++;
static int smallVecSz=-1;
smallVecSz = (v1.size()<v2.size() ? v1.size() : v2.size());
static int ans=0;
if(i==smallVecSz)
{
cout << "Returning " << ans << endl;
return ans;
}
// if element at index i is same in v1 and v2, add 1 to ans else add 0 to ans
ans += (v1[i]==v2[i] ? 1 : 0);
return ans + matchCount(v1,v2,i+1); // pass optional param index i+1 to advance to next ele
}
int main()
{
vector<int> v1 = {2, 5, 2, 1, 8, 9, 1, 6, 9, 2};
vector<int> v2 = {2, 5, 3, 0, 8, 4, 1};
cout << "There are " << matchCount(v1,v2) << " matching numbers at same indexes" << endl;
cout << "Number of Recursion calls: " << calls << endl;
return 0;
}

以下是输入示例：

向量v1＝{2，5，2，1，8，9，1，6，9，2}；

向量v2＝{2，5，3，0，8，4，1}；

以下是一个示例输出：

返回4

在相同的索引上有32个匹配数字

递归调用数：8

我的程序是递归函数，它正确地返回ans4。但主程序是打印32。

Answer 1

Oops，在递归函数中积累的静态变量是一种代码气味。

通常，当您使用递归时，每次调用都会从一个干净、新鲜的环境开始。在这种情况下，您将每个调用的值与其子调用进行累加，以找到总数。

或者，您可以使用一个静态变量，该变量由每次调用更新，并仅由顶级父级使用。

但在这里，你混合了两种方法，实际上得到了太高的价值。

所以这里有两种方法：

1. 使ans成为一个自动(非静态(变量：

   ...
   smallVecSz = (v1.size()<v2.size() ? v1.size() : v2.size());
   int ans=0;
   if(i==smallVecSz)
   ...
   

2. 保持ans静止，不累积：

   ...
   ans += (v1[i]==v2[i] ? 1 : 0);
   matchCount(v1, v2, i+1); // pass optional param index i+1 to advance to next ele
   return ans;
   ...
   

   当然，在这种情况下，如果你多次调用该函数，你会得到错误的结果，因为ans不会重置为0(感谢@bruno的注意(

Answer 2

您的问题来自于ans是静态的，并且当您到达向量的末尾而不是0等时返回它

我也不明白为什么这个函数是递归

Answer 3

一个带有循环的解决方案和一个带有递归的解决方案，正如您在注释中请求的那样

#include <iostream>
#include <vector>
using namespace std;
int matchCount(const vector<int>& v1, const vector<int>& v2)
{
vector<int>::const_iterator it1;
vector<int>::const_iterator it2;
int result = 0;
for (it1 = v1.begin(), it2 = v2.begin();
(it1 != v1.end()) && (it2 != v2.end());
++it1, ++it2) {
if (*it1 == *it2)
result += 1;
}
return result;
}
int recurMatchCount(const vector<int>& v1, const vector<int>& v2, int i = 0)
{
return ((i == v1.size()) || (i == v2.size()))
? 0
: (((v1[i] == v2[i]) ? 1 : 0)
+ recurMatchCount(v1, v2, i + 1));
}
int main()
{
vector<int> v1 = {2, 5, 2, 1, 8, 9, 1, 6, 9, 2};
vector<int> v2 = {2, 5, 3, 0, 8, 4, 1};
cout << "There are " << matchCount(v1,v2) << " matching numbers at same indexes" << endl;
cout << "There are " << recurMatchCount(v1,v2) << " recur matching numbers at same indexes" << endl;
return 0;
}