c++ - recursivas - recursividad en java

¿Es posible la recursión de la cola si la comparación depende del valor de retorno?

Question

Tuve una tarea que pedía una función que usa la recursión directa para encontrar el índice del entero más bajo, más bajo, más negativo, de la izquierda. Los requisitos adicionales eran que los parámetros de la función fueran la matriz y el tamaño y que el valor devuelto para ningún valor válido fuera -999.

Se me ocurrió esto:

int LowIndexMinNeg(int src[], int size)
{
    if (size == 0)
       return -999;
    int index = LowIndexMinNeg(src, size - 1);

    if (index >= 0)
       return (src[size - 1] < src[index]) ? (size - 1) : index;
    else
       return (src[size - 1] < 0) ? (size - 1) : index;
} 

Funciona, satisface los requisitos y me dio todo el crédito. ¿Se puede implementar esto con recursión de cola?

Me parece que, dado que tienes que tomar el resultado de la llamada recursiva para usarlo en una comparación, debes decidir si lo pasas o lo actualizas, no sería posible, pero la recursión aún mantiene mi cerebro en nudos. Puede haber algo obvio que me falta.

Nota: Mi tarea ya estaba entregada y calificada.

Answer 1

Aquí es cómo puedes implementar eso usando la recursión de la cola:

int LowIndexMinNeg(int src[], int size, int index = 0, int lowest_index = -999, int lowest_value = 0)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNeg(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNeg(src, size, index+1, lowest_index, lowest_value);
    }
}

Esta implementación utiliza argumentos predeterminados para mantener la función en conjunto, pero esto hace que la interfaz sea desordenada. Puedes dividir esto en dos funciones si quieres:

static int LowIndexMinNegHelper(int src[], int size, int index, int lowest_index, int lowest_value)
{
    if (index >= size) {
        return lowest_index;
    }
    if (src[index] < lowest_value) {
        return LowIndexMinNegHelper(src, size, index+1, index, src[index]);
    } else {
        return LowIndexMinNegHelper(src, size, index+1, lowest_index, lowest_value);
    }
}


int LowIndexMinNeg(int src[], int size)
{
    return LowIndexMinNegHelper(src, size, 0, -999, 0);
}

En este caso, LowIndexMinNegHelper solo necesita ser una función local (que he indicado anteriormente con static ).

Answer 2

Necesita almacenar el número más bajo encontrado hasta ahora en algún lugar. Con tu función estás usando la pila para almacenar eso.

Con una función recursiva de cola, necesitarás almacenar el número más bajo encontrado hasta ahora en otro lugar. p.ej:

• Como variable global (ugh ..).
• Como parámetro a la propia función.
• Como variable miembro

El requisito que tienes para tu función probablemente descarta todos esos, por lo que te queda algo como el código que tienes, que no se puede escribir para que sea recursivo.

Para tener una idea de, por ejemplo, el 2 último punto:

  int LowIndexMinNeg(int src[], int size,int current_lowest = 0,int lowest_index = 0) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size -1;
     }
      return LowIndexMin(src,size - 1,current_lowest,lowest_index);
   }

Y

struct find_smallest {
  int current_lowest = 0;
  int lowest_index = 0

   int LowIndexMinNeg(int src[], int size) {
     if(size == 0)
        return current_lowest == 0 ? -999 : lowest_index;
     int val = src[size - 1] ;
     if(val < 0 && val  < current_lowest) {
        current_lowest = val;
        lowest_index = size - 1;
     }
      return LowIndexMin(src,size - 1);
   }
};

Answer 3

No estoy seguro de si las reglas de la asignación hubieran permitido definir una función auxiliar, pero esa es una transformación estándar para lograr la recursión de la cola cuando la firma más natural de la operación no lo permite. Por ejemplo:

int LowIndexMinNeg2(int src[], int size, int min)
{
    if (size == 0) return min;
    src--; size--; 
    if (min >= 0) min++;

    if (src[0] < 0
    && (min < 0 || src[0] <= src[min])) 
        min = 0;

    return LowIndexMinNeg2(src, size, min);
} 

int LowIndexMinNeg2(int src[], int size)
{
    return LowIndexMinNeg2(src + size, size, -999);
} 

Esta versión también invierte el orden de recorrido para hacer posible distinguir un valor "real" de ''min'' del valor ''no encontrado''. Otros enfoques, probablemente más legibles, implicarían el uso de acumuladores adicionales para el valor mínimo real (en lugar de solo un índice) y / o el desplazamiento actual en la matriz (para que el recorrido se pueda hacer en el orden "normal". Por supuesto, si estuviera codificando algo como esto para un uso serio, no estaría usando la recursión en primer lugar.

Answer 4

Podría tener una propuesta, pero por supuesto tuve que cambiar la firma:

int LowIndexMinNeg(int src[], int size, int min = -999)
{
  if (size == 0)
    return min;

  const int min_value = (min == -999) ? 0 : src[min];
  return LowIndexMinNeg(src, size - 1, src[size - 1] <= min_value ? size - 1 : min);
}

Answer 5

Podrías hacer esto con dos estáticas ...

int LowIndexMinNeg(int src[], int size)
{
  static int _min = 0;
  static int _index = 0;

  if (size == 0) return -999;
  if (_index == size) return (src[_min] < 0) ? _min : -999;
  if (src[_index] < 0 && src[_index] < src[_min]) _min = _index;
  ++_index;
  return LowIndexMinNeg(src, size);
}

Answer 6

Si transforma el resultado de la recursión antes de regresar, no es una cola recursiva.

EDITAR: Habiendo dicho eso, si quieres hacer la función recursiva de cola:

const int SENTINEL= 0;

int LowIndexMinNeg(int src[], int size, int index)
{
    if (size == 0)
    {
        if (index<0 || src[index]>=0)
            return -999;
        else
            return index;
    }

    int current_index= size - 1;
    int new_index= src[current_index]<=src[index] ? current_index : index;

    return LowIndexMinNeg(src, size - 1, new_index);
} 

Y llame como LowIndexMinNeg(src, src_size, src_size - 1)

EDIT2: encontrar el valor negativo más mal denominado de izquierda. Probablemente pueda declararlo como el índice del primer valor más negativo.

EDIT3: eliminando la mayoría de los condicionales, ya que es más fácil encontrar el índice del valor más bajo y luego verificar si es negativo.