Voltemos às funções e estudemo-las mais a fundo.
Nosso primeiro tópico será recursão .
Se você não é iniciante em programação, provavelmente ela já está familiarizada e você pode pular este capítulo.
A recursão é um padrão de programação útil em situações em que uma tarefa pode ser naturalmente dividida em várias tarefas do mesmo tipo, porém mais simples. Ou quando uma tarefa pode ser simplificada em uma ação fácil mais uma variante mais simples da mesma tarefa. Ou, como veremos em breve, para lidar com determinadas estruturas de dados.
Quando uma função resolve uma tarefa, no processo ela pode chamar muitas outras funções. Um caso parcial disso é quando uma função chama a si mesma . Isso é chamado de recursão .
Para começar algo simples – vamos escrever uma função pow(x, n) que eleva x a uma potência natural de n . Em outras palavras, multiplica x por si mesmo n vezes.
pow(2, 2) = 4 pow(2, 3) = 8 pow(2, 4) = 16
Existem duas maneiras de implementá-lo.
Pensamento iterativo: o loop for :
função pow(x, n) {
deixe resultado = 1;
//multiplica o resultado por x n vezes no loop
for (seja i = 0; i < n; i++) {
resultado *=x;
}
resultado de retorno;
}
alerta( pow(2, 3) ); // 8Pensamento recursivo: simplifique a tarefa e chame a si mesmo:
função pow(x, n) {
se (n == 1) {
retornar x;
} outro {
retornar x * pow(x, n - 1);
}
}
alerta( pow(2, 3) ); // 8Observe como a variante recursiva é fundamentalmente diferente.
Quando pow(x, n) é chamado, a execução se divide em duas ramificações:
se n == 1 = x
/
pow(x, n) =
senão = x * pow(x, n - 1) Se n == 1 , então tudo é trivial. É chamada de base da recursão porque produz imediatamente o resultado óbvio: pow(x, 1) é igual x .
Caso contrário, podemos representar pow(x, n) como x * pow(x, n - 1) . Em matemática, alguém escreveria x n = x * x n-1 . Isso é chamado de passo recursivo : transformamos a tarefa em uma ação mais simples (multiplicação por x ) e uma chamada mais simples da mesma tarefa ( pow com menor n ). As próximas etapas simplificam cada vez mais até n atingir 1 .
Também podemos dizer que pow se autodenomina recursivamente até n == 1 .
Por exemplo, para calcular pow(2, 4) a variante recursiva executa estas etapas:
pow(2, 4) = 2 * pow(2, 3)
pow(2, 3) = 2 * pow(2, 2)
pow(2, 2) = 2 * pow(2, 1)
pow(2, 1) = 2
Assim, a recursão reduz uma chamada de função a uma mais simples, e então – a uma ainda mais simples, e assim por diante, até que o resultado se torne óbvio.
A recursão geralmente é mais curta
Uma solução recursiva geralmente é mais curta que uma iterativa.
Aqui podemos reescrever o mesmo usando o operador condicional ? em vez de if para tornar pow(x, n) mais conciso e ainda muito legível:
função pow(x, n) {
retornar (n == 1)? x : (x * pow(x, n - 1));
} O número máximo de chamadas aninhadas (incluindo a primeira) é chamado profundidade de recursão . No nosso caso, será exatamente n .
A profundidade máxima de recursão é limitada pelo mecanismo JavaScript. Podemos confiar que será 10.000, alguns motores permitem mais, mas 100.000 provavelmente está fora do limite para a maioria deles. Existem otimizações automáticas que ajudam a aliviar isso (“otimizações de chamadas finais”), mas elas ainda não são suportadas em todos os lugares e funcionam apenas em casos simples.
Isso limita a aplicação da recursão, mas ainda permanece muito ampla. Existem muitas tarefas em que o modo de pensar recursivo fornece um código mais simples e mais fácil de manter.
Agora vamos examinar como funcionam as chamadas recursivas. Para isso, examinaremos os bastidores das funções.
As informações sobre o processo de execução de uma função em execução são armazenadas em seu contexto de execução .
O contexto de execução é uma estrutura de dados interna que contém detalhes sobre a execução de uma função: onde está o fluxo de controle agora, as variáveis atuais, o valor this (não usamos aqui) e alguns outros detalhes internos.
Uma chamada de função possui exatamente um contexto de execução associado a ela.
Quando uma função faz uma chamada aninhada, acontece o seguinte:
A função atual está pausada.
O contexto de execução associado a ele é lembrado em uma estrutura de dados especial chamada pilha de contexto de execução .
A chamada aninhada é executada.
Depois de terminar, o contexto de execução antigo é recuperado da pilha e a função externa é retomada de onde parou.
Vamos ver o que acontece durante a chamada pow(2, 3) .
No início da chamada pow(2, 3) o contexto de execução irá armazenar variáveis: x = 2, n = 3 , o fluxo de execução está na linha 1 da função.
Podemos esboçá-lo como:
Contexto: { x: 2, n: 3, na linha 1 } pow(2, 3)
É quando a função começa a ser executada. A condição n == 1 é falsa, então o fluxo continua no segundo ramo de if :
função pow(x, n) {
se (n == 1) {
retornar x;
} outro {
retornar x * pow(x, n - 1);
}
}
alerta( pow(2, 3) );As variáveis são as mesmas, mas a linha muda, então o contexto agora é:
Contexto: { x: 2, n: 3, na linha 5 } pow(2, 3)
Para calcular x * pow(x, n - 1) , precisamos fazer uma subchamada de pow com novos argumentos pow(2, 2) .
Para fazer uma chamada aninhada, o JavaScript lembra o contexto de execução atual na pilha de contexto de execução .
Aqui chamamos a mesma função pow , mas isso não importa. O processo é o mesmo para todas as funções:
O contexto atual é “lembrado” no topo da pilha.
O novo contexto é criado para a subchamada.
Quando a subchamada termina – o contexto anterior é retirado da pilha e sua execução continua.
Aqui está a pilha de contexto quando entramos na subchamada pow(2, 2) :
Contexto: { x: 2, n: 2, na linha 1 } pow(2, 2)
Contexto: { x: 2, n: 3, na linha 5 } pow(2, 3)
O novo contexto de execução atual está no topo (e em negrito), e os contextos anteriores lembrados estão abaixo.
Quando finalizamos a subchamada – é fácil retomar o contexto anterior, pois mantém ambas as variáveis e o local exato do código onde parou.
Observe:
Aqui na imagem usamos a palavra “linha”, pois em nosso exemplo há apenas uma subchamada em linha, mas geralmente uma única linha de código pode conter múltiplas subchamadas, como pow(…) + pow(…) + somethingElse(…) .
Portanto seria mais preciso dizer que a execução recomeça “imediatamente após a subchamada”.
O processo se repete: uma nova subchamada é feita na linha 5 , agora com argumentos x=2 , n=1 .
Um novo contexto de execução é criado, o anterior é colocado no topo da pilha:
Contexto: { x: 2, n: 1, na linha 1 } pow(2, 1)
Contexto: { x: 2, n: 2, na linha 5 } pow(2, 2)
Contexto: { x: 2, n: 3, na linha 5 } pow(2, 3)
Existem 2 contextos antigos agora e 1 atualmente em execução pow(2, 1) .
Durante a execução de pow(2, 1) , diferentemente de antes, a condição n == 1 é verdadeira, então o primeiro ramo de if funciona:
função pow(x, n) {
se (n == 1) {
retornar x;
} outro {
retornar x * pow(x, n - 1);
}
} Não há mais chamadas aninhadas, então a função termina retornando 2 .
À medida que a função termina, seu contexto de execução não é mais necessário, sendo então removido da memória. O anterior é restaurado do topo da pilha:
Contexto: { x: 2, n: 2, na linha 5 } pow(2, 2)
Contexto: { x: 2, n: 3, na linha 5 } pow(2, 3)
A execução de pow(2, 2) é retomada. Possui o resultado da subchamada pow(2, 1) , portanto também pode finalizar a avaliação de x * pow(x, n - 1) , retornando 4 .
Então o contexto anterior é restaurado:
Contexto: { x: 2, n: 3, na linha 5 } pow(2, 3)
Quando terminar, temos o resultado de pow(2, 3) = 8 .
A profundidade de recursão neste caso foi: 3 .
Como podemos ver nas ilustrações acima, a profundidade da recursão é igual ao número máximo de contexto na pilha.
Observe os requisitos de memória. Contextos exigem memória. No nosso caso, elevar à potência de n na verdade requer memória para n contextos, para todos os valores mais baixos de n .
Um algoritmo baseado em loop economiza mais memória:
função pow(x, n) {
deixe resultado = 1;
for (seja i = 0; i < n; i++) {
resultado *=x;
}
resultado de retorno;
} O pow iterativo usa um único contexto alterando i e result no processo. Seus requisitos de memória são pequenos, fixos e não dependem de n .
Qualquer recursão pode ser reescrita como um loop. A variante de loop geralmente pode ser mais eficaz.
…Mas às vezes a reescrita não é trivial, especialmente quando uma função usa diferentes subchamadas recursivas dependendo das condições e mescla seus resultados ou quando a ramificação é mais complexa. E a otimização pode ser desnecessária e não valer totalmente os esforços.
A recursão pode fornecer um código mais curto, mais fácil de entender e suportar. Não são necessárias otimizações em todos os lugares, principalmente precisamos de um bom código, por isso é utilizado.
Outra ótima aplicação da recursão é a travessia recursiva.
Imagine, temos uma empresa. A estrutura de pessoal pode ser apresentada como um objeto:
deixe empresa = {
vendas: [{
nome: 'João',
salário: 1000
}, {
nome: 'Alice',
salário: 1600
}],
desenvolvimento: {
sites: [{
nome: 'Pedro',
salário: 2000
}, {
nome: 'Alex',
salário: 1800
}],
internos: [{
nome: 'Jack',
salário: 1300
}]
}
};Em outras palavras, uma empresa possui departamentos.
Um departamento pode ter uma variedade de funcionários. Por exemplo, o departamento sales possui 2 funcionários: John e Alice.
Ou um departamento pode ser dividido em subdepartamentos, como se development tivesse duas filiais: sites e internals . Cada um deles tem sua própria equipe.
Também é possível que quando um subdepartamento cresce, ele se divida em subsubdepartamentos (ou equipes).
Por exemplo, o departamento sites no futuro poderá ser dividido em equipes para siteA e siteB . E eles, potencialmente, podem dividir-se ainda mais. Isso não está na foto, apenas algo para ter em mente.
Agora digamos que queremos uma função que obtenha a soma de todos os salários. Como podemos fazer isso?
Uma abordagem iterativa não é fácil porque a estrutura não é simples. A primeira ideia pode ser fazer for loop for na company com subloop aninhado nos departamentos de 1º nível. Mas então precisamos de mais subloops aninhados para iterar sobre a equipe em departamentos de 2º nível, como sites ... E então outro subloop dentro daqueles para departamentos de 3º nível que pode aparecer no futuro? Se colocarmos 3-4 subloops aninhados no código para percorrer um único objeto, ele se tornará bastante feio.
Vamos tentar a recursão.
Como podemos ver, quando nossa função soma um departamento, existem dois casos possíveis:
Ou é um departamento “simples” com uma variedade de pessoas – então podemos somar os salários em um ciclo simples.
Ou é um objeto com N subdepartamentos – então podemos fazer N chamadas recursivas para obter a soma de cada um dos subdepartamentos e combinar os resultados.
O primeiro caso é a base da recursão, o caso trivial, quando obtemos um array.
O segundo caso quando obtemos um objeto é a etapa recursiva. Uma tarefa complexa é dividida em subtarefas para departamentos menores. Eles podem, por sua vez, dividir-se novamente, mas mais cedo ou mais tarde a divisão terminará em (1).
O algoritmo é provavelmente ainda mais fácil de ler no código:
let company = { // o mesmo objeto, compactado por questões de brevidade
vendas: [{nome: 'John', salário: 1000}, {nome: 'Alice', salário: 1600 }],
desenvolvimento: {
sites: [{nome: 'Peter', salário: 2000}, {nome: 'Alex', salário: 1800 }],
internos: [{nome: 'Jack', salário: 1300}]
}
};
//A função para fazer o trabalho
function somaSalários(departamento) {
if (Array.isArray(departamento)) { // caso (1)
return departamento.reduce((anterior, atual) => anterior + atual.salário, 0); //soma o array
} else { // caso (2)
seja soma = 0;
for (deixe subdep de Object.values(department)) {
soma += somaSalários(subdep); // chama recursivamente os subdepartamentos, soma os resultados
}
soma de retorno;
}
}
alert(somaSalários(empresa)); //7700O código é curto e fácil de entender (espero?). Esse é o poder da recursão. Também funciona para qualquer nível de aninhamento de subdepartamentos.
Aqui está o diagrama de chamadas:
Podemos facilmente perceber o princípio: para um objeto {...} são feitas subchamadas, enquanto os arrays [...] são as “folhas” da árvore de recursão, eles dão resultado imediato.
Observe que o código usa recursos inteligentes que abordamos anteriormente:
Método arr.reduce explicado no capítulo Métodos de array para obter a soma do array.
Loop for(val of Object.values(obj)) para iterar sobre os valores dos objetos: Object.values retorna uma matriz deles.
Uma estrutura de dados recursiva (definida recursivamente) é uma estrutura que se replica em partes.
Acabamos de ver isso no exemplo de estrutura de empresa acima.
Um departamento da empresa é:
Ou uma série de pessoas.
Ou um objeto com departamentos .
Para desenvolvedores web existem exemplos muito mais conhecidos: documentos HTML e XML.
No documento HTML, uma tag HTML pode conter uma lista de:
Pedaços de texto.
Comentários HTML.
Outras tags HTML (que por sua vez podem conter trechos de texto/comentários ou outras tags, etc.).
Essa é mais uma vez uma definição recursiva.
Para melhor compreensão, abordaremos mais uma estrutura recursiva chamada “Lista vinculada” que pode ser uma alternativa melhor para arrays em alguns casos.
Imagine, queremos armazenar uma lista ordenada de objetos.
A escolha natural seria um array:
deixe arr = [obj1, obj2, obj3];
…Mas há um problema com arrays. As operações “excluir elemento” e “inserir elemento” são caras. Por exemplo, a operação arr.unshift(obj) precisa renumerar todos os elementos para abrir espaço para um novo obj e, se o array for grande, isso leva tempo. O mesmo com arr.shift() .
As únicas modificações estruturais que não requerem renumeração em massa são aquelas que operam com o final do array: arr.push/pop . Então um array pode ser bem lento para filas grandes, quando temos que trabalhar desde o início.
Alternativamente, se realmente precisarmos de inserção/exclusão rápida, podemos escolher outra estrutura de dados chamada lista vinculada.
O elemento da lista vinculada é definido recursivamente como um objeto com:
value .
next propriedade referenciando o próximo elemento da lista vinculada ou null se esse for o fim.
Por exemplo:
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
};Representação gráfica da lista:
Um código alternativo para criação:
deixe lista = {valor: 1};
lista.próximo = {valor: 2};
lista.próximo.próximo = {valor: 3};
lista.próximo.próximo.próximo = {valor: 4};
lista.próximo.próximo.próximo.próximo = null; Aqui podemos ver ainda mais claramente que existem vários objetos, cada um tem o value e next aponta para o vizinho. A variável list é o primeiro objeto da cadeia, portanto, seguindo next ponteiros dela, podemos alcançar qualquer elemento.
A lista pode ser facilmente dividida em várias partes e posteriormente unida novamente:
deixe segundaLista = lista.próximo.próximo; lista.próximo.próximo = null;
Para participar:
lista.próximo.próximo = segundaLista;
E com certeza podemos inserir ou retirar itens em qualquer lugar.
Por exemplo, para acrescentar um novo valor, precisamos atualizar o cabeçalho da lista:
deixe lista = {valor: 1};
lista.próximo = {valor: 2};
lista.próximo.próximo = {valor: 3};
lista.próximo.próximo.próximo = {valor: 4};
// acrescenta o novo valor à lista
lista = { valor: "novo item", próximo: lista }; Para remover um valor do meio, altere next do anterior:
lista.próximo = lista.próximo.próximo;
Fizemos list.next saltar de 1 para o valor 2 . O valor 1 agora está excluído da cadeia. Se não estiver armazenado em nenhum outro lugar, será automaticamente removido da memória.
Ao contrário dos arrays, não há renumeração em massa, podemos reorganizar os elementos facilmente.
Naturalmente, as listas nem sempre são melhores que os arrays. Caso contrário, todos usariam apenas listas.
A principal desvantagem é que não podemos acessar facilmente um elemento pelo seu número. Em um array isso é fácil: arr[n] é uma referência direta. Mas na lista precisamos começar do primeiro item e next N vezes para obter o enésimo elemento.
…Mas nem sempre precisamos dessas operações. Por exemplo, quando precisamos de uma fila ou mesmo deque – a estrutura ordenada que deve permitir adicionar/remover elementos muito rapidamente de ambas as extremidades, mas não é necessário acesso ao seu meio.
As listas podem ser aprimoradas:
Podemos adicionar a propriedade prev além de next para fazer referência ao elemento anterior, para voltar facilmente.
Também podemos adicionar uma variável chamada tail referenciando o último elemento da lista (e atualizá-la ao adicionar/remover elementos do final).
…A estrutura dos dados pode variar de acordo com as nossas necessidades.
Termos:
Recursão é um termo de programação que significa chamar uma função por si mesma. Funções recursivas podem ser usadas para resolver tarefas de maneira elegante.
Quando uma função chama a si mesma, isso é chamado de etapa de recursão . A base da recursão são argumentos de função que tornam a tarefa tão simples que a função não faz mais chamadas.
Uma estrutura de dados definida recursivamente é uma estrutura de dados que pode ser definida por si mesma.
Por exemplo, a lista vinculada pode ser definida como uma estrutura de dados que consiste em um objeto que faz referência a uma lista (ou nula).
lista = { valor, próximo -> lista }Árvores como a árvore de elementos HTML ou a árvore de departamentos deste capítulo também são naturalmente recursivas: elas têm ramificações e cada ramificação pode ter outras ramificações.
Funções recursivas podem ser usadas para percorrê-las, como vimos no exemplo sumSalary .
Qualquer função recursiva pode ser reescrita em uma função iterativa. E isso às vezes é necessário para otimizar coisas. Mas para muitas tarefas uma solução recursiva é rápida o suficiente e mais fácil de escrever e suportar.
importância: 5
Escreva uma função sumTo(n) que calcule a soma dos números 1 + 2 + ... + n .
Por exemplo:
somaPara(1) = 1 somaPara(2) = 2 + 1 = 3 somaPara(3) = 3 + 2 + 1 = 6 somaPara(4) = 4 + 3 + 2 + 1 = 10 ... somaPara(100) = 100 + 99 + ... + 2 + 1 = 5050
Faça 3 variantes de solução:
Usando um loop for.
Usando uma recursão, faça com que sumTo(n) = n + sumTo(n-1) for n > 1 .
Usando a fórmula de progressão aritmética.
Um exemplo do resultado:
function sumTo(n) { /*... seu código ... */ }
alerta(somaTo(100) ); //5050PS Qual variante de solução é a mais rápida? O mais lento? Por que?
PPS Podemos usar recursão para contar sumTo(100000) ?
A solução usando um loop:
função somaPara(n) {
seja soma = 0;
for (seja i = 1; i <= n; i++) {
soma += eu;
}
soma de retorno;
}
alerta(somaTo(100) );A solução usando recursão:
função somaPara(n) {
se (n == 1) retornar 1;
retornar n + somaTo(n - 1);
}
alerta(somaTo(100) ); A solução usando a fórmula: sumTo(n) = n*(n+1)/2 :
função somaPara(n) {
retornar n * (n + 1)/2;
}
alerta(somaTo(100) ); PS Naturalmente, a fórmula é a solução mais rápida. Ele usa apenas 3 operações para qualquer número n . A matemática ajuda!
A variante loop é a segunda em termos de velocidade. Tanto na variante recursiva quanto na variante de loop, somamos os mesmos números. Mas a recursão envolve chamadas aninhadas e gerenciamento de pilha de execução. Isso também consome recursos, por isso é mais lento.
PPS Alguns mecanismos suportam a otimização de “chamada final”: se uma chamada recursiva for a última na função, sem nenhum outro cálculo realizado, então a função externa não precisará retomar a execução, então o mecanismo não precisa lembre-se de seu contexto de execução. Isso elimina a carga na memória. Mas se o mecanismo JavaScript não suportar a otimização de chamada final (a maioria deles não), ocorrerá um erro: tamanho máximo da pilha excedido, porque geralmente há uma limitação no tamanho total da pilha.
importância: 4
O fatorial de um número natural é um número multiplicado por "number minus one" , depois por "number minus two" e assim por diante até 1 . O fatorial de n é denotado como n!
Podemos escrever uma definição de fatorial assim:
não! = n * (n - 1) * (n - 2) * ...*1
Valores de fatoriais para diferentes n :
1! = 1 2! = 2 * 1 = 2 3! = 3 * 2 * 1 = 6 4! = 4*3*2*1 = 24 5! = 5*4*3*2*1 = 120
A tarefa é escrever uma função factorial(n) que calcule n! usando chamadas recursivas.
alerta(fatorial(5) ); // 120
PS Dica: n! pode ser escrito como n * (n-1)! Por exemplo: 3! = 3*2! = 3*2*1! = 6
Por definição, um fatorial n! pode ser escrito como n * (n-1)! .
Em outras palavras, o resultado de factorial(n) pode ser calculado como n multiplicado pelo resultado de factorial(n-1) . E a chamada para n-1 pode descer recursivamente cada vez mais, até 1 .
função fatorial(n) {
retornar (n! = 1)? n * fatorial (n - 1): 1;
}
alerta(fatorial(5) ); // 120 A base da recursão é o valor 1 . Também podemos fazer 0 a base aqui, não importa muito, mas dá mais um passo recursivo:
função fatorial(n) {
retornar n? n * fatorial (n - 1): 1;
}
alerta(fatorial(5) ); // 120importância: 5
A sequência de números de Fibonacci tem a fórmula F n = F n-1 + F n-2 . Em outras palavras, o próximo número é a soma dos dois anteriores.
Os primeiros dois números são 1 , depois 2(1+1) , depois 3(1+2) , 5(2+3) e assim por diante: 1, 1, 2, 3, 5, 8, 13, 21... .
Os números de Fibonacci estão relacionados à proporção áurea e a muitos fenômenos naturais que nos rodeiam.
Escreva uma função fib(n) que retorne o n-th número de Fibonacci.
Um exemplo de trabalho:
function fib(n) { /* seu código */ }
alerta(mentira(3)); //2
alerta(fib(7)); //13
alerta(fib(77)); //5527939700884757 PS A função deve ser rápida. A chamada para fib(77) não deve demorar mais do que uma fração de segundo.
A primeira solução que poderíamos tentar aqui é a recursiva.
Os números de Fibonacci são recursivos por definição:
função fib(n) {
retornar n <= 1? n : fib(n - 1) + fib(n - 2);
}
alerta(fib(3) ); //2
alerta(fib(7) ); //13
//fib(77); // será extremamente lento! …Mas para grandes valores de n é muito lento. Por exemplo, fib(77) pode travar o mecanismo por algum tempo, consumindo todos os recursos da CPU.
Isso ocorre porque a função faz muitas subchamadas. Os mesmos valores são reavaliados repetidas vezes.
Por exemplo, vamos ver alguns cálculos para fib(5) :
... mentira(5) = mentira(4) + mentira(3) mentira(4) = mentira(3) + mentira(2) ...
Aqui podemos ver que o valor de fib(3) é necessário para fib(5) e fib(4) . Portanto, fib(3) será chamado e avaliado duas vezes de forma totalmente independente.
Aqui está a árvore de recursão completa:
Podemos notar claramente que fib(3) é avaliado duas vezes e fib(2) é avaliado três vezes. A quantidade total de cálculos cresce muito mais rápido que n , tornando-a enorme mesmo para n=77 .
Podemos otimizar isso lembrando valores já avaliados: se um valor de digamos fib(3) for calculado uma vez, então podemos simplesmente reutilizá-lo em cálculos futuros.
Outra variante seria abandonar a recursão e usar um algoritmo baseado em loop totalmente diferente.
Em vez de ir de n para valores mais baixos, podemos fazer um loop que começa em 1 e 2 , então obtém fib(3) como sua soma, então fib(4) como a soma dos dois valores anteriores, então fib(5) e sobe e sobe, até chegar ao valor necessário. Em cada etapa precisamos apenas lembrar dois valores anteriores.
Aqui estão as etapas do novo algoritmo em detalhes.
O começo:
// a = fib(1), b = fib(2), esses valores são por definição 1 seja a = 1, b = 1; // obtém c = fib(3) como sua soma seja c = a + b; /* agora temos fib(1), fib(2), fib(3) um b c 1, 1, 2 */
Agora queremos obter fib(4) = fib(2) + fib(3) .
Vamos mudar as variáveis: a,b obterá fib(2),fib(3) e c obterá sua soma:
uma =b; // agora a = fib(2) b=c; // agora b = fib(3) c = a + b; //c = fib(4) /* agora temos a sequência: um b c 1, 1, 2, 3 */
A próxima etapa fornece outro número de sequência:
uma =b; // agora a = fib(3)
b=c; // agora b = fib(4)
c = a + b; //c = fib(5)
/* agora a sequência é (mais um número):
um b c
1, 1, 2, 3, 5
*/…E assim por diante até obtermos o valor necessário. Isso é muito mais rápido que a recursão e não envolve cálculos duplicados.
O código completo:
função fib(n) {
seja a = 1;
seja b = 1;
para (seja i = 3; i <= n; i++) {
seja c = a + b;
uma =b;
b=c;
}
retornar b;
}
alerta(fib(3) ); //2
alerta(fib(7) ); //13
alerta(fib(77) ); //5527939700884757 O loop começa com i=3 , porque o primeiro e o segundo valores da sequência são codificados nas variáveis a=1 , b=1 .
A abordagem é chamada de programação dinâmica bottom-up.
importância: 5
Digamos que temos uma lista uniligada (conforme descrito no capítulo Recursão e pilha):
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
}; Escreva uma função printList(list) que produza os itens da lista um por um.
Faça duas variantes da solução: usando um loop e usando recursão.
O que é melhor: com recursão ou sem?
A variante baseada em loop da solução:
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
};
function printList(lista) {
deixe tmp = lista;
enquanto (tmp) {
alerta(tmp.valor);
tmp = tmp.próximo;
}
}
printList(lista); Observe que usamos uma variável temporária tmp para percorrer a lista. Tecnicamente, poderíamos usar uma list de parâmetros de função:
function printList(lista) {
enquanto(lista) {
alerta(lista.valor);
lista = lista.próximo;
}
} …Mas isso seria imprudente. No futuro poderemos precisar estender uma função, fazer outra coisa com a lista. Se mudarmos list , perderemos essa capacidade.
Falando em bons nomes de variáveis, list aqui é a própria lista. O primeiro elemento disso. E deveria permanecer assim. Isso é claro e confiável.
Por outro lado, o papel do tmp é exclusivamente percorrer uma lista, como i no loop for .
A variante recursiva de printList(list) segue uma lógica simples: para gerar uma lista, devemos exibir o elemento atual list e fazer o mesmo para list.next :
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
};
function printList(lista) {
alerta(lista.valor); // mostra o item atual
if (lista.próximo) {
printList(lista.próximo); //faça o mesmo para o resto da lista
}
}
printList(lista);Agora, o que é melhor?
Tecnicamente, o loop é mais eficaz. Essas duas variantes fazem o mesmo, mas o loop não gasta recursos para chamadas de funções aninhadas.
Por outro lado, a variante recursiva é mais curta e às vezes mais fácil de entender.
importância: 5
Produza uma lista vinculada única da tarefa anterior Produza uma lista vinculada única na ordem inversa.
Faça duas soluções: usando um loop e usando uma recursão.
A lógica recursiva é um pouco complicada aqui.
Precisamos primeiro gerar o resto da lista e depois gerar a atual:
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
};
function printReverseList(lista) {
if (lista.próximo) {
printReverseList(lista.próximo);
}
alerta(lista.valor);
}
printReverseList(lista);
A variante de loop também é um pouco mais complicada que a saída direta.
Não há como obter o último valor da nossa list . Também não podemos “voltar”.
Então, o que podemos fazer é primeiro percorrer os itens na ordem direta e lembrá-los em uma matriz e, em seguida, exibir o que lembramos na ordem inversa:
deixe lista = {
valor: 1,
próximo: {
valor: 2,
próximo: {
valor: 3,
próximo: {
valor: 4,
próximo: nulo
}
}
}
};
function printReverseList(lista) {
deixe arr = [];
deixe tmp = lista;
enquanto (tmp) {
arr.push(tmp.valor);
tmp = tmp.próximo;
}
for (seja i = arr.length - 1; i >= 0; i--) {
alerta(arr[i]);
}
}
printReverseList(lista);Observe que a solução recursiva na verdade faz exatamente a mesma coisa: ela segue a lista, lembra os itens na cadeia de chamadas aninhadas (na pilha de contexto de execução) e depois os gera.