Motivo de la declaración de retorno en una llamada a función recursiva

13

Acabo de tener una duda en mi mente. La siguiente subrutina (para buscar un elemento, en una lista, por ejemplo) tiene una declaración de retorno al final:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    return( search_list(l->next, x) );
}

No puedo obtener el significado de la declaración de devolución al final (es decir, devuelve search_list (l- > next, x)). Sería de gran ayuda si alguien pudiera explicar este concepto, utilizando el modelo de pila.

    
pregunta user1369975 17.06.2013 - 07:13

2 respuestas

18

Una declaración de devolución devuelve un valor al llamante inmediato del marco de llamada de la función actual. En el caso de la recursión, este llamante inmediato puede ser otra invocación de esa misma función.

En la mayoría de los idiomas, si no usa el valor de retorno de una función a la que llamó (recursivamente o no), ese valor de retorno se descarta o es un error que se puede diagnosticar. Hay algunos idiomas en los que el valor de retorno de la última llamada de función se reutiliza automáticamente como el valor de retorno de la invocación de la función actual, pero no diferencian entre llamadas de función normales y recursivas.

Suponiendo que los valores de retorno no utilizados se descartan de forma silenciosa, si hubiera escrito el código de esta manera:

list *search_list(list *l, item_type x) {
  if (l == NULL) return(NULL);
  if (l->item == x)
    return(l);
  else
    search_list(l->next, x); // no return!
}

, entonces search_list solo devolvería un valor definido para una lista vacía (NULL) o si el primer elemento coincide con el valor que está buscando. Tan pronto como la función entra en la llamada recursiva, no sabes cuál será el resultado, porque el resultado de la llamada recursiva se descarta.

Además, prometes devolver un valor desde tu función, pero tienes una ruta (la recursiva) donde no especificas qué valor devolver. Dependiendo del idioma que use, esto generalmente se traduce en un diagnóstico obligatorio o en un comportamiento indefinido (lo cual es abreviado para: cualquier cosa puede suceder y puede cambiar en cualquier momento sin previo aviso. No responsabilice a nadie más que a usted mismo si se equivoca tu presentación más importante). En algunas situaciones, el valor de retorno faltante puede parecer que funciona, pero eso puede cambiar la próxima vez que ejecute el programa (con o sin recompilación).

    
respondido por el Bart van Ingen Schenau 17.06.2013 - 09:57
1

Dos cosas; Devolver la lista completa en el caso de que encuentre la "x" que está buscando no necesariamente garantiza el uso de la recursión, pero aparte de eso, tenga en cuenta lo siguiente:

Suponga que está buscando un valor de X="Diciembre", y su lista es el valor numérico de los meses del año, un puntero al mes siguiente y los ítems l- > en la lista están escritos Fuera nombres de los meses. (Enero, febrero, ..., diciembre). Necesitas los tres rendimientos para los posibles resultados. El primero, return (NULL) es necesario si la lista no contiene la X que está buscando. El segundo, (return (l)) devuelve la lista, en este caso, informándole que encontró su "x". El último es donde el modelo de pila entra en juego. Las llamadas sucesivas a la función habrían actualizado las variables locales (específicamente, l- > item's) así:

1: l->item = January
   returns search_list(l->next, x)
2: l->item = February
   returns search_list(l->next, x)
3-11: March, April, May, June, July, August, September, October, November
   all return search_list(l->next, x)
12: l->item = December
  This matches the second if() and returns your list, letting you know you found your search item.
    
respondido por el panhandel 17.06.2013 - 08:20

Lea otras preguntas en las etiquetas