Recursão - é "dividir e conquistar" ou "reutilização de código"

11

A recursão - como todos sabemos - é um desses problemas - que envolver sua cabeça parece alcançar um "marco" em sua viagem de programação.

Mas quando se trata de realmente usá-lo em problemas do mundo real - conhecer a mecânica da recursão NÃO é suficiente - é preciso também entender a natureza dos problemas em que a recursão é a solução mais adequada.

Então, minha pergunta é esta ...

  • quais são os "padrões de problemas" que exigem a solução da recursão
  • recursão é uma forma de estratégia "dividir e conquistar" ou uma forma de "reutilização de código" - ou é um padrão de design por si só
  • você pode nos dar um exemplo de um problema do mundo real em que a recursão vem à mente como uma solução imediata

- ATUALIZAÇÃO -

muitas respostas estão se referindo a "problemas reais" como atravessar árvores, fatorial etc. Eu preferiria "os problemas reais REAIS" - deixe-me dar um exemplo ...

Tínhamos uma grande quantidade de texto (cerca de 30 MB de texto como uma lista vinculada structs) e precisávamos fazer um índice para pesquisa de texto completo. Precisávamos manter o índice inteiro na memória e indexar novamente o texto a cada 10 minutos.

A cada 10 minutos, comparávamos o texto inteiro (duas listas vinculadas, linha por linha) com um pedaço de texto recém-gerado - para ver qual linha foi alterada - e então reindexamos apenas essa linha - dessa maneira poderíamos evitar ter que indexar novamente o texto INTEIRO. Lembre-se - precisávamos encontrar os pontos de diferença entre duas listas vinculadas de 30 MB.

Um dos meus colegas criou um programa fantástico que usava recursão PESADA para comparar as linhas - e depois coletar as posições em que os mandris diferiam em uma matriz - sim, eu sei que parece intrigante - como a recursão poderia ajudar aqui - mas fez.

A questão é: como ele pôde ver que esse problema poderia ser resolvido de maneira inteligente com o uso pesado de recursão?

recursion codificador de árvore
fonte
Atualmente, são 30 MB realmente grandes em que a maioria dos computadores possui GB de RAM e TB de espaço no disco rígido?
JB King
30 MB NÃO podem ser grandes - mas, considerando o tipo de estrutura de dados em que nosso texto foi inserido -, foi realmente uma GRANDE porção de texto para PROCESS - e DIFF.
treecoder
3
“Atravessar uma estrutura de pastas” não é REAL o suficiente? E falho completamente em ver, no seu exemplo, como a recursão deve ser não intuitiva aqui e por que seu uso deve ser particularmente notável. Seu colega projetou um algoritmo recursivo, como qualquer outro algoritmo. Você também pode perguntar como Hoare teve a ideia de resolver o problema de classificação recursivamente.
21411 Konrad Rudolph
2
Estou certo ao pensar que você quis dizer "reutilização de código" mais como "executar a mesma série de operações um número indeterminado de vezes"? Isso é o contrário de "reutilização de código" no sentido de escrever código genérico para uso em outros lugares.
Andy Hunt
4
Mas a travessia de árvores é um "verdadeiro problema REAL", que muitas pessoas encontram quase que diariamente.
Falcon

Respostas:

16
  • quais são os "padrões de problemas" que exigem a solução da recursão

Eu não diria que existe um padrão de problema para o uso da recursão. Toda função que pode ser implementada com recursão também pode ser implementada iterativamente, geralmente pressionando e popping uma pilha.

É uma questão de expressão e também de desempenho. Os algoritmos iterativos costumam ter um desempenho melhor e são mais fáceis de otimizar. No entanto, algoritmos recursivos se beneficiam de uma expressão mais clara e, portanto, geralmente são mais fáceis de ler, entender e implementar.

Algumas coisas ainda não podem ser expressas sem recursão, listas infinitas, por exemplo. As chamadas linguagens funcionais dependem fortemente da recursão, pois é seu modo natural de expressão. O ditado é: "Programação recursiva é programação funcional feita corretamente".

  • recursão é uma forma de estratégia "dividir e conquistar" ou uma forma de "reutilização de código" - ou é um padrão de design por si só

Eu não chamaria isso de padrão de design. É uma questão de expressão. Às vezes, uma expressão recursiva é simplesmente mais poderosa e mais expressiva e, portanto, leva a um código melhor e mais limpo.

  • você pode nos dar um exemplo de um problema do mundo real em que a recursão vem à mente como uma solução imediata

Qualquer coisa que precise atravessar árvores será adequadamente expressa por um algoritmo recursivo.

Falcão
fonte
7
"Todas as funções que podem ser implementadas com recursão também podem ser implementadas iterativamente, geralmente pressionando e estourando uma pilha". Afinal, em idiomas que utilizam memória baseada em pilha, você já está pressionando e ativando os dados da função dentro e fora da pilha ao usar a recursão.
JAB
Somente se você compilar ou interpretar o idioma por uma máquina ;-) Além disso, de um ponto de vista muito alto, a expressão e o idioma são completamente independentes da máquina e do hardware e do sistema operacional; portanto, não há necessariamente uma pilha.
Falcon
Ah, sim, você está absolutamente certo. Eu deveria ter dito "em implementações de linguagens / compiladores de linguagem que utilizam memória baseada em pilha".
JAB
De um modo geral, você também está certo. Eu não queria aparecer.
Falcon
2
Listas infinitas podem ser expressas sem recursão, pelo menos sem uma implementação recursiva. Os geradores Python podem fazer isso, assim como os geradores em Icon dos quais Python parece ter emprestado a idéia. Acredito que o F # possa fazer esse truque, embora não tenha certeza. Basicamente, os geradores são um caso especial de co-rotinas (como multitarefa cooperativa) que são adequadas para a implementação de listas lentas. Cada vez que um gerador "produz" um resultado, o chamador recupera o controle e o gerador permanece ocioso até o próximo resultado ser solicitado.
Steve314
8

recursão é uma forma de estratégia "dividir e conquistar" ou uma forma de "reutilização de código" - ou é um padrão de design por si só

Nem. Dividir e conquistar usa recursão. Mas a recursão não é necessariamente dividir e conquistar, pois a última significa dividir um problema em duas (ou mais) partes e resolver cada uma delas simetricamente. Na recursão, você não faz isso.

A reutilização de código é completamente independente, e um padrão de design entra em jogo em um nível muito mais alto. Por exemplo, até dividir e conquistar (também um padrão de nível superior ao da recursão) ainda não é considerado um padrão de design - é um padrão algorítmico .

você pode nos dar um exemplo de um problema do mundo real em que a recursão vem à mente como uma solução imediata

Travessia de árvore. Ou, geralmente, o gráfico é transversal. Isso inclui atravessar uma estrutura de pastas.

E, claro, qualquer coisa que use dividir e conquistar ou programação dinâmica, pois ambas são naturalmente expressas em termos de recursão.

Konrad Rudolph
fonte
A programação dinâmica nem sempre é expressa naturalmente como recursão. De fato, a programação dinâmica se refere estritamente a abordagens tabulares - excluindo a memorização. As opiniões parecem variar sobre isso, mas a "programação" na "programação dinâmica" é na verdade um termo matemático, referindo-se a abordagens tabulares (uma parte da trivialidade que aprendi no curso de algoritmos de código aberto do MIT). Portanto, estritamente, a programação dinâmica explora a subestrutura ideal usando o que geralmente é mais facilmente expresso como um loop simples. É muito mais provável que a memorização implique recursão, mas não necessariamente.
Steve314
1
@ Steve314 Concordo que a implementação prática do DP (seja em um programa de computador ou manualmente) raramente usa recursão. Mas a ideia é inerentemente baseada em uma relação de recorrência - que é apenas uma fórmula recursiva! - e um estojo básico.
Konrad Rudolph
Concordo que a "subestrutura ideal" (uma solução ótima tem soluções parciais ótimas) é uma idéia recursiva. Essa é uma visão da matemática / ciência da computação da recursão, não relacionada diretamente à implementação - mas o papel da recursão na ciência da computação é um ponto importante a ser destacado. Poucos algoritmos (e provavelmente nenhum padrão de design) são ferramentas importantes na ciência da computação - a maioria são assuntos puramente para estudar, em vez de ferramentas para serem usadas no estudo de outra coisa.
Steve314
4 
what are the "problem patterns" that call for the solution of recursion

Derivado da auto-similaridade dos fractais, eu diria que a auto-igualdade ou a auto-identidade (ou como é chamada) é um padrão típico de problema para recursão. Ou seja, um problema pode ser dividido em subproblemas que têm a mesma estrutura do problema principal.

No percurso da árvore mencionado, cada subárvore é uma árvore completa em si mesma, assim como a árvore principal, e a árvore principal pode ser uma subárvore dentro de outra árvore.

Então, acho que seu colega descobriu as propriedades de auto-igualdade do seu problema de indexação. Ou ele fez o contrário e transformou o problema em uma representação auto-igual.

Seguro
fonte
1
+1 para "um problema pode ser dividida em sub-problemas que têm a mesma estrutura como o principal problema"
treecoder
+1 e parafrasear: onde a solução do problema se aplica às camadas filho. Meu exemplo do mundo real é encontrar cobranças de cartão de crédito que contribuem para um "lote". O software de contabilidade terá os encargos individuais e o depósito em lote na conta corrente. Meu caso pode se tornar uma pergunta aqui, pois o fluxo de pilha não foi muito nítido. stackoverflow.com/questions/14719806
Chris K
3

Bem, a recursão pode ser entendida facilmente se alguém tentar transformar loops imperativos em funções funcionais. De qualquer forma, vamos tentar responder a todas as perguntas:

quais são os "padrões de problemas" que exigem a solução da recursão

Se você tiver uma estrutura ou algoritmo semelhante a uma árvore, precisará de recursão. Se o seu código imperativo lida com uma pilha, você precisará de recursão. Se uma determinada etapa do seu algoritmo depende das etapas anteriores (pense em loops), você precisa de recursão. A necessidade aqui deve ser interpretada como pode ser usada.

recursão é uma forma de estratégia "dividir e conquistar" ou uma forma de "reutilização de código" - ou é um padrão de design por si só

Nenhum. Dividir e conquistar usa recursão, mas pode ser implementado com pilhas. A reutilização de código refere-se a outra coisa. Os padrões de design são mais complicados que a simples recursão.

você pode nos dar um exemplo de um problema do mundo real em que a recursão vem à mente como uma solução imediata

Análise e tudo o que lida com estruturas de árvores. Até estruturas de árvore implícitas.

Mihai Maruseac
fonte
3

Se existe uma maneira de simplificá-lo para que seja fácil, essa pode ser a pista de que a recursão poderia funcionar. Você pode classificar e procurar exemplos onde existem soluções recursivas, como Merge Sort e Binary Search, respectivamente.

Algo a ter em mente é como alguns problemas podem ser mal resolvidos com recursão como um fatorial.

Quanto a um exemplo do mundo real em que eu usaria recursão, procurar um livro de uma estante de livros pode ser feito com muita facilidade de maneira recursiva. Eu apenas olho para o livro e, se não é o que eu quero, passo para o próximo. Paro quando encontro o livro ou chego ao fim da fila. O loop na verificação de um livro e na passagem para o próximo poderia ser feito recursivamente. Talvez isso seja um exemplo muito real.

JB King
fonte
2

quais são os "padrões de problemas" que exigem a solução da recursão

Em termos muito gerais, a recursão é necessária quando você está resolvendo um problema em que f (x) = f (g (x)) . A menos que você esteja bem com a recursão infinita, g (x) não deve ser avaliado como x .

recursão é uma forma de estratégia "dividir e conquistar" ou uma forma de "reutilização de código" - ou é um padrão de design por si só

Nenhuma das acima. É apenas uma maneira de fazer a mesma coisa repetidamente, às vezes com base em variações na entrada. O conceito existe há muito mais tempo do que padrões de design, reutilização de código ou até mesmo computadores.

você pode nos dar um exemplo de um problema do mundo real em que a recursão vem à mente como uma solução imediata

Fatoriais, a seqüência de Fibonacci, a travessia de árvores e muitos outros problemas podem ser resolvidos com a recusa. A recursão no sentido de uma função se chamar não é necessariamente a melhor maneira de implementar esse tipo de coisa; existem outras maneiras de obter o mesmo efeito (por exemplo, uma pilha e um loop) que podem ser mais desejáveis.

Blrfl
fonte
-1

Quando você escreve um algoritmo recursivo, geralmente traduz uma definição recursiva do problema no código. Então você nem precisa saber como será executado.

É o que acontece na programação funcional. De fato, você especifica o que (definição) e não como . Em outras palavras, você define a base e, em seguida, define seu problema no termo de um subproblema.

Por exemplo, considere o Factorialalgoritmo

  • Defina a base: Fatorial (1) = 1;
  • Definir fatorial n: fatorial (n) = n * fatorial (n-1);

Então, quando você encontrar um problema, pense se você pode defini-lo recursivamente ou não, se você pode defini-lo recursivamente, você quase o resolveu.

No entanto, qualquer função recursiva não deve ser uma definição recursiva. Você pode definir a base e relacionar (definir) a solução do problema principal à solução (definição) de subproblemas. Mas, para essa relação, você pode precisar de um procedimento.

Um exemplo é o MergeSortqual mergepoderia ser um procedimento imperativo para relacionar a definição ou solução de classificação de toda a matriz com a classificação das sub-matrizes.

Ahmad
fonte