Noções básicas sobre recursion

Estou tendo grandes dificuldades para entender a recursion na escola. Sempre que o professor está falando sobre isso, eu pareço entender, mas assim que eu tento sozinho, isso explode completamente meus cérebros.

Eu estava tentando resolver Towers of Hanoi a noite toda e completamente explodi minha mente. Meu livro tem apenas cerca de 30 páginas em recursion, por isso não é muito útil. Alguém sabe de livros ou resources que podem ajudar a esclarecer este tópico?

Como você esvazia um vaso contendo cinco flores?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso contendo quatro flores.

Como você esvazia um vaso contendo quatro flores?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso contendo três flores.

Como você esvazia um vaso contendo três flores?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso contendo duas flores.

Como você esvazia um vaso contendo duas flores?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso contendo uma flor.

Como você esvazia um vaso contendo uma flor?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso que não contém flores.

Como você esvazia um vaso sem flores?

Resposta: se o vaso não estiver vazio, você tira uma flor, mas o vaso está vazio, então está feito.

Isso é repetitivo. Vamos generalizar isso:

Como você esvazia um vaso contendo N flores?

Resposta: se o vaso não estiver vazio, você tira uma flor e depois esvazia um vaso contendo flores N-1 .

Hmm, podemos ver isso no código?

void emptyVase( int flowersInVase ) { if( flowersInVase > 0 ) { // take one flower and emptyVase( flowersInVase - 1 ) ; } else { // the vase is empty, nothing to do } } 

Hmm, não poderíamos ter feito isso em um loop?

Por que sim, a recursion pode ser substituída pela iteração, mas a recursion é mais elegante.

Vamos falar de trees. Na ciência da computação, uma tree é uma estrutura composta de nós , onde cada nó tem um número de filhos que também são nós ou nulos. Uma tree binária é uma tree feita de nós que têm exatamente dois filhos, normalmente chamados de “esquerda” e “direita”; novamente os filhos podem ser nós, ou nulos. Uma raiz é um nó que não é o filho de nenhum outro nó.

Imagine que um nó, além de seus filhos, tenha um valor, um número e imagine que desejamos sumr todos os valores em alguma tree.

Para sumr valor em qualquer nó, adicionaríamos o valor do próprio nó ao valor de seu filho esquerdo, se houver, e o valor de seu filho direito, se houver. Agora lembre-se de que os filhos, se não forem nulos, também são nós.

Então, para sumr o filho esquerdo, adicionaríamos o valor do próprio nó filho ao valor de seu filho esquerdo, se houver, e o valor de seu filho direito, se houver.

Portanto, para sumr o valor do filho esquerdo da criança esquerda, adicionaríamos o valor do próprio nó filho ao valor do filho à esquerda, se houver, e o valor do filho da direita, se houver.

Talvez você tenha antecipado para onde estou indo e gostaria de ver algum código? ESTÁ BEM:

 struct node { node* left; node* right; int value; } ; int sumNode( node* root ) { // if there is no tree, its sum is zero if( root == null ) { return 0 ; } else { // there is a tree return root->value + sumNode( root->left ) + sumNode( root->right ) ; } } 

Observe que, em vez de testar explicitamente os filhos para ver se eles são nulos ou nós, apenas fazemos com que a function recursiva retorne zero para um nó nulo.

Então, digamos que temos uma tree que se parece com isso (os números são valores, as barras apontam para filhos e @ significa que o ponteiro aponta para nulo):

  5 / \ 4 3 /\ /\ 2 1 @ @ /\ /\ @@ @@ 

Se chamarmos sumNode na raiz (o nó com valor 5), retornaremos:

 return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ; 

Vamos expandir isso no lugar. Em todos os lugares que vemos sumNode, vamos substituí-lo com a expansão da declaração de retorno:

 sumNode( node-with-value-5); return root->value + sumNode( root->left ) + sumNode( root->right ) ; return 5 + sumNode( node-with-value-4 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + sumNode( node-with-value-2 ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + sumNode( node-with-value-1 ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + sumNode(null ) + sumNode( null ) + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + sumNode( node-with-value-3 ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + sumNode(null ) + sumNode( null ) ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 + 0 + 0 ; return 5 + 4 + 2 + 0 + 0 + 1 + 0 + 0 + 3 ; return 5 + 4 + 2 + 0 + 0 + 1 + 3 ; return 5 + 4 + 2 + 1 + 3 ; return 5 + 4 + 3 + 3 ; return 5 + 7 + 3 ; return 5 + 10 ; return 15 ; 

Agora, vejamos como conquistamos uma estrutura de profundidade arbitrária e “ramificação”, considerando-a como a aplicação repetida de um modelo composto? cada vez que passamos pela function sumNode, lidamos com apenas um único nó, usando uma ramificação singe if / then e duas instruções de retorno simples que quase escreveram themsleves, diretamente de nossa especificação?

 How to sum a node: If a node is null its sum is zero otherwise its sum is its value plus the sum of its left child node plus the sum of its right child node 

Esse é o poder da recursion.


O exemplo do vaso acima é um exemplo de recursion da cauda . Tudo o que a recursion da cauda significa é que, na function recursiva, se recursamos (isto é, se chamamos a function novamente), essa foi a última coisa que fizemos.

O exemplo da tree não foi recursivo à cauda, ​​porque mesmo que a última coisa que fizemos foi reciclar a criança certa, antes de fazermos isso, recursamos a criança esquerda.

Na verdade, a ordem em que chamamos os filhos e o valor do nó atual não importava, porque a adição é comutativa.

Agora vamos olhar para uma operação onde a ordem é importante. Usaremos uma tree binária de nós, mas desta vez o valor mantido será um caractere, não um número.

Nossa tree terá uma propriedade especial, que para qualquer nó, seu caractere vem depois (em ordem alfabética) do caractere mantido por seu filho esquerdo e antes (em ordem alfabética) do caractere mantido por seu filho direito.

O que queremos fazer é imprimir a tree em ordem alfabética. Isso é fácil de fazer, dada a propriedade especial da tree. Nós apenas imprimimos o filho esquerdo, depois o caractere do nó, depois o filho certo.

Nós não queremos apenas imprimir à toa, então vamos passar nossa function para imprimir. Este será um object com uma function de impressão (char); nós não precisamos nos preocupar sobre como isso funciona, apenas que quando a impressão é chamada, ela imprime algo, em algum lugar.

Vamos ver isso no código:

 struct node { node* left; node* right; char value; } ; // don't worry about this code class Printer { private ostream& out; Printer( ostream& o ) :out(o) {} void print( char c ) { out < < c; } } // worry about this code int printNode( node* root, Printer& printer ) { // if there is no tree, do nothing if( root == null ) { return ; } else { // there is a tree printNode( root->left, printer ); printer.print( value ); printNode( root->right, printer ); } Printer printer( std::cout ) ; node* root = makeTree() ; // this function returns a tree, somehow printNode( root, printer ); 

Além da ordem de operações agora importante, este exemplo ilustra que podemos passar as coisas para uma function recursiva. A única coisa que temos que fazer é garantir que, em cada chamada recursiva, continuemos a transmiti-la. Nós passamos em um ponteiro de nó e uma impressora para a function, e em cada chamada recursiva, passamos por eles “para baixo”.

Agora, se a nossa tree se parece com isso:

  k / \ hn /\ /\ aj @ @ /\ /\ @@ i@ /\ @@ 

O que vamos imprimir?

 From k, we go left to h, where we go left to a, where we go left to null, where we do nothing and so we return to a, where we print 'a' and then go right to null, where we do nothing and so we return to a and are done, so we return to h, where we print 'h' and then go right to j, where we go left to i, where we go left to null, where we do nothing and so we return to i, where we print 'i' and then go right to null, where we do nothing and so we return to i and are done, so we return to j, where we print 'j' and then go right to null, where we do nothing and so we return to j and are done, so we return to h and are done, so we return to k, where we print 'k' and then go right to n where we go left to null, where we do nothing and so we return to n, where we print 'n' and then go right to null, where we do nothing and so we return to n and are done, so we return to k and are done, so we return to the caller 

Então, se nós apenas olharmos as linhas, nós seremos impressos:

  we return to a, where we print 'a' and then go right to we return to h, where we print 'h' and then go right to we return to i, where we print 'i' and then go right to we return to j, where we print 'j' and then go right to we return to k, where we print 'k' and then go right to we return to n, where we print 'n' and then go right to 

Nós vemos que imprimimos “ahijkn”, que é de fato em ordem alfabética.

Conseguimos imprimir uma tree inteira, em ordem alfabética, apenas sabendo como imprimir um único nó em ordem alfabética. O que era justo (porque nossa tree tinha a propriedade especial de ordenar valores à esquerda de valores alfabeticamente posteriores) sabendo imprimir o filho esquerdo antes de imprimir o valor do nó, e tto imprimir o filho correto depois de imprimir o valor do nó.

E esse é o poder da recursion: ser capaz de fazer coisas inteiras sabendo apenas como fazer uma parte do todo (e saber quando parar de recorrer).

Lembrando que na maioria das linguagens, operador || (“ou”) curto-circuito quando o primeiro operando é verdadeiro, a function recursiva geral é:

 void recurse() { doWeStop() || recurse(); } 

Luc M comenta:

Então, deve criar um crachá para esse tipo de resposta. Parabéns!

Obrigado, Luc! Mas, na verdade, porque editei essa resposta mais de quatro vezes (para adicionar o último exemplo, mas principalmente para corrigir erros de digitação e refiná-lo – digitar em um minúsculo teclado de netbook é difícil), não consigo mais pontos para ele . O que me desencoraja de colocar tanto esforço em respostas futuras.

Veja meu comentário aqui sobre isso: https://stackoverflow.com/questions/128434/what-are-community-wiki-posts-in-stackoverflow/718699#718699

Seu cérebro explodiu porque entrou em uma recursion infinita. Isso é um erro comum de iniciante.

Acredite ou não, você já entendeu a recursividade, está apenas sendo arrastado por uma metáfora comum, mas falha, de uma function: uma pequena checkbox com coisas que entram e saem.

Pense em vez de uma tarefa ou procedimento, como “descubra mais sobre recursividade na rede”. Isso é recursivo e você não tem problema com isso. Para concluir esta tarefa, você pode:

 a) Ler uma página de resultados do Google para "recursion"
 b) Depois de ler, siga o primeiro link e ...
 a.1) Leia essa nova página sobre recursion 
 b.1) Depois de ler, siga o primeiro link e ...
 a.2) Leia essa nova página sobre recursion 
 b.2) Depois de ler, siga o primeiro link e ...

Como você pode ver, você faz coisas recursivas há muito tempo sem problemas.

Por quanto tempo você continuaria fazendo essa tarefa? Para sempre até seu cérebro explodir? Claro que não, você vai parar em um determinado ponto, sempre que você acredita que você tenha concluído a tarefa.

Não há necessidade de especificar isso ao pedir que você “descubra mais sobre a recursion na rede”, porque você é um humano e pode inferir isso sozinho.

O computador não pode inferir o jack, então você deve include um final explícito: “descubra mais sobre a recursion na rede, até que você entenda ou tenha lido no máximo 10 páginas “.

Você também inferiu que deveria começar na página de resultados do Google para “recursion”, e novamente isso é algo que um computador não pode fazer. A descrição completa da nossa tarefa recursiva também deve include um ponto de partida explícito:

“descubra mais sobre recursividade na rede, até que você entenda ou leu no máximo 10 páginas e começa em http://www.google.com/search?q=recursion

Para grok a coisa toda, eu sugiro que você tente qualquer um desses livros:

  • Common Lisp: Uma introdução suave à computação simbólica. Esta é a mais bela explicação não matemática da recursion.
  • O pequeno engenheiro.

Para entender a recursion, tudo o que você precisa fazer é olhar o label da sua garrafa de xampu:

 function repeat() { rinse(); lather(); repeat(); } 

O problema com isso é que não há nenhuma condição de finalização, e a recursion será repetida indefinidamente, ou até que você fique sem shampoo ou água quente (condições de terminação externas, semelhantes a explodir sua pilha).

Se você quer um livro que faça um bom trabalho explicando a recursion em termos simples, dê uma olhada em Gödel, Escher, Bach: Uma Trança Eterna de Ouro de Douglas Hofstadter, especificamente no Capítulo 5. Além da recursion, é um bom trabalho explicar um número de conceitos complexos em ciência da computação e matemática de uma maneira compreensível, com uma explicação baseada em outra. Se você não teve muita exposição a esses tipos de conceitos antes, pode ser um livro bastante surpreendente.

Isso é mais uma queixa do que uma pergunta. Você tem uma pergunta mais específica sobre recursion? Como a multiplicação, não é uma coisa sobre a qual as pessoas escrevem muito.

Falando em multiplicação, pense nisso.

Questão:

O que é um * b?

Responda:

Se b é 1, é um. Caso contrário, é um + a * (b-1).

O que é um * (b-1)? Veja a pergunta acima para uma maneira de resolver isso.

Eu acho que este método muito simples deve ajudá-lo a entender a recursion. O método se chamará até que uma determinada condição seja verdadeira e retornará:

 function writeNumbers( aNumber ){ write(aNumber); if( aNumber > 0 ){ writeNumbers( aNumber - 1 ); } else{ return; } } 

Esta function irá imprimir todos os números do primeiro número que você vai alimentá-lo até 0. Assim:

 writeNumbers( 10 ); //This wil write: 10 9 8 7 6 5 4 3 2 1 0 //and then stop because aNumber is no longer larger then 0 

O que acontece é que writeNumbers (10) escreverá 10 e depois chamará writeNumbers (9), que escreverá 9 e depois chamará writeNumber (8) etc. Até que writeNumbers (1) escreva 1 e, em seguida, chame writeNumbers (0), que escreverá 0 butt não irá chamar writeNumbers (-1);

Este código é essencialmente o mesmo que:

 for(i=10; i>0; i--){ write(i); } 

Então, por que usar a recursion, você pode perguntar se um loop for essencialmente o mesmo. Bem, você geralmente usa a recursion quando precisa aninhar loops, mas não sabe o quão profundo eles estão nesteds. Por exemplo, ao imprimir itens de matrizes aninhadas:

 var nestedArray = Array('Im a string', Array('Im a string nested in an array', 'me too!'), 'Im a string again', Array('More nesting!', Array('nested even more!') ), 'Im the last string'); function printArrayItems( stringOrArray ){ if(typeof stringOrArray === 'Array'){ for(i=0; i 

Esta function pode ter um array que pode ser nested em 100 níveis, enquanto você escreve um loop for, então você precisa aninhá-lo 100 vezes:

 for(i=0; i 

Como você pode ver, o método recursivo é muito melhor.

Na verdade, você usa recursion para reduzir a complexidade do problema em questão. Você aplica recursion até chegar a um caso base simples que possa ser resolvido facilmente. Com isso você pode resolver o último passo recursivo. E com isso todos os outros passos recursivos até o seu problema original.

Recursão

Método A, chama o método A chama o método A. Eventualmente, um desses methods A não chama e sai, mas é recursivo porque algo chama a si mesmo.

Exemplo de recursion onde eu quero imprimir cada nome de pasta no disco rígido: (em c #)

 public void PrintFolderNames(DirectoryInfo directory) { Console.WriteLine(directory.Name); DirectoryInfo[] children = directory.GetDirectories(); foreach(var child in children) { PrintFolderNames(child); // See we call ourself here... } } 

Vou tentar explicar isso com um exemplo.

Você sabe o que n! significa? Se não: http://en.wikipedia.org/wiki/Factorial

3! = 1 * 2 * 3 = 6

aqui vai algum pseudocódigo

 function factorial(n) { if (n==0) return 1 else return (n * factorial(n-1)) } 

Então vamos tentar:

 factorial(3) 

é n 0?

não!

então, nós nos aprofundamos mais com nossa recursion:

 3 * factorial(3-1) 

3-1 = 2

é 2 == 0?

não!

então vamos mais fundo! 3 * 2 * fatorial (2-1) 2-1 = 1

é 1 == 0?

não!

então vamos mais fundo! 3 * 2 * 1 * fatorial (1-1) 1-1 = 0

é 0 == 0?

sim!

nós temos um caso trivial

então temos 3 * 2 * 1 * 1 = 6

Espero que o tenha ajudado

Qual livro você está usando?

O livro padrão sobre algoritmos que é realmente bom é o Cormen & Rivest. Minha experiência é que ela ensina recursion muito bem.

A recursion é uma das partes mais difíceis da programação, e embora exija instinto, pode ser aprendida. Mas precisa de uma boa descrição, bons exemplos e boas ilustrações.

Além disso, 30 páginas em geral são muito, 30 páginas em uma única linguagem de programação é confusa. Não tente aprender a recursion em C ou Java antes de entender a recursion em geral a partir de um livro geral.

Uma function recursiva é simplesmente uma function que se chama quantas vezes for necessário. É útil se você precisar processar algo várias vezes, mas não tem certeza de quantas vezes será realmente necessário. De certa forma, você poderia pensar em uma function recursiva como um tipo de loop. Como um loop, no entanto, você precisará especificar condições para o processo ser quebrado, caso contrário, ele se tornará infinito.

http://javabat.com é um lugar divertido e excitante para praticar a recursion. Seus exemplos começam razoavelmente leves e funcionam extensivamente (se você quiser ir tão longe). Nota: Sua abordagem é aprender praticando. Aqui está uma function recursiva que escrevi para simplesmente replace um loop for.

O loop for:

 public printBar(length) { String holder = ""; for (int index = 0; i < length; i++) { holder += "*" } return holder; } 

Aqui está a recursion para fazer a mesma coisa. (note que sobrecarregamos o primeiro método para garantir que ele seja usado exatamente como acima). Também temos outro método para manter nosso índice (semelhante ao modo como a declaração for faz isso para você acima). A function recursiva deve manter seu próprio índice.

 public String printBar(int Length) // Method, to call the recursive function { printBar(length, 0); } public String printBar(int length, int index) //Overloaded recursive method { // To get a better idea of how this works without a for loop // you can also replace this if/else with the for loop and // operationally, it should do the same thing. if (index >= length) return ""; else return "*" + printBar(length, index + 1); // Make recursive call } 

Para encurtar a história, a recursion é uma boa maneira de escrever menos código. No último printBar, tenhamos uma declaração if. SE nossa condição foi atingida, sairemos da recursion e retornaremos ao método anterior, que retorna ao método anterior, etc. Se eu enviei um printBar (8), recebo o ********. Eu estou esperando que, com um exemplo de uma function simples que faz a mesma coisa que um loop for, talvez isso ajude. Você pode praticar isso mais no Java Bat embora.

A maneira verdadeiramente matemática de olhar para a construção de uma function recursiva seria a seguinte:

1: Imagine que você tenha uma function que esteja correta para f (n-1), construa f de modo que f (n) esteja correto. 2: Construa f, de modo que f (1) esteja correto.

É assim que você pode provar que a function está correta, matematicamente, e é chamada de indução . É equivalente a ter diferentes casos de base, ou funções mais complicadas em múltiplas variables). Também é equivalente imaginar que f (x) está correto para todo x

Agora, por um exemplo “simples”. Crie uma function que possa determinar se é possível ter uma combinação de moedas de 5 centavos e 7 centavos para fazer x centavos. Por exemplo, é possível ter 17 centavos por 2×5 + 1×7, mas é impossível ter 16 centavos.

Agora imagine que você tem uma function que informa se é possível criar x centavos, contanto que x

 bool can_create_coins(int n) { if (n >= 7 && can_create_coins_small(n-7)) return true; else if (n >= 5 && can_create_coins_small(n-5)) return true; else return false; } 

O truque aqui é perceber que o fato de can_create_coins funcionar para n significa que você pode replace can_create_coins por can_create_coins_small, dando:

 bool can_create_coins(int n) { if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; } 

Uma última coisa a fazer é ter um caso básico para interromper a recursion infinita. Note que se você está tentando criar 0 centavos, então isso é possível não ter moedas. Adicionando esta condição dá:

 bool can_create_coins(int n) { if (n == 0) return true; else if (n >= 7 && can_create_coins(n-7)) return true; else if (n >= 5 && can_create_coins(n-5)) return true; else return false; } 

Pode ser provado que esta function sempre retornará, usando um método chamado descida infinita , mas isso não é necessário aqui. Você pode imaginar que f (n) só chama valores mais baixos de n e sempre chegará a 0.

Para usar esta informação para resolver o seu problema de Tower of Hanoi, eu acho que o truque é assumir que você tem uma function para mover n-1 comprimidos de a para b (para qualquer a / b), tentando mover n tabelas de a para b .

Exemplo recursivo simples no Common Lisp :

MYMAP aplica uma function a cada elemento de uma lista.

1) uma lista vazia não tem elemento, então retornamos a lista vazia – () e NIL ambos são a lista vazia.

2) aplique a function à primeira lista, chame MYMAP para o resto da lista (a chamada recursiva) e combine ambos os resultados em uma nova lista.

 (DEFUN MYMAP (FUNCTION LIST) (IF (NULL LIST) () (CONS (FUNCALL FUNCTION (FIRST LIST)) (MYMAP FUNCTION (REST LIST))))) 

Vamos assistir a execução rastreada. Ao entrar em uma function, os argumentos são impressos. Ao EXITAR uma function, o resultado é impresso. Para cada chamada recursiva, a saída será recuada no nível.

Este exemplo chama a function SIN em cada número de uma lista (1 2 3 4).

 Command: (mymap 'sin '(1 2 3 4)) 1 Enter MYMAP SIN (1 2 3 4) | 2 Enter MYMAP SIN (2 3 4) | 3 Enter MYMAP SIN (3 4) | | 4 Enter MYMAP SIN (4) | | 5 Enter MYMAP SIN NIL | | 5 Exit MYMAP NIL | | 4 Exit MYMAP (-0.75680256) | 3 Exit MYMAP (0.14112002 -0.75680256) | 2 Exit MYMAP (0.9092975 0.14112002 -0.75680256) 1 Exit MYMAP (0.841471 0.9092975 0.14112002 -0.75680256) 

Este é o nosso resultado :

 (0.841471 0.9092975 0.14112002 -0.75680256) 

Para explicar a recursion a uma criança de seis anos, primeiro explique-a a uma criança de cinco anos e depois espere um ano.

Na verdade, esse é um contra-exemplo útil, porque sua chamada recursiva deve ser mais simples, não mais difícil. Seria ainda mais difícil explicar a recursion para uma criança de cinco anos e, embora você pudesse interromper a recursion em 0, não há uma solução simples para explicar a recursion a uma criança de zero anos de idade.

Para resolver um problema usando recursion, primeiro sub-divida-o em um ou mais problemas mais simples que você pode resolver da mesma maneira, e quando o problema for simples o suficiente para resolver sem recursion adicional, você pode retornar a níveis mais altos.

Na verdade, essa era uma definição recursiva de como resolver um problema com recursion.

As crianças implicitamente usam recursion, por exemplo:

Viagem de carro para a Disney World

Estamos lá ainda?

Já chegamos lá?

Já chegamos lá? (Quase …)

Já chegamos lá? (SHHHH)

Já estamos lá?(!!!!!)

Em que ponto a criança adormece …

Esta function de contagem regressiva é um exemplo simples:

 function countdown() { return (arguments[0] > 0 ? ( console.log(arguments[0]),countdown(arguments[0] - 1)) : "done" ); } countdown(10); 

Ao trabalhar com soluções recursivas, eu sempre tento:

  • Estabeleça o caso base primeiro, ou seja, quando n = 1 em uma solução para fatorial
  • Tente criar uma regra geral para todos os outros casos

Também existem diferentes tipos de soluções recursivas, há a abordagem de dividir e conquistar, que é útil para fractais e muitos outros.

Também ajudaria se você pudesse trabalhar em problemas mais simples primeiro apenas para pegar o jeito. Alguns exemplos estão resolvendo o fatorial e gerando o enésimo número de fibonacci.

Para referências, eu recomendo Algorithms por Robert Sedgewick.

Espero que ajude. Boa sorte.

Ai Eu tentei descobrir as torres de Hanoi no ano passado. A coisa complicada sobre o TOH é que ele não é um exemplo simples de recursion – você aninhou recursões que também mudam o papel das torres em cada chamada. A única maneira de fazer com que fizesse sentido era literalmente visualizar o movimento dos anéis em minha mente e verbalizar qual seria o chamado recursivo. Eu começaria com um único anel, depois dois, depois três. Eu realmente pedi o jogo na internet. Demorei talvez dois ou três dias quebrando meu cérebro para consegui-lo.

Uma function recursiva é como uma mola que você comprime um pouco em cada chamada. Em cada etapa, você coloca um pouco de informação (contexto atual) em uma pilha. Quando o passo final é alcançado, a mola é liberada, coletando todos os valores (contextos) de uma só vez!

Não tenho certeza se essa metáfora é eficaz … 🙂

De qualquer forma, além dos exemplos clássicos (fatorial que é o pior exemplo, pois é ineficiente e facilmente achatado, Fibonacci, Hanói …) que são um pouco artificiais (eu raramente, ou nunca, os uso em casos reais de programação), é interessante ver onde é realmente usado.

Um caso muito comum é andar uma tree (ou um gráfico, mas as trees são mais comuns, em geral).
Por exemplo, uma hierarquia de pastas: para listar os arquivos, você os itera. Se você encontrar um subdiretório, a function listando os arquivos se chamará com a nova pasta como argumento. Ao voltar de listar essa nova pasta (e suas subpastas!), Ela retoma seu contexto, para o próximo arquivo (ou pasta).
Outro caso concreto é quando se desenha uma hierarquia de componentes GUI: é comum ter containers, como painéis, para conter componentes que podem ser painéis, componentes compostos, etc. A rotina de pintura chama recursivamente a function de pintura de cada componente, que chama a function de tinta de todos os componentes, etc.

Não tenho certeza se sou muito claro, mas gosto de mostrar o uso do material de ensino no mundo real, já que era algo que eu estava tropeçando no passado.

Pense uma abelha operária. Ela tenta fazer mel. It does its job and expects other worker bees to make rest of the honey. And when the honeycomb is full, it stops.

Think it as magic. You have a function that has the same name with the one you are trying to implement and when you give it the subproblem, it solves it for you and the only thing you need to do is to integrate the solution of your part with the solution it gave you.

For example, we want to calculate the length of a list. Lets call our function magical_length and our magical helper with magical_length We know that if we give the sublist which does not have the first element, it will give us the length of the sublist by magic. Then only thing we need to think is how to integrate this information with our job. The length of the first element is 1 and magic_counter gives us the length of sublist n-1, therefore total length is (n-1) + 1 -> n

 int magical_length( list ) sublist = rest_of_the_list( list ) sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length 

However this answer is incomplete because we didn’t consider what happens if we give an empty list. We thought that the list we have always has at least one element. Therefore we need to think about what should be the answer if we are given an empty list and answer is obviously 0. So add this information to our function and this is called base/edge condition.

 int magical_length( list ) if ( list is empty) then return 0 else sublist_length = magical_length( sublist ) // you can think this function as magical and given to you return 1 + sublist_length