Recursão

Recursão

> Tutorial LeekScript

Pré-requisitos:

• Obrigatório:
• Saiba como definir uma função.
• Recomendado:
• Saber usar funções/encerramentos anônimos.
• Útil:
• Ter noções do que são tipos de dados abstratos, em particular a pilha. cf: fonte
• Saiba o que é [Memoisization] (https://leekwars.com/encyclopedia/Optimisation#Pr%C3%A9parer_du_curry)

----

A recursão, em termos gerais, é a capacidade de um objeto se referir a si mesmo. No mundo real, isso é mais evidente nos fractais, bem como quando dois espelhos são colocados frente a frente. Também encontramos essa noção em frases do estilo: "Eu sonho que sonho que sonho." ou "Eu acho que escrevo que sonho que penso que escrevo...", etc. Na programação, isso se manifesta principalmente com funções que se chamam:

loop de função() { laço(); }

A função acima é a função recursiva mais simples que existe. Quando chamado, ele não faz nada além de chamar a si mesmo. Isso é o mesmo que usar um loop infinito (por exemplo, while(true);). Usaremos essa função como um esqueleto básico para todas as nossas futuras funções recursivas.

Recursão

A recursão é análoga à desconstrução. É encontrado principalmente em algoritmos do tipo ''Dividir e Conquistar''. Para resolver nosso problema, começamos subdividindo-o em subproblemas mais fáceis de resolver, repetimos o processo até encontrar um problema que sabemos resolver diretamente e, a partir daí, resolvemos os problemas superiores combinando nossas soluções anteriores.

Definir soma de 0 a n

Queremos definir uma função tomando um inteiro n como parâmetro e retornando a soma de 0 a n (por exemplo, 0 + 1 + ... + n). Tomando nosso esqueleto básico, podemos começar com a seguinte função:

função somaN(n){ somaN(?); retornar?; }

No momento temos as seguintes informações:

• n é conhecido;
• podemos chamar sumN com um novo valor;
• podemos usar o retorno da nova chamada;
• sumN deve retornar um número;
• deve haver uma adição em algum lugar;
• como para loop, sumN não para. Nós vamos ter que descobrir como pará-lo.

Ao trabalhar recursivamente, é sempre uma boa ideia começar com a condição de parada. No caso da recursão, queremos parar de criar subproblemas quando encontramos algo que podemos resolver. Nesse caso, a soma de 0 a 0 é algo que sabemos resolver. 0 é, portanto, nosso caso base, podemos retornar diretamente a soma correspondente.

função somaN(n) { if (n === 0) { return 0; } senão { somaN(?); retornar?; } }

Agora precisamos descobrir como chegar ao caso base. Poderíamos subtrair n dele mesmo, mas nesse caso não poderíamos somar os inteiros entre 0 e n, teríamos apenas 0 e n disponíveis. Teremos, portanto, que criar um sub-problema que possa resolver uma soma com um n mais próximo do nosso caso base.

função somaN(n) { if (n === 0) { return 0; } senão { somaN(n - 1); retornar?; } }

Agora só precisamos fazer a soma, que nos foi solicitada no início. Aqui, a soma de 0 para n também é a soma da soma de 0 para n - 1 e n.

função somaN(n) { if (n === 0) { return 0; } else { return n + somaN(n - 1); } }

Com ternário:

função somaN(n) { retornar n === 0? 0 : n + somaN(n - 1); }

Sinta-se à vontade para experimentar o código em seu editor Leekwars. Talvez você descubra o principal problema da recursão. Você também pode visualizar a execução (de forma básica) neste site.

Corecursão

/!\ Seção a refazer, o que é mostrado é principalmente recursão de cauda. Inadequado para vários ramos. /!\ Corecursion é análogo à construção. Ao contrário da recursão onde buscamos chegar a um caso base a partir do nosso problema principal, na corecursão partimos diretamente do nosso caso base, e avançamos para a solução do problema principal.

Recursão Mútua

Já cobrimos a recursão mútua com espelhos e sentenças. Na programação, com funções, isso se traduz em duas ou mais funções chamando uma à outra. Apresentamos a seguir o caso mais simples de recursão mútua:

função mutualLoop() { mutualHelper(); }

função mut