Em inglês simples, o que é recursão?

74

A idéia de recursão não é muito comum no mundo real. Então, parece um pouco confuso para os programadores iniciantes. Embora, eu acho, eles se acostumem ao conceito gradualmente. Então, qual pode ser uma boa explicação para eles entenderem a idéia facilmente?

Gulshan
fonte
Mais informações estão sendo compartilhadas sobre este assunto em Recursos para melhorar sua compreensão sobre recursão?
22411 Kenneth
1
Recursão é quando uma função pode se chamar. "Se você entende totalmente os espaços para nome e o escopo, e como os parâmetros são passados ​​para uma função, já conhece a recursão. Eu posso mostrar exemplos, mas você deve descobrir como eles funcionam por conta própria". Os alunos geralmente lutam com a recursão não tanto porque é confusa, mas porque eles não têm uma compreensão firme do escopo / espaço de nome variável. Antes de mergulhar na recursão, certifique-se de que os alunos possam rastrear adequadamente um programa em que você atribuiu propositadamente variáveis ​​em escopos diferentes com o mesmo nome para confundi-las.
dspyz
1
Para entender recursão, você deve primeiro entender recursão
Goerman

Respostas:

110

Para explicar a recursão , uso uma combinação de explicações diferentes, geralmente para ambas tentar:

  • explique o conceito,
  • explique por que isso importa,
  • explique como obtê-lo.

Para iniciantes, o Wolfram | Alpha o define em termos mais simples do que a Wikipedia :

Uma expressão tal que cada termo é gerado pela repetição de uma operação matemática específica.


Matemáticas

Se o seu aluno (ou a pessoa que você explica também, de agora em diante eu direi aluno) tem pelo menos algum conhecimento matemático, obviamente já encontrou recursão estudando séries e sua noção de recursividade e sua relação de recorrência .

Uma maneira muito boa de começar é demonstrar com uma série e dizer que é simplesmente do que se trata a recursão:

  • uma função matemática ...
  • ... que se chama para calcular um valor correspondente a um n-ésimo elemento ...
  • ... e que define alguns limites.

Normalmente, você recebe um "huh huh, whatev '", na melhor das hipóteses, porque eles ainda não o usam, ou mais provavelmente apenas um ronco muito profundo.


Exemplos de codificação

De resto, na verdade, é uma versão detalhada do que apresentei no Adendo da minha resposta para a pergunta que você apontou sobre ponteiros (trocadilho).

Nesta fase, meus alunos geralmente sabem como imprimir algo na tela. Supondo que estamos usando C, eles sabem como imprimir um único caractere usando writeou printf. Eles também sabem sobre os loops de controle.

Eu costumo recorrer a alguns problemas de programação repetitivos e simples até que eles o entendam:

  • a operação fatorial ,
  • uma impressora de alfabeto,
  • uma impressora de alfabeto invertida,
  • a operação de exponenciação .

Fatorial

O fatorial é um conceito matemático muito simples de entender, e a implementação está muito próxima de sua representação matemática. No entanto, eles podem não conseguir no início.

Definição Recursiva da Operação Fatorial

Alfabetos

A versão em alfabeto é interessante para ensiná-los a pensar sobre a ordem de suas declarações recursivas. Como nos ponteiros, eles lançam linhas aleatoriamente para você. O objetivo é levá-los à conclusão de que um loop pode ser invertido modificando as condições OU apenas invertendo a ordem das instruções em sua função. É aí que a impressão do alfabeto ajuda, pois é algo visual para eles. Basta que eles escrevam uma função que imprima um caractere para cada chamada e se auto-recursivamente para escrever a próxima (ou anterior).

Fãs de FP, pule o fato de que imprimir coisas no fluxo de saída é um efeito colateral por enquanto ... Não vamos ficar muito irritantes na parte frontal do FP. (Mas se você usar um idioma com suporte à lista, sinta-se à vontade para concatenar uma lista a cada iteração e apenas imprimir o resultado final. Mas geralmente eu os inicio com C, que infelizmente não é o melhor para esse tipo de problemas e conceitos) .

Exponenciação

O problema da exponenciação é um pouco mais difícil ( nesta fase do aprendizado). Obviamente, o conceito é exatamente o mesmo que para um fatorial e não há complexidade adicional ... exceto que você possui vários parâmetros. E isso geralmente é suficiente para confundir as pessoas e jogá-las fora no começo.

Sua forma simples:

Forma simples da operação de exponenciação

pode ser expresso assim pela recorrência:

Relação de recorrência para a operação de exponenciação

Mais difíceis

Depois que esses problemas simples forem mostrados E reimplementados nos tutoriais, você poderá dar exercícios um pouco mais difíceis (mas muito clássicos):

Nota: Novamente, alguns deles realmente não são mais difíceis ... Eles apenas abordam o problema exatamente do mesmo ângulo, ou um pouco diferente. Mas a prática leva à perfeição.


Ajudantes

Uma referência

Algumas leituras nunca são demais. Bem, a princípio será, e eles se sentirão ainda mais perdidos. É o tipo de coisa que cresce em você e fica na parte de trás da sua cabeça, até que um dia você percebe que finalmente entendeu. E então você pensa nessas coisas que lê. A recursão , a recursão em Ciência da Computação e as páginas de relação de recorrência na Wikipedia serviriam por enquanto.

Nível / profundidade

Supondo que seus alunos não tenham muita experiência em codificação, forneça stubs de código. Após as primeiras tentativas, ofereça a eles uma função de impressão que possa exibir o nível de recursão. Imprimir o valor numérico do nível ajuda.

O diagrama de empilhar como gavetas

Recuar um resultado impresso (ou a saída do nível) também ajuda, pois fornece outra representação visual do que seu programa está fazendo, abrindo e fechando contextos de pilha, como gavetas ou pastas em um explorador de sistemas de arquivos.

Acrônimos Recursivos

Se seu aluno já é um pouco versado na cultura da computação, ele pode já usar alguns projetos / softwares com nomes usando siglas recursivas . Tem sido uma tradição que existe há algum tempo, especialmente em projetos GNU. Alguns exemplos incluem:

Recursivo:

  • GNU - "GNU não é Unix"
  • Nagios - "Nagios não vai insistir na santidade"
  • PHP - "Pré-processador de hipertexto PHP" (e originall "Página inicial pessoal")
  • Vinho - "O vinho não é um emulador"
  • Zile - "O Zile é Emacs Perdido"

Mutuamente recursivo:

  • HURD - "HIRD de Daemons que Substituem o Unix" (onde HIRD é "HURD de Interfaces representando Profundidade")

Faça com que eles tentem criar seus próprios.

Da mesma forma, existem muitas ocorrências de humor recursivo, como a correção de pesquisa recursiva do Google . Para mais informações sobre recursão, leia esta resposta .


Armadilhas e Aprendizagem Adicional

Alguns problemas com os quais as pessoas geralmente enfrentam e para os quais você precisa saber respostas.

Por que, oh Deus, por que ???

Por que você faria isso? Uma razão boa, mas não óbvia, é que muitas vezes é mais simples expressar um problema dessa maneira. Um motivo não tão bom, mas óbvio, é que muitas vezes é preciso digitar menos (não faça com que se sintam muuuuitas apenas por usar recursão ...).

Alguns problemas são definitivamente mais fáceis de resolver ao usar uma abordagem recursiva. Normalmente, qualquer problema que você possa resolver usando o paradigma Divide and Conquer se ajustará a um algoritmo de recursão com várias ramificações.

O que há de novo N ??

Por que meu nou (qualquer que seja o nome da sua variável) é diferente toda vez? Os iniciantes geralmente têm problemas para entender o que são variáveis ​​e parâmetros e como as coisas nomeadas nem seu programa podem ter valores diferentes. Então agora, se esse valor está no loop de controle ou na recursão, é ainda pior! Seja gentil e não use os mesmos nomes de variáveis ​​em todos os lugares e deixe claro que os parâmetros são apenas variáveis .

Condições finais

Como determino minha condição final? Isso é fácil, basta que eles digam os passos em voz alta. Por exemplo, para o fatorial, comece de 5, depois 4, depois ... até 0.

O diabo está nos detalhes

Não fale com coisas anteriores, como otimização de chamada de cauda . Eu sei, sei, o TCO é bom, mas eles não se importam a princípio. Dê a eles algum tempo para entender o processo de uma maneira que funcione para eles. Sinta-se à vontade para destruir seu mundo novamente mais tarde, mas faça uma pausa.

Da mesma forma, não fale diretamente da primeira aula sobre a pilha de chamadas e seu consumo de memória e ... bem ... o estouro da pilha . Costumo dar aulas particulares a alunos que me mostram palestras onde eles têm 50 slides sobre tudo o que há para saber sobre recursão quando eles mal conseguem escrever um loop corretamente nesse estágio. Esse é um bom exemplo de como uma referência ajudará mais tarde, mas agora apenas o confunde profundamente.

Mas, por favor, no devido tempo, deixe claro que existem razões para seguir a rota iterativa ou recursiva .

Recursão mútua

Vimos que as funções podem ser recursivas e até podem ter vários pontos de chamada (8 rainhas, Hanói, Fibonacci ou até mesmo um algoritmo de exploração para um limpador de minas). Mas e as chamadas recursivas mutuamente ? Comece com a matemática aqui também. f(x) = g(x) + h(x)onde g(x) = f(x) + l(x)e he lapenas fazer coisas.

Começando com apenas séries matemáticas, é mais fácil escrever e implementar, pois o contrato é claramente definido pelas expressões. Por exemplo, as sequências femininas e masculinas de Hofstadter :

Sequências masculinas e femininas de Hofstadter

No entanto, em termos de código, é de notar que a implementação de uma solução mutuamente recursiva muitas vezes leva a codificar a duplicação e deve, antes, ser simplificados em uma única forma recursiva (Veja Peter Norvig 's Resolver cada quebra-cabeça Sudoku .

haylem
fonte
5
Estou lendo sua resposta depois de vê-la após quase 5 ou 6 vezes. Foi bom, mas muito longo para atrair outros usuários aqui, eu acho. Aprendi muitas coisas sobre o ensino da recursão aqui. Como professor, por favor, avalie minha ideia para ensinar recursion- programmers.stackexchange.com/questions/25052/…
Gulshan
9
@Gulshan, acho que essa resposta é tão abrangente quanto qualquer outra e é facilmente "desnatada" por um leitor casual. Por isso, recebe um static unsigned int vote = 1;de mim. Perdoe o humor estático, se quiser :) Esta é a melhor resposta até agora.
Tim Post
1
@ Gulsan: apenas quem quer aprender está disposto a tomar o tempo para fazer é corretamente :) Eu realmente não me importo. Às vezes, uma resposta curta é elegante e transmite muitas informações úteis e necessárias para começar ou explicar um conceito geral. Eu só queria uma resposta mais longa para essa e, considerando que o OP menciona uma pergunta para a qual eu recebi a resposta "correta" e faço uma pergunta semelhante, achei adequado fornecer o mesmo tipo de resposta. Que bom que você aprendeu alguma coisa.
haylem
@Gulshan: Agora, com relação à sua resposta: o primeiro ponto me confundiu bastante, devo dizer. Gosto que você descreva o conceito de funções recursivas como algo que muda de estado gradualmente ao longo do tempo, mas acho que sua maneira de apresentar é um pouco estranha. Depois de ler seus 3 pontos, eu não esperaria que muitos estudantes de repente consigam resolver Hanói. Mas pode ser apenas uma questão de redação.
haylem
Eu encontrei uma boa maneira de mostrar que a mesma variável pode ter valores diferentes em diferentes profundidades de recursão: considere os alunos anotando as etapas que estão seguindo e os valores das variáveis, seguindo algum código recursivo. Quando eles atingirem uma recursão, peça que eles comecem novamente em uma nova peça. Quando atingirem uma condição de saída, faça com que retornem à peça anterior. Isso é essencialmente emular uma pilha de chamadas, mas é uma boa maneira de mostrar essas diferenças.
Andy Hunt #
58

A chamada de uma função a partir dessa mesma função.

ChaosPandion
fonte
2
Esta é a melhor explicação para começar realmente. Simples e direto ao ponto; Depois de estabelecer este resumo, entre em todos os detalhes da viagem.
Jhocking
27

A recursão é uma função que se chama.

É importante saber como usá-lo, quando usá-lo e como evitar um design inadequado, o que exige que você experimente por si mesmo e entenda o que acontece.

A coisa mais importante que você precisa saber é ter muito cuidado para não obter um loop que nunca termine. A resposta do pramodc84 à sua pergunta tem a seguinte falha: Ela nunca termina ...
Uma função recursiva deve sempre verificar uma condição para determinar se deve se chamar novamente ou não.

O exemplo mais clássico para usar a recursão é trabalhar com uma árvore sem limites estáticos de profundidade. Esta é uma tarefa que você deve usar recursão.

admiração
fonte
Você ainda pode implementar seu último parágrafo de maneira iterativa, embora a recursividade seja obviamente melhor. "É importante saber como usá-lo, quando usá-lo e como evitar um design inadequado, o que exige que você experimente por si mesmo e entenda o que acontece." Eu pensei que o objetivo da pergunta era obter uma explicação para esse tipo de coisas.
haylem
@haylem: Você está certo sobre essa resposta ao "Como usá-lo, quando usá-lo e como evitar um design inadequado .." seria mais no local do que o OP solicita (não apenas "experimente por si mesmo" "como eu disse), mas isso exigiria uma palestra extensa do tipo mais didático, em vez de uma resposta rápida a uma pergunta aqui. Você fez um bom trabalho com sua resposta . +1 por isso ... Aqueles que realmente precisam entender melhor o conceito se beneficiarão da leitura de sua resposta.
temor
que tal um par de funções que se chamam? A chama B que chama A novamente até que alguma condição seja atingida. isso ainda será considerado recursão?
23412 santiagozky
Sim, a função aainda se chama, apenas indiretamente (chamando b).
Kindall
1
@santiagozky: Como todos disseram, ainda é recursão. No entanto, eu recomendaria não fazê-lo. Ao usar a recursão, deve ficar muito claro no código que a recursão está em vigor. Se se chamar indiretamente por meio de outra função, torna muito mais difícil ver o que está acontecendo. Se você não sabe que uma função se chama efetivamente, pode entrar na situação em que você (ou alguém que não criou essa função) quebra alguma condição para a recursão (enquanto altera a funcionalidade no código) e termina em um cadeado com um loop sem fim.
temor
21

A programação recursiva é o processo de reduzir progressivamente um problema para uma versão mais fácil de resolver.

Toda função recursiva tende a:

  1. faça uma lista para processar, ou alguma outra estrutura ou domínio do problema
  2. lidar com o ponto / etapa atual
  3. chama a si próprio no (s) restante (s) / subdomínio (s)
  4. combinar ou usar os resultados do trabalho do subdomínio

Quando a etapa 2 é anterior a 3 e a etapa 4 é trivial (concatenação, soma ou nada), isso permite a recursão da cauda . A etapa 2 geralmente deve ocorrer após a etapa 3, pois os resultados do (s) subdomínio (s) do problema podem ser necessários para concluir a etapa atual.

Faça a travessia de uma árvore binária direta. A travessia pode ser feita em pré-encomenda, ordem ou pós-encomenda, dependendo do que for necessário.

   B
A     C

Pré-encomenda: BAC

traverse(tree):
    visit the node
    traverse(left)
    traverse(right)

Em ordem: ABC

traverse(tree):
    traverse(left)
    visit the node
    traverse(right)

Pós-encomenda: ACB

traverse(tree):
    traverse(left)
    traverse(right)
    visit the node

Muitos problemas recursivos são casos específicos de uma operação de mapa ou uma dobra - entender apenas essas duas operações pode levar a um entendimento significativo de bons casos de uso para recursão.

Orbling
fonte
O principal componente da recursão prática é a idéia de usar a solução para um problema um pouco menor para resolver um problema maior. Caso contrário, você apenas terá uma recursão infinita.
Barry Brown
@ Barry Brown: Muito bem. Daí a minha declaração "... reduzindo um problema para mais fácil de resolver versões de si mesmo"
Orbling
Eu não diria necessariamente isso ... Geralmente, é o caso, especialmente em dividir e conquistar problemas ou em situações em que você realmente define uma relação de recorrência que se resume a um caso simples. Mas eu diria que é mais sobre provando que para cada iteração N do seu problema, há um caso computável N + 1.
haylem
1
@ Sean McMillan: A recursão é uma ferramenta poderosa quando usada em domínios adequados. Freqüentemente eu o vejo como uma maneira inteligente de lidar com uma questão relativamente trivial, que ofusca maciçamente a verdadeira natureza da tarefa em questão.
Orbling 13/09/11
20

O OP disse que a recursão não existe no mundo real, mas eu imploro para diferir.

Vamos dar uma 'operação' no mundo real de cortar uma pizza. Você tirou a pizza do forno e, para servi-la, você deve cortá-la ao meio, depois cortar as metades ao meio, e novamente cortar as metades resultantes ao meio.

A operação de cortar a pizza que você está executando repetidamente até obter o resultado desejado (o número de fatias). E por razões de argumento, digamos que uma pizza sem cortes é uma fatia em si.

Aqui está um exemplo em Ruby:

def cut_pizza (fatias existentes, fatias desejadas)
  if existing_slices! = selected_slices
    # ainda não temos fatias suficientes para alimentar todos, então
    # estamos cortando as fatias de pizza, dobrando seu número
    new_slices = existing_slices * 2 
    # e esta aqui é a chamada recursiva
    cut_pizza (novos_slices, desejados_slices)
  outro
    # temos o número desejado de fatias, então retornamos
    # aqui em vez de continuar recursando
    retornar existente_slices
  fim
fim

pizza = 1 # uma pizza inteira, 'uma fatia'
cut_pizza (pizza, 8) # => obteremos 8

Portanto, a operação no mundo real está cortando uma pizza e a recursão está fazendo a mesma coisa repetidamente até que você tenha o que deseja.

As operações que você descobrirá que podem ser implementadas com funções recursivas são:

  • Cálculo de juros compostos ao longo de vários meses.
  • Procurando um arquivo em um sistema de arquivos (porque os sistemas de arquivos são árvores por causa de diretórios).
  • Qualquer coisa que envolva trabalhar com árvores em geral, eu acho.

Eu recomendo escrever um programa para procurar um arquivo com base no nome do arquivo e tentar escrever uma função que se auto-identifique até ser encontrada, a assinatura terá a seguinte aparência:

find_file_by_name(file_name_we_are_looking_for, path_to_look_in)

Então você poderia chamar assim:

find_file_by_name('httpd.conf', '/etc') # damn it i can never find apache's conf

É simplesmente programar mecânica, na minha opinião, uma maneira de remover a duplicação de maneira inteligente. Você pode reescrever isso usando variáveis, mas esta é uma solução 'melhor'. Não há nada de misterioso ou difícil nisso. Você escreverá algumas funções recursivas, elas clicarão e farão outro truque mecânico em sua caixa de ferramentas de programação.

Crédito extra O cut_pizzaexemplo acima apresentará um erro muito profundo no nível da pilha se você solicitar um número de fatias que não seja uma potência de 2 (ou seja, 2 ou 4 ou 8 ou 16). Você pode modificá-lo para que, se alguém pedir 10 fatias, ele não funcione para sempre?

Ryan Allen
fonte
16

Ok, vou tentar manter isso simples e conciso.

Função recursiva são funções que se chamam. A função recursiva consiste em três coisas:

  1. Lógica
  2. Uma chamada para si mesma
  3. Quando terminar.

As melhores maneiras de escrever métodos recursivos é pensar no método que você está tentando escrever como um exemplo simples, manipulando apenas um loop do processo sobre o qual deseja iterar, depois adicionar a chamada ao próprio método e adicionar quando quiser terminar. A melhor maneira de aprender é praticar como todas as coisas.

Como este é o site dos programadores, evitarei escrever código, mas aqui está um bom link

se você entendeu essa piada, entendeu o que significa recursão.

dustyprogrammer
fonte
Veja também esta resposta: programmers.stackexchange.com/questions/25052/… (-:
Murph
4
Estritamente, a recursão não precisa de uma condição de terminação; garantir que a recursão seja encerrada limita os tipos de problemas que a função recursiva pode resolver e existem alguns tipos de apresentações semânticas que não exigem finalização.
Donal Fellows
6

A recursão é uma ferramenta que um programador pode usar para chamar uma chamada de função em si mesma. A sequência de Fibonacci é o exemplo de como a recursão é usada.

O código mais recursivo, se não todos, pode ser expresso como função iterativa, mas geralmente é confuso. Bons exemplos de outros programas recursivos são estruturas de dados, como árvores, árvore de pesquisa binária e até quicksort.

A recursão é usada para tornar o código menos desleixado, lembre-se de que geralmente é mais lento e requer mais memória.

Bryan Harrington
fonte
Se é mais lento ou requer mais memória, depende do uso em questão.
Orbling
5
O cálculo da sequência de Fibonacci é uma coisa terrível a se fazer recursivamente. A travessia de árvores é um uso muito mais natural da recursão. Normalmente, quando a recursão é usada bem, não é mais lenta e não requer mais memória, pois você teria que manter sua própria pilha em vez da pilha de chamadas.
David Thornley
1
@ Dave: Eu não contestaria isso, mas acho que Fibonacci é um bom exemplo para começar.
Bryan Harrington
5

Eu gosto de usar este:

Como você caminha até a loja?

Se você estiver na entrada da loja, basta passar por ela. Caso contrário, dê um passo e caminhe o resto até a loja.

É fundamental incluir três aspectos:

  • Um caso básico trivial
  • Resolvendo um pequeno pedaço do problema
  • Resolvendo o resto do problema recursivamente

Na verdade, usamos muito a recursão na vida diária; nós simplesmente não pensamos dessa maneira.

Barry Brown
fonte
Isso não é recursão. Seria se você o dividisse em dois: Ande pela metade do caminho até a loja, ande pela outra metade. Recurso.
2
Isso é recursão. Isso não é dividir e conquistar, mas é apenas um tipo de recursão. Os algoritmos de gráfico (como a localização de caminhos) estão cheios de conceitos recursivos.
deadalnix
2
Isso é recursão, mas considero um exemplo ruim, pois é muito fácil traduzir mentalmente "dê um passo e depois caminhe o resto do caminho até a loja" em um algoritmo iterativo. Eu sinto que isso é equivalente a converter um forloop bem escrito em uma função recursiva sem sentido.
27712 Brian
3

O melhor exemplo que eu apontaria para você é a linguagem de programação C da K&R. Nesse livro (e estou citando de memória), a entrada na página de índice para recursão (sozinha) lista a página real em que eles falam sobre recursão e a página de índice também.

Kanini
fonte
2

Josh K já mencionou as bonecas Matroshka . Suponha que você queira aprender algo que apenas a boneca mais pequena sabe. O problema é que você realmente não pode falar diretamente com ela, porque ela originalmente vive dentro da boneca mais alta que na primeira foto é colocada à esquerda. Essa estrutura continua assim (uma boneca mora dentro da boneca mais alta) até acabar apenas com a mais alta.

Portanto, a única coisa que você pode fazer é fazer sua pergunta para a boneca mais alta. A boneca mais alta (que não sabe a resposta) precisará passar sua pergunta para a boneca mais curta (que na primeira foto está à direita). Como ela também não tem a resposta, precisa pedir a próxima boneca mais curta. Isso continuará assim até que a mensagem chegue à boneca mais curta. A boneca mais curta (que é a única que sabe a resposta secreta) passará a resposta para a próxima boneca mais alta (encontrada à esquerda), que passará para a próxima boneca mais alta ... e isso continuará até a resposta chega ao seu destino final, que é a boneca mais alta e finalmente ... você :)

É isso que a recursão realmente faz. Uma função / método se chama até obter a resposta esperada. É por isso que quando você escreve um código recursivo, é muito importante decidir quando a recursão deve terminar.

Não é a melhor explicação, mas espero que ajude.

sakisk
fonte
2

Recursão n. - Um padrão de design de algoritmo em que uma operação é definida em termos de si mesma.

O exemplo clássico é encontrar o fatorial de um número, n !. 0! = 1, e para qualquer outro número natural N, o fatorial de N é o produto de todos os números naturais menores ou iguais a N. Portanto, 6! = 6 * 5 * 4 * 3 * 2 * 1 = 720. Esta definição básica permitiria criar uma solução iterativa simples:

int Fact(int degree)
{
    int result = 1;
    for(int i=degree; i>1; i--)
       result *= i;

    return result;
}

No entanto, examine a operação novamente. 6! = 6 * 5 * 4 * 3 * 2 * 1. Pela mesma definição, 5! = 5 * 4 * 3 * 2 * 1, o que significa que podemos dizer 6! = 6 * (5!). Por sua vez, 5! = 5 * (4!) E assim por diante. Ao fazer isso, reduzimos o problema a uma operação executada no resultado de todas as operações anteriores. Isso acaba se reduzindo a um ponto, chamado caso base, onde o resultado é conhecido por definição. No nosso caso, 0! = 1 (na maioria dos casos, também podemos dizer que 1! = 1). Na computação, geralmente temos permissão para definir algoritmos de maneira muito semelhante, fazendo com que o método se chame e passe uma entrada menor, reduzindo assim o problema através de muitas recursões para um caso base:

int Fact(int degree)
{
    if(degree==0) return 1; //the base case; 0! = 1 by definition
    else return degree * Fact(degree -1); //the recursive case; N! = N*(N-1)!
}

Isso pode, em muitos idiomas, ser simplificado ainda mais usando o operador ternário (às vezes visto como uma função Iif em idiomas que não fornecem o operador como tal):

int Fact(int degree)
{
    //reads equivalently to the above, but is concise and often optimizable
    return degree==0 ? 1: degree * Fact(degree -1);
}

Vantagens:

  • Expressão natural - para muitos tipos de algoritmos, essa é uma maneira muito natural de expressar a função.
  • LOC reduzido - geralmente é muito mais conciso definir uma função recursivamente.
  • Velocidade - Em certos casos, dependendo da linguagem e da arquitetura do computador, a recursão de um algoritmo é mais rápida que a solução iterativa equivalente, geralmente porque fazer uma chamada de função é uma operação mais rápida no nível do hardware do que as operações e o acesso à memória necessários para fazer um loop iterativo.
  • Divisibilidade - Muitos algoritmos recursivos são da mentalidade "dividir e conquistar"; o resultado da operação é uma função do resultado da mesma operação realizada em cada uma das duas metades da entrada. Isso permite dividir o trabalho em dois em cada nível e, se disponível, você pode dar a outra metade para outra "unidade de execução" para processar. Isso geralmente é mais difícil ou impossível com um algoritmo iterativo.

Desvantagens:

  • Requer entendimento - Você simplesmente deve "entender" o conceito de recursão para entender o que está acontecendo e, portanto, escrever e manter algoritmos recursivos eficazes. Caso contrário, apenas parece magia negra.
  • Dependente do contexto - se a recursão é uma boa ideia ou não depende de quão elegantemente o algoritmo pode ser definido em termos de si mesmo. Embora seja possível criar, por exemplo, um SelectionSort recursivo, o algoritmo iterativo é tipicamente o mais compreensível.
  • Troca o acesso à RAM pela pilha de chamadas - Normalmente, as chamadas de função são mais baratas que o acesso ao cache, o que pode tornar a recursão mais rápida que a iteração. Porém, geralmente há um limite para a profundidade da pilha de chamadas que pode causar erros de recursão nos casos em que um algoritmo iterativo funcionará.
  • Recursão infinita - Você precisa saber quando parar. A iteração infinita também é possível, mas as construções de loop envolvidas geralmente são mais fáceis de entender e, portanto, depurar.
KeithS
fonte
1

O exemplo que eu uso é um problema que enfrentei na vida real. Você tem um contêiner (como uma mochila grande que pretende levar em uma viagem) e deseja saber o peso total. Você tem no contêiner dois ou três itens soltos e outros contêineres (por exemplo, sacos de material). O peso do contêiner total é obviamente o peso do contêiner vazio mais o peso de tudo o que está nele. Para os itens soltos, você pode apenas pesá-los, e para os sacos de material, você pode apenas pesá-los ou você pode dizer "bem, o peso de cada saco de material é o peso do contêiner vazio, mais o peso de tudo nele". E então você continua entrando em contêineres em contêineres e assim por diante até chegar a um ponto em que existem apenas itens soltos em um contêiner. Isso é recursão.

Você pode pensar que isso nunca acontece na vida real, mas imagine tentar contar ou somar os salários de pessoas de uma empresa ou divisão específica, que tem uma mistura de pessoas que apenas trabalham para a empresa, pessoas em divisões e depois em as divisões existem departamentos e assim por diante. Ou vendas em um país que possui regiões, algumas das quais com sub-regiões, etc. etc. Esse tipo de problema ocorre o tempo todo nos negócios.

Kate Gregory
fonte
0

A recursão pode ser usada para resolver muitos problemas de contagem. Por exemplo, digamos que você tenha um grupo de n pessoas em uma festa (n> 1) e todo mundo aperta a mão de todo mundo exatamente uma vez. Quantos apertos de mão ocorrem? Você pode saber que a solução é C (n, 2) = n (n-1) / 2, mas você pode resolver recursivamente da seguinte maneira:

Suponha que haja apenas duas pessoas. Então (por inspeção) a resposta é obviamente 1.

Suponha que você tenha três pessoas. Escolha uma pessoa e observe que ele / ela aperta a mão de duas outras pessoas. Depois disso, você deve contar apenas os apertos de mão entre as outras duas pessoas. Já fizemos isso agora e é 1. Portanto, a resposta é 2 + 1 = 3.

Suponha que você tenha n pessoas. Seguindo a mesma lógica de antes, é (n-1) + (número de apertos de mão entre n-1 pessoas). Expandindo, obtemos (n-1) + (n-2) + ... + 1.

Expressa como uma função recursiva,

f (2) = 1
f (n) = n-1 + f (n-1), n> 2

Mitch Schwartz
fonte
0

Na vida (ao contrário de um programa de computador), a recursão raramente acontece sob nosso controle direto, porque pode ser confuso fazer isso acontecer. Além disso, a percepção tende a ser sobre os efeitos colaterais, em vez de ser funcionalmente pura; portanto, se a recursão estiver acontecendo, você poderá não perceber.

A recursão acontece aqui no mundo. Muito.

Um bom exemplo é (uma versão simplificada) do ciclo da água:

  • O sol aquece o lago
  • A água sobe para o céu e forma nuvens
  • As nuvens flutuam até uma montanha
  • Na montanha, o ar fica frio demais para reter sua umidade
  • Chuva caindo
  • Forma-se um rio
  • A água do rio corre para o lago

Este é um ciclo que faz com que ele se repita. É recursivo.

Outro lugar onde você pode obter recursão é em inglês (e no idioma humano em geral). Você pode não reconhecê-lo no início, mas a maneira como podemos gerar uma sentença é recursiva, porque as regras nos permitem incorporar uma instância de um símbolo ao lado de outra instância do mesmo símbolo.

De The Language Instinct, de Steven Pinker:

se a menina come sorvete ou a menina come doces, o menino come cachorro-quente

Essa é uma frase inteira que contém outras frases inteiras:

a menina come sorvete

a menina come doce

o menino come cachorro-quente

O ato de entender a sentença completa envolve a compreensão de sentenças menores, que usam o mesmo conjunto de truques mentais para serem entendidas como sentença completa.

Para entender a recursão da perspectiva da programação, é mais fácil olhar para um problema que pode ser resolvido com recursão e entender por que deveria ser e o que isso significa que você precisa fazer.

Para o exemplo, usarei a maior função divisor comum, ou gcd, para abreviar.

Você tem seus dois números ae b. Para encontrar o MDC (assumindo que nenhum é 0), você precisa verificar se aé igualmente divisível em b. Se for então, bé o gcd, caso contrário, você precisa verificar o gcd de be o restante de a/b.

Você já deve conseguir ver que essa é uma função recursiva, pois você tem a função gcd chamando a função gcd. Apenas para martelá-lo em casa, aqui está em c # (novamente, assumindo que 0 nunca seja passado como parâmetro):

int gcd(int a, int b)
{   
    if (a % b == 0) //this is a stopping condition
    {
        return b;
    }

    return (gcd(b, a % b)); //the call to gcd here makes this function recursive
}

Em um programa, é importante ter uma condição de parada, caso contrário, sua função ocorrerá para sempre, o que acabará causando um estouro de pilha!

O motivo para usar a recursão aqui, em vez de um loop while ou alguma outra construção iterativa, é que, enquanto você lê o código, ele diz o que está fazendo e o que acontecerá a seguir, tornando mais fácil descobrir se está funcionando corretamente. .

Matt Ellen
fonte
1
Eu achei o exemplo do ciclo da água iterativo. O segundo exemplo de linguagem parece mais dividir e conquistar do que recursão.
precisa
@Gulshan: eu diria que o ciclo da água é recursivo porque faz com que ele se repita, como uma função recursiva. Não é como pintar uma sala, onde você executa os mesmos passos sobre vários objetos (paredes, teto etc.), como em um loop for. O exemplo da linguagem usa dividir e conquistar, mas também a "função" chamada se autodenomina para trabalhar nas sentenças aninhadas; portanto, é recursiva dessa maneira.
Matt Ellen
No ciclo da água, o ciclo é iniciado pelo sol e nenhum outro elemento do ciclo está fazendo com que o sol o inicie novamente. Então, onde está a chamada recursiva?
precisa
Não há uma chamada recursiva! Não é uma função. : D É recursivo porque faz com que ele se repita. A água do lago volta ao lago e o ciclo recomeça. Se algum outro sistema estivesse colocando água no lago, seria iterativo.
Matt Ellen
1
O ciclo da água é um loop while. Certamente, um loop while pode ser expresso usando recursão, mas isso acabará com a pilha. Por favor não.
27712 Brian
0

Aqui está um exemplo do mundo real para recursão.

Deixe-os imaginar que têm uma coleção de quadrinhos e você misturará tudo em uma grande pilha. Cuidado - se eles realmente tiverem uma coleção, poderão matá-lo instantaneamente quando você mencionar a idéia de fazê-lo.

Agora, deixe-os ordenar essa grande pilha de quadrinhos sem classificação com a ajuda deste manual:

Manual: How to sort a pile of comics

Check the pile if it is already sorted. If it is, then done.

As long as there are comics in the pile, put each one on another pile, 
ordered from left to right in ascending order:

    If your current pile contains different comics, pile them by comic.
    If not and your current pile contains different years, pile them by year.
    If not and your current pile contains different tenth digits, pile them 
    by this digit: Issue 1 to 9, 10 to 19, and so on.
    If not then "pile" them by issue number.

Refer to the "Manual: How to sort a pile of comics" to separately sort each
of the new piles.

Collect the piles back to a big pile from left to right.

Done.

O mais interessante aqui é: quando eles têm problemas únicos, eles têm o "quadro de pilha" completo com as pilhas locais visíveis antes deles no chão. Dê a eles várias impressões do manual e coloque uma de cada nível de pilha com uma marca em que você está atualmente neste nível (ou seja, o estado das variáveis ​​locais), para que você possa continuar lá em cada Concluído.

É disso que se trata basicamente a recursão: executar o mesmo processo, apenas em um nível de detalhe mais fino, quanto mais você entrar nele.

Seguro
fonte
-1
  • Terminar se a condição de saída for atingida
  • faça algo para alterar o estado das coisas
  • fazer o trabalho todo começando com o estado atual das coisas

A recursão é uma maneira muito concisa de expressar algo que precisa ser repetido até que algo seja alcançado.

vpit3833
fonte
-2

Uma boa explicação da recursão é literalmente "uma ação que se repete a partir de si mesma".

Considere um pintor pintando uma parede, é recursivo porque a ação é "pintar uma faixa do teto ao chão do que deslizar um pouco para a direita e (pintar uma faixa do teto ao chão do que deslizar um pouco para a direita e (pintar uma tira do teto ao chão do que deslize um pouco para a direita e (etc))) ".

Sua função paint () chama a si mesma repetidamente para compor sua função paint_wall () maior.

Espero que este pobre pintor tenha algum tipo de condição de parada :)

Dan1ell
fonte
6
Para mim, o exemplo parece mais um procedimento iterativo, não recursivo.
precisa
@Gulshan: Recursão e iteração fazem coisas semelhantes, e muitas vezes as coisas funcionam bem com elas. Os idiomas funcionais geralmente usam recursão em vez de iteração. Existem melhores exemplos de recursão em que seria estranho escrever a mesma coisa iterativamente.
David Thornley