matematicas - funciones recursivas javascript

C la función recursiva no devolverá verdadero

Question

Tengo una función de búsqueda que emplea recursión para realizar una búsqueda binaria de una matriz, values[] , para un value :

int recurseSearch(int value, int values[], int min, int max) {
if (value > values[max] || min > max) return 1;
int midpoint = (max+min)/2;
if (values[midpoint] > value)
//search in left
recurseSearch(value, values, min, midpoint);
else if (values[midpoint] < value)
//search in right
recurseSearch(value, values, midpoint, max);
else if (values[midpoint] == value)
return 0;
else
return 2;
return 3;
}

El código que llama a esto simplemente llama recurseSearch(value, values, 0, n);
Por el bien de verificar, estableceré los values[5] a igual {3, 11, 32, 54, 66} , el value será 3 (es decir, esto debería devolver 0), y n por lo tanto, será 5 .

Entonces esto se llama: recurseSearch(3, values, 0, 5);

Ahora esperaría que esto eventualmente vuelva, e imprima, 0 , ya que 3 está realmente en la matriz. Al depurar todo va bien hasta que el midpoint sea ​​0, y por lo tanto los values[midpoint] == value es verdadero, y por lo tanto la línea de return 0 debe ejecutarse. Sin embargo, lo que ocurre en cambio es que sí lo hace, pero luego el control aparentemente se mueve hacia el final (cierre } ) de la función, pero luego vuelve a subir y ejecuta el return 3; en línea (aquí) 21.

No puedo entender por qué la declaración return 0 no solo sale de la función y por qué la return 3 no se ejecuta en absoluto

Nota: este problema se resuelve eliminando el return 3; línea, sin embargo, esto hace que clang se queje, y el comando para ejecutar ( make ) que estoy usando, fatalmente tiene un silbido, que preferiría evitar

Answer 1

No he examinado cuidadosamente tu código, por lo que podría haber otros errores, pero parece que quieres que el valor de retorno de la llamada recursiva más profunda pase por la pila hasta la persona que llama. En ese caso, eliminarías la return 3; y simplemente devuelva el valor de cada una de las llamadas recursivas que está realizando:

int recurseSearch(int value, int values[], int min, int max) {
if (value > values[max] || min > max) return 1;
int midpoint = (max+min)/2;
if (values[midpoint] > value)
//search in left
return recurseSearch(value, values, min, midpoint);
else if (values[midpoint] < value)
//search in right
return recurseSearch(value, values, midpoint, max);
else if (values[midpoint] == value)
return 0;
else
return 2;
}

La forma en que originalmente escribió su código, los valores de retorno de las llamadas recursivas se ignoraron por completo, y el return 3; declaración sería ejecutada en su lugar.