Recursos para melhorar sua compreensão de recursão? [fechadas]

13

Eu sei o que é recursão (quando um patten se repete dentro de si, normalmente uma função que se chama em uma de suas linhas, após uma fuga condicional ... certo?), E posso entender funções recursivas se as estudar de perto. Meu problema é que, quando vejo novos exemplos, estou sempre inicialmente confuso. Se eu vejo um loop, ou um mapeamento, zipagem, aninhamento, chamada polimórfica e assim por diante, eu sei o que está acontecendo apenas olhando para ele. Quando vejo código recursivo, meu processo de pensamento geralmente é 'wtf is this?' seguido por 'oh, é recursivo', seguido por 'acho que deve funcionar, se eles dizem que funciona'.

Você tem dicas / planos / recursos para desenvolver habilidades nessa área? A recursão é meio que um conceito estranho, então estou pensando que a maneira de enfrentá-la pode ser igualmente estranha e inofensiva.

Andrew M
fonte
28
Para entender recursão, você deve primeiro entender a recursão.
Andreas Johansson
1
"O gato de chapéu volta", do Dr. Seuss, isso pode não ser totalmente útil, mas a chamada recursiva do gato se livra dessa mancha traquina. :-) Também tem o benefício de ser uma leitura muito rápida!
DKnight
2
Prática, prática, prática.
David Thornley
20
Já respondeu a esta pergunta: programmers.stackexchange.com/questions/57243/…
Graham Borland
3
@ Graham Borland: Esse é um exemplo de recursão infinita. Na maioria dos programas, a falta do caso base geralmente resulta em um estouro de pilha ou erro de falta de memória. Para os usuários do site, isso pode resultar em confusão. ;)
FrustratedWithFormsDesigner

Respostas:

10

Comece com algo simples e trace-o com lápis e papel. Seriosuly. Um bom lugar para começar são os algoritmos de passagem em árvore, pois eles são muito mais facilmente manipulados usando recursão do que a iteração regular. Não precisa ser um exemplo complicado, mas algo simples e com o qual você pode trabalhar.

Sim, é estranho e, às vezes, contra-intuitivo, mas quando clica, você diz "Eureka!" você se perguntará como não o entendeu antes! ;) Sugeri árvores porque elas são (IMO) a estrutura mais fácil de entender em recursão e são fáceis de trabalhar usando lápis e papel. ;)

FrustratedWithFormsDesigner
fonte
1
+1 foi dessa maneira que eu gritei. por exemplo, se você estiver usando OO, faça algumas classes com um relacionamento pai-filho e tente criar uma função / método que verifique se um objeto tem um ancestral específico.
Alb
5

Eu recomendo fortemente o Scheme, usando o livro The Little Lisper. Depois que você fez com ele, você vai entender recursão, no fundo. Quase garantido.

jcomeau_ictx
fonte
1
+1 Este livro realmente fez isso por mim. Mas foi renomeado para "The Little Schemer"
mike30 15/04/2013
4

Definitivamente, sugiro o SICP. Além disso, você deve conferir os vídeos do curso introdutório dos autores aqui ; eles são incrivelmente inovadores.

Outra estrada, não tão estritamente relacionada à programação, é ler Gödel, Escher, Bach: uma trança dourada eterna de Hofstadter. Quando você passar por isso, a recursão parecerá tão natural quanto a aritmética. Além disso, você estará convencido de que P = nP e desejará construir máquinas pensantes - mas é um efeito colateral tão pequeno quando comparado aos benefícios.

cbrandolino
fonte
GEB vale a pena ler de qualquer maneira; mesmo que algumas das coisas sobre as quais ele fala estejam um pouco datadas (algum progresso na pesquisa fundamental em CS foi feito nos últimos 40 anos), o entendimento básico não é.
Donal Fellows
2

Basicamente, tudo se resume à prática ... Pegue problemas gerais (classificação, pesquisa, problemas de matemática etc.) e veja se você consegue ver uma maneira pela qual esses problemas podem ser resolvidos se você aplicar uma única função várias vezes.

Por exemplo, a ordenação rápida opera na medida em que move o elemento em uma lista para duas metades e depois se aplica novamente a cada uma dessas metades. Quando a classificação inicial ocorre, não se preocupa em obter as duas metades classificadas nesse ponto. Em vez disso, é pegar o elemento pivô e colocar todos os elementos menores que esse elemento em um lado e todos os elementos maiores ou iguais ao outro lado. Isso faz sentido como ele pode se chamar recursivamente nesse ponto para classificar as duas novas listas menores? São listas também. Apenas menor. Mas eles ainda precisam ser classificados.

O poder por trás da recursão é a noção de dividir e conquistar. Divida um problema repetidamente em problemas menores, de natureza idêntica, mas apenas menores. Se você fizer isso o suficiente, eventualmente, chegará a um ponto em que a única peça restante já está resolvida, então você simplesmente retornará do circuito e o problema será resolvido. Estude os exemplos que você mencionou até entendê- los. Pode demorar um pouco, mas eventualmente ficará mais fácil. Em seguida, tente resolver outros problemas e faça uma função recursiva para resolvê-los! Boa sorte!

EDIT: Também devo acrescentar que um elemento-chave da recursão é a capacidade garantida da função de poder parar. Isso significa que a quebra do problema original deve diminuir continuamente e, eventualmente, é necessário um ponto de parada garantido (um ponto no qual o novo subproblema é solucionável ou já foi resolvido).

Kenneth
fonte
Sim, acho que já vi uma explicação rápida, antes, posso imaginar como isso funciona a partir do seu lembrete acima. Quão expressiva / flexível é a recursão - a maioria dos problemas pode ser coagida a uma abordagem recursiva (mesmo que não seja ótima)? Eu já vi pessoas responderem quebra-cabeças de codificação na rede que a maioria das pessoas estava enfrentando de maneira processual, como se pudessem usar a recursão sempre que quisessem. Também li uma vez, acho que algumas linguagens dependem ou recursão para substituir a construção do loop. E você menciona o ponto de parada garantido. Eu sinto que uma dessas coisas pode ser a chave.
Andrew M
Um bom problema inicial simples para você criar por si mesmo seria escrever um programa recursivo que encontre o fatorial de um número.
23911 Kenneth
Qualquer estrutura de loop pode ser colocada em uma estrutura recursiva. Qualquer estrutura recursiva pode ser colocada em uma estrutura em loop ... mais ou menos. Leva tempo e prática para poder aprender quando e quando não usar a recursão, porque você deve se lembrar de que, ao usar a recursão, há muita sobrecarga em termos de recursos usados ​​no nível do hardware.
21411 Kenneth
Por exemplo, eu via que é viável criar uma estrutura em loop que executa uma classificação rápida ... Mas com certeza seria uma dor real e, dependendo de como isso foi feito, poderia usar mais recursos do sistema no final do que uma função recursiva para matrizes grandes.
22411 Kenneth
então aqui está minha tentativa de fatorial. para ser justo, já vi isso antes e, embora tenha escrito do zero, não da memória, provavelmente ainda é mais fácil do que teria sido. Tentou fazê-lo em JS, mas tinha um erro de análise, mas funciona em Python def factorial(number): """return factorial of number""" if number == 0: return 0 elif number == 1: return 1 else: return number * factorial(number - 1)
Andrew M
2

Pessoalmente, acho que sua melhor aposta é através da prática.

Eu aprendi recursão com o LOGO. Você poderia usar o LISP. A recursão é natural nesses idiomas. Caso contrário, você pode compará-lo ao estudo de suítes e séries matemáticas nas quais você expressa o que vem a seguir com base no que veio antes, ou seja, u (n + 1) = f (u (n)) ou séries mais complexas nas quais você tem várias variáveis ​​e múltiplas dependências, por exemplo, u (n) = g (u (n-1), u (n-2), v (n), v (n-1)); v (n) = h (u (n-1), u (n-2), v (n), v (n-1)) ...

Portanto, minha sugestão seria que você encontrasse "problemas" simples (na expressão deles) de recursão padrão e tente implementá-los no idioma de sua escolha. A prática o ajudará a aprender a pensar, ler e expressar esses "problemas". Observe que muitas vezes alguns desses problemas podem ser expressos por meio da iteração, mas a recursão pode ser uma maneira mais elegante de resolvê-los. Um deles é o cálculo dos números fatoriais.

Acho que "problemas" gráficos facilitam a visualização. Portanto, procure os flocos de Koch, Fibonacci, a curva do dragão e os fractais em geral. Mas também veja o algoritmo de classificação rápida ...

Você precisa travar alguns programas (loops infinitos, uso provisório de recursos infinitos) e manipular mal as condições finais (para obter resultados inesperados) antes de resolver tudo isso. E mesmo quando você conseguir, ainda cometerá esses erros, apenas com menos frequência.

asoundmove
fonte
2

Estrutura e interpretação de programas de computador

É o livro usado para aprender, não apenas a recursão, mas a programação em geral em várias universidades. É um daqueles livros fundamentais que fornece mais informações, quanto mais você ganha e mais lê.

dietbuddha
fonte
0

Por mais que eu goste do SICP e Gödel, Escher, Bach: uma trança dourada eterna , o LISP de Touretzky : uma introdução suave à computação simbólica também faz um bom trabalho ao introduzir recursão.

O conceito básico é este: primeiro, você precisa saber quando sua função recursiva está concluída, para que possa retornar um resultado. Então, você precisa saber como levar o caso inacabado e reduzi-lo a algo em que possa recorrer. Para o exemplo fatorial tradicional (N), você termina quando N <= 1, e o caso inacabado é N * fatorial (N-1).

Para um exemplo muito mais feio, há a função A de Ackermann (m, n).

A(0,n) = n+1.                                   This is the terminal case.
A(m,0) = A(m-1,1) if m > 0.                     This is a simple recursion.
A(m,n) = A(m-1, A(m, n-1)) if m > 0 and n > 0.  This one is ugly.
John R. Strohm
fonte
0

Sugiro brincar com algumas linguagens funcionais no estilo ML, como OCaml ou Haskell. Descobri que a sintaxe de correspondência de padrões realmente me ajudou a entender funções recursivas ainda relativamente complicadas, certamente muito melhores do que as de Scheme ife das conddeclarações. (Aprendi Haskell e Scheme ao mesmo tempo.)

Aqui está um exemplo trivial de contraste:

(define (fib n)
   (cond [(= n 0) 0]
         [(= n 1) 1]
         [else (+ (fib (- n 1)) (fib (- n 2)))]))

e com correspondência de padrões:

fib 0 = 0
fib 1 = 1
fib n = fib (n - 1) + fib (n - 2)

Este exemplo realmente não faz justiça à diferença - nunca tive problemas com nenhuma das versões da função. É apenas para ilustrar como são as duas opções. Quando você obtém funções muito mais complexas, usando coisas como listas e árvores, a diferença se torna muito mais acentuada.

Eu particularmente recomendo o Haskell porque é uma linguagem simples com uma sintaxe muito agradável. Também facilita muito trabalhar com idéias mais avançadas, como corecursão :

fibs = 0 : 1 : zipWith (+) fibs (drop 1 fibs)
fib n = fibs !! n

(Você não entenderá o código acima até jogar um pouco com Haskell, mas tenha certeza de que é basicamente mágico: P.) Certamente, você poderia fazer o mesmo com fluxos no Scheme, mas é muito mais natural em Haskell.

Tikhon Jelvis
fonte
0

Está esgotado, mas se você puder encontrá-lo, "Algoritmos Recursivos", de Richard Lorentz, não passa de recursão. Abrange os conceitos básicos de recursão, bem como algoritmos recursivos específicos.

Os exemplos estão em Pascal, mas não são tão grandes que a escolha do idioma é incômoda.

Wayne Conrad
fonte