Motivo da declaração de retorno na chamada de função recursiva

14

Eu só tinha uma dúvida em minha mente. A seguinte sub-rotina (para pesquisar um elemento, em uma lista, por exemplo) possui uma declaração de retorno no 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) );
}

Não consigo entender o significado da declaração de retorno no final (ou seja, retornar lista_de_pesquisa (l-> próximo, x)). Seria realmente útil se alguém pudesse explicar esse conceito usando o modelo de pilha.

user1369975
fonte
Se o primeiro termo da lista não for o resultado, pesquise o restante da lista . É isso que o último returnfaz.
Giorgio
@ Giorgio, por que apenas uma chamada de função não seria suficiente, por que um retorno é necessário antes disso?
user1369975
7
Porque você precisa de retornar o valor que é retornado pela função
Esailija
7
Downvoters: entenda que, dependendo do contexto do OP, não é nada óbvio o que returnfaz. De fato, em linguagens funcionais (e algumas mistas, como Scala) return não é necessário : o valor da função recursiva é o valor de sua última expressão. Simplesmente escrever search_list(l->next, x)sem returnteria funcionado em Scala! O significado da returndeclaração é óbvio apenas para programadores com um histórico imperativo.
Andres F.
OP: seu snippet de código está escrito em C?
Andres F.

Respostas:

19

Uma declaração de retorno passa um valor de volta para o chamador imediato do quadro de chamadas da função atual. No caso de recursão, esse chamador imediato pode ser outra invocação dessa mesma função.

Na maioria dos idiomas, se você não usar o valor de retorno de uma função chamada (recursivamente ou não), esse valor de retorno será descartado ou será um erro diagnosticável. Em alguns idiomas, o valor de retorno da última chamada de função é reutilizado automaticamente como valor de retorno da chamada de função atual, mas eles não diferenciam entre chamadas de função normais e recursivas.

Supondo que os valores de retorno não utilizados sejam descartados silenciosamente, se você tivesse escrito o código dessa maneira:

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!
}

então search_listsó iria devolver um valor definido para uma lista vazia (NULL) ou se o primeiro item corresponde ao valor que você está procurando. Assim que a função entra na chamada recursiva, você não sabe qual será o resultado, porque o resultado da chamada recursiva é descartado.

Além disso, você promete retornar um valor de sua função, mas possui um caminho (o recursivo) em que não especifica qual valor retornar. Dependendo do idioma que você usa, isso geralmente resulta em um diagnóstico obrigatório ou em um comportamento indefinido (que é uma abreviação de: tudo pode acontecer e pode mudar a qualquer momento sem aviso prévio. Não se responsabilize se alguém estragar tudo sua apresentação mais importante). Há algumas situações em que o valor de retorno ausente pode parecer funcionar, mas isso pode ser alterado na próxima vez em que o programa for executado (com ou sem recompilação).

Bart van Ingen Schenau
fonte
FWIW, Perl retorna o resultado da última expressão automaticamente, o que eu acho que significa que reutilizaria o valor de retorno. Mas eu não o toquei há anos, então não tenho certeza disso.
Bobson
1

Duas coisas; Retornar a lista inteira no caso de você encontrar o "x" que você procura não garante necessariamente o uso de recursão, mas, além disso, considere o seguinte:

Suponha que você esteja buscando um valor de X = "dezembro" e sua lista seja o valor numérico dos meses do ano, um ponteiro para o próximo mês e os itens l-> na lista sejam os nomes escritos meses. (Janeiro, fevereiro, ..., dezembro). Você precisa dos três retornos para os possíveis resultados. O primeiro, return (NULL) é necessário se a lista não contiver o X que você está procurando. O segundo, (return (l)) retorna a lista, neste caso, informando que você encontrou seu "x". O último é onde o modelo de pilha entra em jogo. Chamadas sucessivas para a função teriam atualizado variáveis ​​locais (especificamente, l-> itens) assim:

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.
panhandel
fonte
, obrigado pela sua ilustração, mas realmente não use o último retorno #
user1369975
Sem o último retorno, você nunca terá passado etapa 1.
panhandel