Problem with pointer and recursive function

Question

The code is this :

Node * search ( Node ** root, int mats ) {

    if ( ! ( * root ) ) {

        return NULL;

    } else {

        search ( & ( * root ) -> esq, mats );

        if ( ( * root ) -> person.mat == mats ) {

            return ( * root );

        }

        search ( & ( * root ) -> dir, mats );

    }

    // return NULL;

}

The problem is that the compiler points out that it is giving segmentation failure ( I believe because of the return NULL end ), but if I remove the return NULL from the end it points out that the function is not getting back; so if I let it return NULL it breaks the address I get inside the else ... how to solve ?

Answer 1

The problem is that you do the search(&(*root)->esq, mats); and the search(&(*root)->dir, mats); and then throw away the recursion return value, so unless you happen to look for the value that’s in the root node, it won’t be able to return.

You need a local variable of type Node *; in the else you mark the result of search() for this variable and checks if it is null. If it is not, return it; otherwise, test the value of the current node and return it if it is correct; otherwise return the value of the second node search(). That should work.

Answer 2

How about:

Node * search( Node ** root, int mats )
{
    Node * n = *root;
    Node * e = NULL;

    /* verifica o fim da arvore */
    if( !n )
        return NULL;

    /* verifica o noh atual */
    if( n->person.mat == mats )
        return n;

    /* faz pesquisa na esquerda */
    e = search( &(n->esq), mats );

    /* se encontrou ocorrencia na esquerda... */
    if(e)
        return e;

    /* faz pesquisa na direita */
    return search( &(n->dir), mats );
}

Simplifying:

Node * search( Node * root, int mats )
{
    Node * e = NULL;

    /* verifica o fim da arvore */
    if( !root )
        return NULL;

    /* verifica o noh atual */
    if( root->person.mat == mats )
        return root;

    /* faz pesquisa na esquerda */
    e = search( root->esq, mats );

    /* se encontrou ocorrencia na esquerda... */
    if(e)
        return e;

    /* faz pesquisa na direita */
    return search( root->dir, mats );
}

Answer 3

The compiler does no magic - if you want to return the value that the recursive call to search find for the function that called search for the first time, explicitly place this Return in the code. Below, it is in the penultimate line:

Node * search ( Node ** root, int mats ) {
    if ( ! ( * root ) ) {
        return NULL;  
    }     

    if ( ( * root ) -> person.mat == mats ) {
            return ( * root );
        }
    return search ( & ( * root ) -> dir, mats );
}

The changes I made are: if the root is null, the rest of the function is not executed - then it does not need to be inside a block else- this lowers the levels of { }and identation and improves readability. It also seems that you had an extra call to search before that second if.

And as a final note, the compiler never gives "Segmentation fault" - the operating system gives a "Segmentation fault" while interrupting your program by which it caused an illegal memory access.