Рекурсивная детерминантная функция, возвращающая неопределенное поведение

Question

Рекурсивная детерминантная функция, возвращающая неопределенное поведение

Я написал рекурсивную функцию для вычисления определителя. Я знаю, что мог бы сделать это гораздо эффективнее, но здесь дело не в этом. У меня есть переменная с именем «det1», которая содержит окончательное значение для определителя в конце рекурсии.
Странная часть, когда я возвращаю это значение в функцию det, я получаю полный мусор. НО, когда я просто показываю «det1», я получаю ответ. Есть догадки?

int det1 = 0;
int p = 0;

int det(vector<vector<int> > (&A)){
if (A.size() != A[0].size()){
cout << "Determinant Error: non-square matrix. \n";
return 0;
}
int cF;
vector<vector<int> > temp01;
if (A.size() == 2){
det1 += (A[0][0]*A[1][1]-A[0][1]*A[1][0]);
//cout << "Determinant : " << det1 << "\n";
int output = det1;                     ///////////////////////////////////////Problem with final return
//cout << "Recursion Count : " << p << "\n";
//return(output);                        ///////////////////////////////////////
}else{//extract until a 2x2 is reached
for (int i = 0; i < A.size(); i++){
temp01 = extractNext(A,0, i);
//printMatrix(temp01);
cF = pow(-1, (0)+(i))*A[0][i];
//cout << "Cofactor : " << cF << "\n";
for (int j = 0; j< temp01.size(); j++){
temp01[0][j] = cF*temp01[0][j]; //account for cofactor by multiplying it in
}
//printMatrix(temp); cout << "\n";
p++;
det(temp01);
}
}
}

1

c++determinants linear-algebra recursion

Решение

Другие решения

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

Для матрицы 2 * 2 ваш код должен возвращать правильное значение, при условии, что вы вызываете его только один раз, но только потому, что он сразу принимает часть «если» и выполняет окончательные вычисления за один шаг.
Однако для матрицы 3 * 3 берется часть «else».
Но обратите внимание, что по этому пути нет возврата, поэтому вы можете ожидать, что ваша функция вернет мусор.

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

0

Источник

Accepted Answer

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

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

С некоторыми незначительными изменениями я бы предложил что-то вроде

int det(const vector<vector<int>> &A)
{
if (A.size() != A[0].size()){
cout << "Determinant Error: non-square matrix. \n";
return 0;
}

if (A.size() == 2)
{
return A[0][0] * A[1][1] - A[0][1] * A[1][0];
}
else
{
int determinant = 0;
int sign = -1;
for (int i = 0; i < A.size(); i++){
vector<vector<int>> submatrix = extractNext(A, 0, i);
sign = -sign;
int cofactor = sign * A[0][i];
for (int j = 0; j < submatrix.size(); j++){
submatrix[0][j] = cofactor * submatrix[0][j];
}
determinant += det(submatrix);
}
return determinant;
}
}

2