Что не так с этим методом рекурсии?Подсчитать количество совпадающих элементов с одинаковым индексом в 2 векторах

Question

Я пытаюсь отладить эту программу, чтобы найти количество совпадающих элементов, которые встречаются с одним и тем же индексом в 2 разных векторах.Требуется НЕ использовать циклы

Код в онлайн-компиляторе: 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;
}

Вот пример ввода:

vector v1 = {2, 5, 2, 1, 8, 9, 1, 6, 9, 2};

vector v2 = {2, 5, 3, 0, 8, 4, 1};

Вот пример вывода:

Возвращается 4

Есть 32 соответствующих номеровс теми же индексами

Количество вызовов рекурсии: 8

Моя программа рекурсивно, функция корректно возвращает ответ 4. Но основная программа печатает 32.

Answer 1

решение с циклом, а другое с рекурсией, как вы просили в комментарии

#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;
 }

Answer 2

Упс, статическая переменная, накапливающаяся в рекурсивной функции, является запахом кода.

Обычно, когда вы используете рекурсию, каждый вызов начинается с чистой свежей среды.В этом случае вы накапливаете значение каждого вызова с его дочерними элементами, чтобы найти общее значение.

В качестве альтернативы, вы можете использовать статическую переменную, которая обновляется при каждом вызове и используется только верхним родителем.

Но здесь вы смешиваете оба подхода, фактически получая слишком высокое значение.

Итак, есть два способа:

1. сделать ans автоматическим (неstatic) переменная:

   ...
   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 3

Ваша проблема возникает из-за того, что ANS является статичным, и из-за того, что вы возвращаете ее, когда достигаете конца вектора, а не 0 и т. Д.

Я тоже не понимаю, почему эта функция рекурсивна