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

Question

Tenía una tarea que pedía una función que utiliza la recursión directa para encontrar el índice del entero más negativo a la izquierda en una matriz. Los requisitos adicionales eran para los parámetros de la función para ser la matriz y el tamaño y que el valor de retorno para ningún valor válido era -999.

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 tiene todo el crédito. ¿Puede esto implementarse con recursividad de cola?

Me parece que ya que tiene que tomar el resultado de la llamada recursiva para usar en una comparación para decidir si pasa eso o actualizarlo que no sería posible, pero la recursión todavía ata a mi cerebro en lo adosa así que puede haber algo obvio que me estoy perdiendo.

Nota: Mi tarea asignada ya fue entregada y calificada.

Answer 1

Necesita almacenar el menor número encontrado hasta ahora en alguna parte. Con su función, está utilizando la pila para almacenar eso.

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

• Como variable global (ugh ..).
• Como parámetro de la función en sí.
• Como miembro variable de

El requisito que tiene para su función, probablemente descarta a todos aquellos, por lo que te queda algo así como el código que tiene, que no puede ser escrito para ser recursiva de cola.

Para tener una idea de, p. el último punto 2:

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 2

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

EDIT: Una vez dicho esto, si usted quiere 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 llama como LowIndexMinNeg(src, src_size, src_size - 1)

Edit2: encontrar el valor más a la izquierda más negativo mal llamado. Probablemente pueda indicarlo 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, luego verifica si es negativo.

Answer 3

que podría tener una propuesta, pero por supuesto que tenía 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 4

Así es como se puede poner en práctica que el uso de la cola de recursión:

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 aplicación utiliza los argumentos por defecto a mantener la función en su totalidad, pero esto crea una interfaz desordenada. Se puede dividir esto en dos funciones si le gusta:

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 sólo tiene que ser una función local (que he indicado con static arriba).

Answer 5

no estoy seguro de si las reglas para la asignación habrían permitido definir una función auxiliar, sino que es una transformación estándar para lograr la recursión de 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 que sea posible distinguir un valor "real" de 'min' a partir 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 el conjunto (para que el recorrido se pueda realizar en un orden "normal"). por supuesto, si yo fuera cifrando algo como esto para su uso seria no sería el uso de la recursividad en el primer lugar.

Answer 6

se puede hacer esto con dos estática ...

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); 
}