¿Por qué mi búsqueda binaria recursiva obtiene un error de desbordamiento de pila?

Answer 1

Es porque, cada vez que la función se llama recursivamente, usted está inicializando el
l = 0
r = array.length – 1

Como resultado de lo cual no está cambiando el tamaño de su ventana de búsqueda o, precisamente, no está disminuyendo el tamaño de su ventana de búsqueda.

Este código funcionará solo en caso de que el elemento a buscar esté en la posición media.
p.ej. matriz se parece a 1 2 3 4 5
Si busca 3, este código funcionará ya que no va a recurrir.

if (matriz [mid] == x)
volver a mediados

Este bloque de código suyo le dará la respuesta en el caso anterior.

Pero en el momento en que busca cualquier otro elemento colocado en una posición no intermedia o el elemento no presente en la matriz, el código desbordará la pila.

He modificado tu código. Se ve bastante similar

public static int recursiveBinarySearch (int [] array, int l, int r, int x) {

si (l <= r) {
int mid = l + (rl) / 2;

if (matriz [mid] == x)
volver a mediados

if (matriz [mediados]> x)
return recursiveBinarySearch (array, l, mid-1, x);

if (matriz [mediados] <x)
return recursiveBinarySearch (array, mid + 1, r, x);
}

volver -1;
}

Espero que esto ayude !

Answer 2

La CPU tiene que realizar un seguimiento de a qué invocación de la función volver, esto se llama la pila. Básicamente, está ingresando su función recursiva demasiadas veces, lo que generalmente es una indicación de un bucle infinito. Me doy cuenta de que está pasando I, y luego configurándolo en 0 … eso puede ser lo que lo está causando.

Answer 3

Las variables l y r se restablecen cada llamada recursiva (es decir, no se realizará ningún progreso), creando un error de desbordamiento de pila. En su lugar, llame a recursiveBinarysSearch (array, 0, array.length, x); y no restablezca los límites inferior y superior cada vez.

Answer 4

Está configurando L en cero en cada iteración, obviamente no está creciendo para alcanzar R y romperse.

Básicamente está invalidando la L que pasa a cada llamada recursiva. Intente inicializarlo fuera de la función una vez y luego use la L pasada a la función en cada llamada