Entonces, en el curso de programación que estoy tomando, aprendimos sobre la recursividad. Obtuve una asignación para escribir una función recursiva que obtiene una matriz ordenada y un número y devuelve el índice de ese número en la matriz si existiera.

Todavía no entendía bien el tema de la recursión, así que necesito un poco de ayuda con mi código. Creo que estoy en la dirección correcta, pero de nuevo, estoy luchando un poco con el tema, así que pensé que podría encontrar orientación y ayuda aquí.

Este es el código que tengo en este momento:

private static int arrayIndexValue(int[] arr, int ind)
{
    if (ind > arr.Length/2)
    {
        return arrayIndexValue(arr.Length/2, ind)
    }
    else if (ind < arr.Length/2)
    {
        return arrayIndexValue(arr.Length/2)
    }
}

Básicamente lo que quería escribir aquí es algo como esto:

Si el número que inserta el usuario es más pequeño que el centro de la matriz, continúe con la función pero con la matriz cortada por la mitad (búsqueda binaria)

Lo mismo si el número es mayor (sugerí usar mi función con algo como la búsqueda binaria, pero como puede ver, no sé cómo aplicarlo a mi código)

1
Dolev 27 abr. 2017 a las 17:16

3 respuestas

La mejor respuesta

Tengo una tarea para escribir una función recursiva que obtiene una matriz ordenada y un número y devuelve el índice de ese número en la matriz si existiera.

En su método, verifica los índices, no los valores: debe comparar los valores de los elementos, no los índices.

Para escribir una función recursiva para encontrar un elemento, debe pasar matriz, elemento a buscar, índice inicial y índice final. El índice inicial y el índice final se utilizarán para buscar en parte de la matriz.

Su método será algo como esto:

private static int GetIndex(int[] arr, int element, int startIndex, int endIndex)
{
    if (startIndex > endIndex)
    {
        return -1; //not found
    }

    var middleIndex = (startIndex + endIndex) / 2;

    if (element == arr[middleIndex])
    {
        return middleIndex;
    }

    if (element < arr[middleIndex])
    {
        return GetIndex(arr, element, startIndex, middleIndex - 1);
    }
    else
    {
        return GetIndex(arr, element, middleIndex + 1, endIndex);
    }
}

Y para obtener un índice:

static void Main(String[] args)
{
    var arr = new int[] { 1, 2, 3, 4, 5, 6, 7, 8, 9 };

    var element = 5;
    var index = GetIndex(arr, element , 0, arr.Length - 1);
}
1
Roman Doskoch 27 abr. 2017 a las 14:41

La recursión funciona al dividir todo el problema en partes más pequeñas. Si está en la parte más pequeña (lo que significa que su matriz tiene solo un valor), entonces tendría su solución. Este también sería su primer caso que tiene que manejar.

if (arr.Length == 1) return arr[0];

Ahora puede comenzar a analizar el problema. Decisión binaria izquierda o derecha. Como ya escribió, desea verificar el clima, el número se encuentra a la izquierda o a la derecha desde el centro de su matriz. Entonces, en su condición, necesita acceder al elemento en la matriz utilizando el operador [ ]:

if (ind > arr[arr.Length / 2]) // check if larger than the middle element

Para extraer una parte de la matriz, necesita una segunda matriz en la que pueda copiar el contenido que desee. Como tiene la intención de pasar solo la mitad de la matriz actual a la llamada recursiva, también necesita solo la mitad del tamaño.

int [] temp = new int[arr.Length / 2];

Ahora puede copiar la parte que desee (primera o segunda) según su condición y seguir buscando con una llamada recursiva.

Para copiar la matriz, puede usar la Arra.Copy método. Puede pasar el inicio y la longitud a este método y copiará la parte izquierda o derecha en la matriz int [] temp. Aquí hay un ejemplo de cómo copiar la parte correcta:

Array.Copy(arr, arr.Length / 2, temp, 0, arr.Length / 2);

Al final deberás disparar tu llamada recursiva. Esta llamada esperará la nueva matriz y aún el mismo número para buscar. Entonces, dado que copió la mitad izquierda o derecha de la matriz anterior, ahora pasa la nueva matriz corta a la llamada recursiva:

return arrayIndexValue(temp, ind);

Y ahí lo tienes

2
Mong Zhu 27 abr. 2017 a las 16:38

Entonces, el problema que tiene ahora es que no ha dividido su problema en pasos repetitivos. En realidad, debería ser un flujo muy similar a un bucle sin todas las variables. Quiero hacer algo un poco más simple primero.

void int find(int[] values, int at, int value) {
    if (values.Length >= at || at < 0) {
        return -1;
    } else if (values[at] == value) {
        return at;
    }
    return find(values, at+1, value);
}

Esta función solo mueve un índice hacia arriba una vez a través de la recursividad, pero también podemos hacer algo muy similar con un bucle.

void int find(int[] values, int at, int value) {
    while (values.Length < at && at >= 0) {
        if (values[at] == value) {
            return at;
        }
        at = at + 1;
    }
    return -1;
}

La razón por la que generalmente hablamos sobre la recursividad es que generalmente se usa para que no tenga un estado "mutante". Las variables y sus valores son los mismos para cada valor. Puede romper esto, pero generalmente se considera beneficioso. Una puñalada rápida a su problema produce algo como

void int find(int[] sortedValues, int start, int end, int value) {
    var midIndex = (start + end) / 2;
    var mid = sortedValues[midIndex];
    if (start == end) {
        return mid == value ? midIndex : -1;
    } else if (mid > value) {
        return find(sortedValues, mid, end, value);
    } else if (mid < value) {
        return find(sortedValues, start, mid, value);
    } else {
        return midIndex;
    }
}

Sin embargo, esto no es perfecto. Tiene problemas conocidos como casos extremos que podrían causar un bloqueo. Definitivamente debe limpiarse un poco. Si realmente desea sumergir el dedo del pie en la recursión, pruebe un lenguaje puramente funcional donde no pueda mutar, como Haskell, Elm, o tal vez algo un poco impuro como F #, Clojure o Scala. De todos modos diviértete.

1
Buttink 27 abr. 2017 a las 14:41