Noções básicas sobre recursão [fechado]

Estou tendo grandes problemas para entender a recursão na escola. Sempre que o professor está falando sobre isso, parece que entendi, mas assim que o tento sozinho, ele explode completamente.

Eu estava tentando resolver Towers of Hanoi a noite toda e me surpreendeu completamente. Meu livro tem apenas cerca de 30 páginas em recursão, portanto não é muito útil. Alguém sabe de livros ou recursos 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ê retira 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ê retira 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ê retira 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ê retira 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ê retira uma flor e depois esvazia um vaso que não contém flores.

Como você esvazia um vaso que não contém flores?

Resposta: se o vaso não estiver vazio, retire uma flor, mas o vaso está vazio e pronto.

Isso é repetitivo. Vamos generalizar:

Como você esvazia um vaso contendo N flores?

Resposta: se o vaso não estiver vazio, retire uma flor e esvazie 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 for?

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

Vamos conversar sobre árvores. Na ciência da computação, uma árvore é uma estrutura composta de nós , em que cada nó tem algum número de filhos que também são nós, ou nulos. Uma árvore binária é uma árvore feita de nós que possuem exatamente dois filhos, geralmente chamados "esquerdo" e "direito"; novamente os filhos podem ser nós ou nulos. Uma raiz é um nó que nã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 somar todos os valores em alguma árvore.

Para somar valor em qualquer nó, adicionaríamos o valor do próprio nó ao valor de seu filho esquerdo, se houver, e ao 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.

Portanto, para somar o filho esquerdo, adicionamos o valor do nó filho ao valor do filho esquerdo, se houver, e ao valor do filho direito, se houver.

Portanto, para somar o valor do filho esquerdo do filho esquerdo, adicionaríamos o valor do nó filho ao valor do filho esquerdo, se houver, e ao valor do filho direito, se houver.

Talvez você tenha antecipado para onde estou indo com isso 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 função recursiva retorne zero para um nó nulo.

Digamos que tenhamos uma árvore 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 todo lugar que vemos sumNode, vamos substituí-lo pela 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 veja como conquistamos uma estrutura de profundidade arbitrária e "ramificação", considerando-a como a aplicação repetida de um modelo composto? a cada vez, através de nossa função sumNode, lidamos com apenas um único nó, usando uma única ramificação if / then e duas instruções simples de retorno 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 recursão.

O exemplo de vaso acima é um exemplo de recursão da cauda . Tudo o que significa recursão final é que, na função recursiva, se recorremos (ou seja, se chamamos a função novamente), essa foi a última coisa que fizemos.

O exemplo da árvore não era recursivo de cauda, ​​porque mesmo que a última coisa que fizemos foi retribuir o filho certo, antes de fazê-lo, recursivamos o filho esquerdo.

De fato, a ordem na qual chamamos os filhos e adicionamos o valor do nó atual não importava, porque a adição é comutativa.

Agora vamos ver uma operação em que a ordem é importante. Usaremos uma árvore binária de nós, mas desta vez o valor mantido será um caractere, não um número.

Nossa árvore terá uma propriedade especial: 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 árvore em ordem alfabética. Isso é fácil, dada a propriedade especial da árvore. Nós apenas imprimimos o filho esquerdo, o caractere do nó e o filho direito.

Não queremos apenas imprimir à vontade, então passaremos à nossa função algo para imprimir. Este será um objeto com uma função print (char); não precisamos nos preocupar com o funcionamento, apenas 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 das operações agora importantes, este exemplo ilustra que podemos passar as coisas para uma função recursiva. A única coisa que precisamos fazer é garantir que, a cada chamada recursiva, continuemos a repassá-la. Passamos um ponteiro de nó e uma impressora para a função e, em cada chamada recursiva, passamos "inativos".

Agora, se nossa árvore estiver assim:

         k
        / \
       h   n
      /\   /\
     a  j @  @
    /\ /\
    @@ 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

Portanto, se apenas olharmos para as linhas, fomos 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

Vimos que imprimimos "ahijkn", que está de fato em ordem alfabética.

Conseguimos imprimir uma árvore inteira, em ordem alfabética, apenas sabendo como imprimir um único nó em ordem alfabética. O que era justo (porque nossa árvore tinha a propriedade especial de ordenar valores à esquerda dos valores em ordem alfabética mais tarde) saber imprimir o filho esquerdo antes de imprimir o valor do nó e imprimir o filho certo depois de imprimir o valor do nó.

E esse é o poder da recursão: ser capaz de fazer coisas inteiras, sabendo apenas como fazer uma parte do todo (e sabendo quando parar de se repetir).

Lembrando que, na maioria dos idiomas, operador || ("ou") curto-circuito quando seu primeiro operando for verdadeiro, a função recursiva geral é:

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

Luc M comenta:

O SO deve criar um crachá para esse tipo de resposta. Parabéns!

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

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

Seu cérebro explodiu porque entrou em uma recursão infinita. Esse é um erro comum para iniciantes.

Acredite ou não, você já entende a recursão, está apenas sendo arrastado por uma metáfora comum, mas defeituosa, de uma função: uma pequena caixa com coisas que entram e saem.

Pense em vez de uma tarefa ou procedimento, como "descobrir mais sobre a recursão na rede". Isso é recursivo e você não tem nenhum problema com isso. Para concluir esta tarefa, você pode:

a) Leia a página de resultados do Google para "recursão"
b) Depois de ler, siga o primeiro link e ...
a.1) Leia a nova página sobre recursão 
b.1) Depois de ler, siga o primeiro link e ...
a.2) Leia a nova página sobre recursão 
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é o seu cérebro explodir? Claro que não, você irá parar em um determinado momento, sempre que acreditar que concluiu a tarefa.

Não é necessário especificar isso ao solicitar que você "descubra mais sobre a recursão na rede", porque você é humano e pode inferir isso sozinho.

O computador não pode inferir o conector, portanto, você deve incluir um final explícito: "saiba mais sobre a recursão na rede, ATÉ que você a compreenda ou tenha lido no máximo 10 páginas ".

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

"saiba mais sobre a recursão na rede, até que você a compreenda ou tenha lido no máximo 10 páginas e iniciando em www.google.com/search?q=recursion "

Para entender tudo, sugiro que você tente um destes livros:

• Lisp comum: uma introdução suave à computação simbólica. Esta é a explicação não-matemática mais bonita da recursão.
• O pequeno planejador.

Para entender a recursão, basta olhar no rótulo do seu frasco de xampu:

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

O problema é que não há condição de terminação e a recursão se repetirá indefinidamente, ou até você ficar sem xampu ou água quente (condições de terminação externas, semelhantes a queimar sua pilha).

Se você quer um livro que explique bem a recursão em termos simples, dê uma olhada em Gödel, Escher, Bach: Uma Eterna Trança Dourada de Douglas Hofstadter, especificamente no Capítulo 5. Além da recursão, ele faz um bom trabalho de explicar uma série 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ê nunca teve muita exposição a esses tipos de conceitos antes, pode ser um livro bastante impressionante.

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

Falando em multiplicação, pense nisso.

Questão:

O que é a * b?

Responda:

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

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

Eu acho que esse método muito simples deve ajudá-lo a entender a recursão. 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 função imprimirá todos os números do primeiro número que você alimentará 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 em baixo é que writeNumbers (10) escreve 10 e depois chama writeNumbers (9) que escreve 9 e depois chama writeNumber (8) etc. Até writeNumbers (1) escreve 1 e depois chama writeNumbers (0) que escreve 0 butt não chamará writeNumbers (-1);

Este código é essencialmente o mesmo que:

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

Então, por que usar recursão, você pode perguntar se um loop for faz essencialmente o mesmo. Bem, você geralmente usa recursão quando precisaria aninhar loops, mas não saberá a profundidade em que estão aninhados. 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<stringOrArray.length; i++){ 
     printArrayItems( stringOrArray[i] );
   }
 }
 else{
   write( stringOrArray );
 }
}

printArrayItems( stringOrArray );
//this will write:
//'Im a string' 'Im a string nested in an array' 'me too' 'Im a string again'
//'More nesting' 'Nested even more' 'Im the last string'

Essa função pode levar uma matriz que pode ser aninhada em 100 níveis, enquanto você escreve um loop for, é necessário aninhar 100 vezes:

for(i=0; i<nestedArray.length; i++){
 if(typeof nestedArray[i] == 'Array'){
  for(a=0; i<nestedArray[i].length; a++){
   if(typeof nestedArray[i][a] == 'Array'){
    for(b=0; b<nestedArray[i][a].length; b++){
     //This would be enough for the nestedAaray we have now, but you would have
     //to nest the for loops even more if you would nest the array another level
     write( nestedArray[i][a][b] );
    }//end for b
   }//endif typeod nestedArray[i][a] == 'Array'
   else{ write( nestedArray[i][a] ); }
  }//end for a
 }//endif typeod nestedArray[i] == 'Array'
 else{ write( nestedArray[i] ); }
}//end for i

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

Na verdade, você usa a recursão para reduzir a complexidade do seu problema em questão. Você aplica a recursão até chegar a um caso básico simples que pode ser resolvido facilmente. Com isso, você pode resolver o último passo recursivo. E com isso todas as outras etapas recursivas até o seu problema original.

Vou tentar explicar com um exemplo.

Você sabe o que n! significa? Caso contrário: 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 nos aprofundamos com nossa recursão:

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 tenha ajudado

Recursão

O método A chama o método A chama o método A. Eventualmente, um desses métodos A não chama e sai, mas é recursão porque algo se chama.

Exemplo de recursão em que desejo imprimir todos os nomes de pastas 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...
    }
}

Qual livro você está usando?

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

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

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

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

http://javabat.com é um lugar divertido e emocionante para praticar recursão. Seus exemplos começam bastante leves e passam por extensos (se você quiser ir tão longe). Nota: A abordagem deles é aprender praticando. Aqui está uma função recursiva que escrevi para simplesmente substituir um loop for.

O loop for:

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

Aqui está a recursão para fazer a mesma coisa. (observe 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 que a instrução for faz para você acima). A função 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 resumir uma longa história, a recursão é uma boa maneira de escrever menos código. No último printBar, observe que temos uma instrução if. Se nossa condição for atingida, sairemos da recursão e retornaremos ao método anterior, que retorna ao método anterior, etc. Se eu enviei uma printBar (8), recebo ********. Espero que, com um exemplo de uma função simples que faça a mesma coisa que um loop for, talvez isso ajude. Você pode praticar isso mais no Java Bat.

A maneira verdadeiramente matemática de analisar a criação de uma função recursiva seria a seguinte:

1: Imagine que você tem uma função correta para f (n-1), construa f para que f (n) esteja correta. 2: Construa f, de modo que f (1) esteja correto.

É assim que você pode provar que a função está correta, matematicamente, e se chama Indução . É equivalente a ter casos base diferentes ou funções mais complicadas em várias variáveis). Também é equivalente a imaginar que f (x) está correto para todos x

Agora, um exemplo "simples". Crie uma função 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 2x5 + 1x7, mas impossível ter 16 centavos.

Agora imagine que você tem uma função que informa se é possível criar x centavos, desde que x <n. Chame esta função can_create_coins_small. Deveria ser bastante simples imaginar como fazer a função para n. Agora construa sua função:

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 substituir can_create_coins por can_create_coins_small, fornecendo:

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 base para interromper a recursão infinita. Observe que se você estiver tentando criar 0 centavos, isso é possível por não ter moedas. A adição desta condição fornece:

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-se provar que essa função sempre retornará, usando um método chamado descida infinita , mas isso não é necessário aqui. Você pode imaginar que f (n) chama apenas valores mais baixos de n e sempre chegará a 0.

Para usar essas informações para resolver o problema da Torre de Hanói, acho que o truque é assumir que você tem a função de mover n-1 tablets 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 função a cada elemento em uma lista.

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

2) aplique a função à primeira lista, chame MYMAP pelo restante da lista (a chamada recursiva) e combine os dois 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 inserir uma função, os argumentos são impressos. Ao sair de uma função, o resultado é impresso. Para cada chamada recursiva, a saída será recuada no nível.

Este exemplo chama a função SIN em cada número em 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 recursão para uma criança de seis anos, primeiro explique-a para uma criança de cinco anos e depois espere um ano.

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

Para resolver um problema usando a recursão, primeiro 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 ser resolvido sem mais recursões, você poderá retornar aos níveis mais altos.

De fato, essa era uma definição recursiva de como resolver um problema com recursão.

Filhos implicitamente usam recursão, por exemplo:

Viagem a Disney World

Já chegamos? (Não)

Já chegamos? (Em breve)

Já estamos lá? (Quase ...)

Já estamos lá? (SHHHH)

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

Nesse ponto, a criança adormece ...

Esta função de contagem regressiva é um exemplo simples:

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

A Lei de Hofstadter aplicada a projetos de software também é relevante.

A essência da linguagem humana é, segundo Chomsky, a capacidade dos cérebros finitos de produzir o que ele considera gramáticas infinitas. Com isso, ele quer dizer não apenas que não há limite superior para o que podemos dizer, mas que não há limite superior para o número de frases que nossa linguagem possui, não há limite superior para o tamanho de uma frase em particular. Chomsky afirmou que a ferramenta fundamental subjacente a toda essa criatividade da linguagem humana é a recursão: a capacidade de uma frase se repetir dentro de outra frase do mesmo tipo. Se eu disser "casa do irmão de João", tenho um substantivo "casa", que ocorre em uma frase nominal, "casa do irmão", e essa frase nominal ocorre em outra frase substantiva, "casa do irmão de João". Isso faz muito sentido, e é '

Referências

• Recursão e pensamento humano

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

• Estabeleça o caso base primeiro, isto é, 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 resolver problemas mais simples primeiro apenas para entender o problema. Alguns exemplos estão resolvendo para o fatorial e gerando o enésimo número de fibonacci.

Para referências, eu recomendo Algoritmos de Robert Sedgewick.

Espero que ajude. Boa sorte.

Ai. Tentei descobrir as Torres de Hanói no ano passado. O mais complicado do TOH é que não é um exemplo simples de recursão - você possui recursões aninhadas que também alteram os papéis das torres em cada chamada. A única maneira de fazer sentido era literalmente visualizar o movimento dos anéis nos olhos da minha mente e verbalizar qual seria o chamado recursivo. Eu começaria com um único toque, depois dois, depois três. Na verdade, eu pedi o jogo na internet. Levei talvez dois ou três dias quebrando meu cérebro para consegui-lo.

Uma função 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 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 os utilizo em casos reais de programação) interessante ver onde é realmente usado.

Um caso muito comum é andar em uma árvore (ou em um gráfico, mas as árvores 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 função que lista os arquivos chama a si mesma com a nova pasta como argumento. Ao voltar da lista desta nova pasta (e de suas subpastas!), Ela retoma seu contexto, para o próximo arquivo (ou pasta).
Outro caso concreto é o desenho de uma hierarquia de componentes da GUI: é comum ter contêineres, como painéis, para reter componentes que também podem ser painéis ou componentes compostos, etc. A rotina de pintura chama recursivamente a função de pintura de cada componente, que chama a função de pintura de todos os componentes que possui, etc.

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

Pense em uma abelha operária. Tenta fazer mel. Ele faz o seu trabalho e espera que outras abelhas operárias recuperem o mel. E quando o favo de mel está cheio, ele para.

Pense nisso como mágica. Você tem uma função que tem o mesmo nome com a que você está tentando implementar e, quando fornece o subproblema, resolve-o para você e a única coisa que você precisa fazer é integrar a solução da sua parte à solução que deu-te.

Por exemplo, queremos calcular o comprimento de uma lista. Vamos chamar nossa função de comprimento mágico e nosso ajudante mágico com comprimento mágico. Sabemos que se dermos a sublist que não possui o primeiro elemento, ela nos dará o comprimento da sublist por mágica. A única coisa que precisamos pensar é como integrar essas informações ao nosso trabalho. O comprimento do primeiro elemento é 1 e magic_counter nos fornece o comprimento da sub-lista n-1, portanto, o comprimento total é (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

No entanto, esta resposta está incompleta porque não consideramos o que acontece se dermos uma lista vazia. Pensamos que a lista que temos sempre tem pelo menos um elemento. Portanto, precisamos pensar sobre qual deve ser a resposta se recebermos uma lista vazia e a resposta for obviamente 0. Portanto, adicione essas informações à nossa função e isso será chamado de condição de base / borda.

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