Compreender a recursão com javascript

Introdução

Alguns problemas são resolvidos mais naturalmente usando a recursão. Por exemplo, uma sequência como Fibonacci tem uma definição recursiva. Cada número na é a soma dos dois números anteriores da sequência. Os problemas que exigem que você construa ou corte uma estrutura de dados semelhante à árvore também pode ser resolvida com a recursão. O trem para pensar recursivamente lhe dará uma poderosa capacidade de resolver esses problemas.

Neste tutorial, farei uma revisão passo a passo de várias funções recursivas para ver como elas funcionam e mostram técnicas que você pode usar para definir funções recursivas sistematicamente.

conteúdo:

• o que é a recursão?
• recursion com números
• recursion com listas
• listas de construção
• revisão

Qual é a recursão?

Uma função definida recursivamente é uma função definida em termos de uma versão mais simples. Este é um exemplo simplificado:

function doA(n) { ... doA(n-1);}

Para entender como o recotador funciona conceitualmente, veremos um exemplo que não tem nada a ver com o código. Imagine que você é responsável por responder a telefonemas no seu trabalho. Como esta é uma empresa movimentada, seu telefone tem várias linhas para que você possa participar de várias chamadas ao mesmo tempo. Cada linha telefônica é um botão no receptor e, quando há uma chamada recebida, o botão piscará. Hoje, quando você chega ao trabalho e liga o telefone, há quatro linhas piscando ao mesmo tempo. Portanto, você começa a trabalhar respondendo todas as chamadas.

Você atende a linha uma e diga “por favor aguarde”. Então você responde a linha dois e colocá-lo em espera. Abaixo você atende a linha de três e coloque-a em espera. Finalmente, você responde a quarta linha e fala com a pessoa que você está chamando. Quando terminar com a quarta pessoa, você pendura e responde a terceira chamada. Quando terminar com a terceira chamada, você desliga e responde ao segundo. Quando terminar com a segunda chamada, você desliga e responde ao primeiro. Quando você acaba com essa ligação, você pode finalmente pendurar o telefone.

Cada uma das chamadas telefônicas deste exemplo é como uma chamada recursiva em uma função. Quando você receber uma chamada, é colocado na pilha de chamadas (em termos de código). Se você não conseguir terminar uma chamada imediatamente, então você aguenta em espera. Se você tiver uma chamada para uma função que não pode ser avaliada imediatamente, ela permanece na pilha de chamadas. Quando você pode atender uma chamada, isso é servido. Quando seu código é capaz de avaliar a chamada para uma função, ela é removida da pilha. Ter essa analogia em mente enquanto você verifica os exemplos de código a seguir.

recursão com números

Todas as funções recursivas precisam de uma caixa de base para ser concluído. No entanto, o simples fato de adicionar um caso de base à nossa função não impedirá que ele funcione infinitamente. A função deve dar um passo para se aproximar do caso base. Finalmente, há o passo recursivo. Na etapa recursiva, o problema é reduzido a uma versão menor do problema.

Suponha que você tenha uma função que adicione os números de 1 a n. Por exemplo, se n = 4, a função adicionará 1 + 2 + 3 + 4.

primeiro, determinamos a caixa de base. Encontrar o caso da base é como encontrar o caso em que o problema pode ser resolvido sem recursão. Neste exemplo é quando n é igual a zero. Zero não tem partes, portanto, nossa recursão pode parar ao chegar a 0.

Em cada etapa, você subtrairá o valor para o número atual. Qual é o caso recursivo? O caso recursivo é a função suma invocada com o número reduzido.

function sum(num){ if (num === 0) { return 0; } else { return num + sum(--num) }}sum(4); //10

É o que acontece em cada etapa:

• Ir para a soma (4).
• 4 é igual a 0? Não. Coloque a soma (4) em espera e vá para a soma (3).
• 3 é igual a 0? Não. Coloque a soma (3) em espera e vá para a soma (2).
• 2 é igual a 0? Não. Coloque a soma (2) em espera e vá para a soma (1).
• 1 é igual a 0? Não. Lugar soma (1) em espera e ir para a soma (0).
• 0 é igual a 0? Sim Avaliar a soma (0).
• RETA SUM (1).
• soma retra (2).
• RETA SUM (3).
• RETA soma (4).

esta é outra maneira de ver como a função está processando cada chamada:

sum(4)4 + sum(3)4 + ( 3 + sum(2) )4 + ( 3 + ( 2 + sum(1) ))4 + ( 3 + ( 2 + ( 1 + sum(0) )))4 + ( 3 + ( 2 + ( 1 + 0 ) ))4 + ( 3 + ( 2 + 1 ) )4 + ( 3 + 3 ) 4 + 6 10

O argumento deve mudar no caso recursivo e abordar o caso base. Este argumento deve ser verificado no caso de base. No exemplo anterior, uma vez que estamos restaurando o valor um no caso recursivo, devemos verificar se o argumento é igual a zero em nosso caso base.

tarefa

1. implementar a função SUME usando um ciclo em vez de recursion.
2. cria uma função que multiplica dois números recursivamente. Por exemplo, multiply(2,4) irá resultar em 8. Escrever o que acontece durante cada etapa para multiply(2,4)

Recursão com listas

A recursão em uma lista é semelhante à recursão em um número, mas em vez de reduzir o número em cada etapa, reduziremos a lista em cada etapa até que tenhamos uma lista vazia.

Considere a função SUM que recebe uma lista como uma entrada e retorna a soma de todos os elementos dessa lista. Esta é uma implementação para a função de soma:

function sum(l){ if (empty(l)) { return 0; } else { return car(l) + sum(cdr(l)); }}

A função empty Retorna o valor verdadeiro (verdadeiro) se A lista não tem elementos. A função car retorna o primeiro elemento na lista. Por exemplo, car() Retorna o valor 1. A função cdr Retorna a lista sem o primeiro elemento. Por exemplo, cdr() retorna. O que acontece quando executamos sum()

sum()1 + sum()1 + ( 2 + sum() )1 + ( 2 + ( 3 + sum() ))1 + ( 2 + ( 3 + ( 4 + sum() )))1 + ( 2 + ( 3 + ( 4 + 0 ) ))1 + ( 2 + ( 3 + 4 ) )1 + ( 2 + 7 ) 1 + 910

Ao executar a recursão em uma lista é revisada se estiver vazia. Caso contrário, o passo recursivo é realizado em uma versão reduzida da lista.

Tarefa

1. Retriba esta função de soma para que você use um ciclo para adicionar cada elemento A lista em vez de usar a recursão.
2. Define uma função chamada Comprimento (comprimento) que recebe uma lista como uma entrada e retorna o número de itens nessa lista. Você não deve usar a função de comprimento integrada em JavaScript. Por exemplo, length() deve retornar o valor 4. Escreva o que acontece em cada etapa.

listas de construção

no Último exemplo que estávamos retornando um número. Mas suponha que queremos devolver uma lista. Isso significa que, em vez de adicionar um número à nossa etapa recursiva, precisamos adicionar uma lista. Considere a função remove (delete), que recebe um item e uma lista como uma entrada e retorna a lista sem o elemento que queremos remover. Apenas o primeiro elemento que encontramos será eliminado.

function remove(item, l){ if (empty(l)) { return ; } else if (eq(car(l), item)) { return cdr(l); } else { return cons(car(l), remove(item, cdr(l))); }}remove('c', ) //

Aqui, a função eq Retorna um valor verdadeiro (true) se ambas as entradas forem iguais. O cons recebe um elemento e uma lista como entradas e retorna uma nova lista com o item adicionado no início dele.

Verificamos se o primeiro elemento da lista é igual ao elemento que queremos excluir. Em caso afirmativo, excluir o primeiro elemento da lista e retorna a nova lista. Se o primeiro elemento não for igual ao elemento que queremos excluir, tomamos o primeiro elemento da lista e adicioná-lo ao passo recursivo. A etapa recursiva conterá a lista com o primeiro elemento eliminado.

Continuaremos a eliminar elementos até chegarmos ao nosso caso de base, que é uma lista vazia. Uma lista vazia significa que viajamos todos os seus elementos. O que a função faz remove('c', )

remove('c', )cons( ‘a’, remove(‘c’, ) )cons( ‘a’ , cons( ‘b’, remove(‘c’, ) ))cons( ‘a’, cons( ‘b’, )cons( ‘a’, )

em uma situação em que precisamos construir uma lista, tomamos O primeiro elemento e adicioná-lo à parte recursiva da nossa lista.

Tarefa

1. retonhe a função Remover para que você use ciclos em vez de recursão para excluir um item de Uma lista.
2. Modifique a função Remover para remover todas as ocorrências de um item em uma lista. Por exemplo, remove(‘c’, retorna. Escreva o que acontece passo a passo.

revisão

Uma função recursiva tem três partes. O primeiro é o caso base, que é a condição terminal. O segundo é o passo que vem ao nosso caso de base. O terceiro é o passo recursivo, no qual a função é invocada com uma entrada reduzida.

A recursão é como iteração. Qualquer função que você possa definir recursivamente também pode ser definida usando ciclos. Outros aspectos a considerar ao usar esta técnica são a recursão em listas aninhadas e a otimização de suas chamadas recursivas.

Um grande recurso para continuar aprendendo sobre a recursão é o livro o pequeno esquema. Isso ensina a pensar recursivamente usando um formato de perguntas e respostas.