Recursive Determinant Function Returning Undefined Behavior

Question

I wrote up a recursive function for computing a determinant. I know I could have done it much more efficiently but that is not the point here. I have a variable called "det1" that holds the final value for the determinant at the end of the recursion. The weird part is when I return this value in the det function, I get complete rubbish. BUT, when I just plain and simply print "det1" out, I get my answer. Any guesses here?

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

Provide [Minimal, Complete, and Verifiable example](https://stackoverflow.com/help/mcve). We have no idea what functions you call in `det` do and which way you use `det` itself. — Daniel Langr, Sep 04 '18 at 06:00
Global variables and recursion is not a pleasant combination. — molbdnilo, Sep 04 '18 at 06:03
Your function only returns a value if there's an error. In all other cases, using the (non-existent) return value is undefined. — molbdnilo, Sep 04 '18 at 06:05
Don't use global variables, ever. Also enable all compiler warnings, and treat them as errors. — n. m. could be an AI, Sep 04 '18 at 06:30
Also see [Why does this C++ snippet compile \(non-void function does not return a value\)](https://stackoverflow.com/a/20614325/1708801) — Shafik Yaghmour, Sep 04 '18 at 07:13
Unrelated to your problem, but using `pow(-1, ...)` is overkill. — Jabberwocky, Sep 04 '18 at 07:43
@n.m. never ever use globals is a tiny bit too strict, what about `std::cout` :P — 463035818_is_not_an_ai, Sep 04 '18 at 08:26
@user463035818 also never take any advice too literally (but that's from the advanced C++ course) — n. m. could be an AI, Sep 04 '18 at 08:43
@n.m. hope there are no singletons in your advanced course ;) — 463035818_is_not_an_ai, Sep 04 '18 at 08:46

score 2 · Answer 1 · answered Sep 04 '18 at 06:23

You're not returning a value on all code paths, which will ultimately lead to undefined behaviour when you use a return value that never existed.
(A reasonably modern compiler should warn you about this.)

You should return the determinant from the recursions instead of mutating a global - mixing mutable state and recursion usually only leads to trouble.
(This also makes your code much more similar to the mathematical definition of the determinant, which in turn makes it much easier to understand and verify.)

With some minor changes, I would suggest something like

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

score 0 · Answer 2 · answered Sep 04 '18 at 06:24

Your code is not returning determinant, because you did not create the return path for it. You do rely on side effects, too.

For 2*2 matrix your code should return correct value, provided you only call it once, but only because it immediately takes the "if" part, and does final calculations in one step. However, for 3*3 matrix, the "else" part is taken. But note, that there is no return on that path, so you can expect your function to return garbage.

To fix it, you need to rewrite the else branch such that you calculate the sum of values returned by recursive call, and use a temp variable on stack for this. Finally, you should return this value.

Recursive Determinant Function Returning Undefined Behavior

2 Answers2