Что не так с этим методом рекурсии? Подсчитайте количество совпадающих элементов, которые находятся в одном индексе в 2 векторах
Я пытаюсь отладить эту программу, чтобы найти количество совпадающих элементов, которые встречаются в одном индексе в двух разных векторах. Требование НЕ использовать какие-либо петли
Code on online compiler: 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};
Вот пример вывода:
Returning 4
There are 32 matching numbers at same indexes
Number of Recursion calls: 8
Моя программа является рекурсивной, функция правильно возвращает ответ 4. Но основная программа печатает 32.
Из-за того, что ans - это static, и из-за вашего условия возврата ваша функция фактически возвращает ans * (v1.size()<v2.size() ? v1.size() : v2.size()) = 4 * 8 = 32.
Вы не только накапливаете ответ в ans (поскольку он помечен как static, он в основном становится глобальной переменной, как и calls), но вы также умножаете его на количество рекурсивных вызовов при возврате из matchCount.
Поставьте cout << "ans = " << ans << "\n"; перед строкой return ans + matchCount(v1,v2,i+1); и посмотрите на вывод. Это поможет вам понять, что происходит.
Ответы 3
ваша проблема возникает из-за того, что ans является статическим и тем фактом, что вы возвращаете его, когда достигаете конца вектора, а не 0 и т. д.
Я тоже не понимаю, почему эта функция рекурсивна
Мое требование заключалось в том, чтобы не использовать петли
@Manjunath, вы должны указать эту информацию в вопросе.
решение с циклом и другое с рекурсией, как вы просили в комментарии
#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;
}
конечно количество вызовов рекурсии min(v1.size(),v2.size()) - 1
У меня возникнет соблазн использовать тот факт, что true превращается в 1, а false в 0, чтобы упростить арифметику.
@Caleth, вы не можете предположить, что ((int) true) равно 1, это вероятно, но не уверен. Более того, даже если верно то, что ничего не меняет в сгенерированном коде, компилятор обязательно сгенерирует одно и то же в обоих случаях.
@Caleth, хорошо, спасибо за ссылку, я не знал. Но снова убедитесь, что сгенерированный код такой же.
Спасибо @bruno. Это действительно лаконичный и понятный код.
К сожалению, статическая переменная, накапливающаяся в рекурсивной функции, - это запах кода.
Обычно, когда вы используете рекурсию, каждый вызов начинается с чистой новой среды. В этом случае вы накапливаете значение каждого вызова с его дочерними элементами, чтобы найти общую сумму.
В качестве альтернативы вы можете использовать статическую переменную, которая обновляется при каждом вызове и используется только верхним родителем.
Но здесь вы смешиваете оба подхода, получая на самом деле слишком высокую ценность.
Итак, здесь 2 способа:
сделать
ansавтоматической (нестатической) переменной:... smallVecSz = (v1.size()<v2.size() ? v1.size() : v2.size()); int ans=0; if (i==smallVecSz) ...сохранять
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 за внимание)
Я надеюсь, что @Manjunath понимает, что с ответ static функция не может быть вызвана более одного раза, чтобы вернуть правильный результат (кроме, конечно, первого раза, когда результат был 0 :))
Какой интерес в статике smallVec?