Conteúdo principal

Melhorando a eficiência das funções recursivas

A recursão pode ser uma maneira elegante de resolver um problema, e muitos algoritmos se prestam a soluções recursivas. No entanto, algoritmos recursivos podem ser ineficientes em termos de tempo e espaço. Aqui, vamos explorar várias técnicas para melhorar sua eficiência.

No desafio de programação para computar recursivamente o fatorial de um número, pedimos para você chamar a função várias vezes com valores diferentes.

Por exemplo, este código JavaScript chama factorial() 4 vezes:

factorial(0);
factorial(2);
factorial(5);
factorial(10);

Vamos considerar todas as chamadas que o computador faz ao executar essas 4 linhas de código:

Linha de código	Chamadas recursivas	Total de chamadas
`factorial(0)`		1 chamada
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 chamadas
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	6 chamadas
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)` → `factorial(4)` → `factorial(3)` → `factorial(2)` → `factorial(1)` → `factorial(0)`	11 chamadas

Observe que factorial(10) tem que fazer 11 chamadas de função, e 6 delas têm exatamente os mesmos argumentos e valores de retorno que as chamadas de função anteriores feitas durante factorial(5).

Memoização do fatorial

Podemos usar uma técnica chamada memoização para economizar tempo do computador ao fazer chamadas de funções idênticas. A memoização (uma forma de armazenamento em cache) lembra o resultado de uma chamada de função com entradas específicas em uma tabela de busca (o "memorando") e retorna esse resultado quando a função é chamada novamente com as mesmas entradas.

Uma memoização da função fatorial pode ser assim:

Se $n$ ‍ = 0, retorne 1
Caso contrário, se $n$ ‍ estiver no memorando, retorne o valor do memorando para $n$ ‍
Caso contrário,
- Calcule $(n - 1)! \times n$ ‍
- Armazene o resultado no memorando
- Retorne o resultado

Esse algoritmo verifica o valor de entrada no memorando antes de fazer uma chamada recursiva potencialmente cara. O memorando deve ser uma estrutura de dados com tempos de busca eficientes, como uma tabela de mapeamento com tempo de busca

O (1)

Se você quiser visualizar a execução do algoritmo memoizado implementado em JavaScript, assista a este vídeo ou execute a visualização você mesmo. Antes de assistir, você pode se desafiar a implementar o algoritmo na linguagem de sua escolha.

Com a memoização implementada, o computador pode fazer menos chamadas totais sobre chamadas repetidas para factorial():

Linha de código	Chamadas recursivas	Total de chamadas
`factorial(0)`		1 chamada
`factorial(2)`	`factorial(1)` → `factorial(0)`	3 chamadas
`factorial(5)`	`factorial(4)` → `factorial(3)` → `factorial(2)`	3 chamadas
`factorial(10)`	`factorial(9)` → `factorial(8)` → `factorial(7)` → `factorial(6)` → `factorial(5)`	6 chamadas

A memoização faz uma troca entre tempo e espaço. Contanto que a busca seja eficiente e a função seja chamada repetidamente, o computador pode economizar tempo com o custo de usar memória para armazenar o memorando.

Memoização de Fibonacci

No caso da função fatorial, um algoritmo só se beneficia da otimização da memoização quando um programa faz repetidas chamadas à função durante sua execução. Em alguns casos, no entanto, a memoização pode economizar tempo até para uma única chamada para uma função recursiva.

Vejamos um exemplo simples, o algoritmo para gerar números de Fibonacci.

A sequência de Fibonacci é uma série de números famosa em que o próximo número na sequência é a soma dos 2 números anteriores. Os dois primeiros números na sequência são definidos como

0

1

. Depois disso, o próximo número é

1

(de

0 + 1

) e o número depois disso é

2

(de

1 + 1

), e assim por diante.

Os primeiros 10 números de Fibonacci:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34

Uma função recursiva simples para gerar o

n

-ésimo número de Fibonacci se parece com isto:

Se $n$ ‍ é 0 ou 1, retorne $n$ ‍
Caso contrário, retorne $fibonacci (n - 1) + fibonacci (n - 2)$ ‍

Esse algoritmo é um exemplo de recursão múltipla, pois chama a si mesmo várias vezes. Para entender as várias chamadas que o computador faz, é importante visualizar as chamadas como uma árvore.

Quando

n = 5

, o computador faz 15 chamadas:

Invólucro do vídeo da Khan Academy

Recursive Fibonacci Calls (Diagrammed)Ver transcrição do vídeo

Observe as múltiplas chamadas para a função fibonacci para os valores de entrada de 3, 2, 1 e 0. À medida que a entrada aumenta, isso se torna cada vez mais ineficiente. Uma chamada para fibonacci(30) resulta em uma chamada fibonacci(2) feita pelo computador mais de meio milhão de vezes.

Podemos usar a memoização aqui para evitar que o computador recalcule um número de Fibonacci que já foi calculado.

A versão memoizada do algoritmo recursivo de Fibonacci se parece com isto:

Se $n$ ‍ for 0 ou 1, retorne $n$ ‍
Caso contrário, se $n$ ‍ estiver no memorando, retorne o valor do memorando para $n$ ‍
Caso contrário,
- Calcule $fibonacci (n - 1) + fibonacci (n - 2)$ ‍
- Armazene o resultado no memorando
- Retorne o resultado

Se você quiser visualizar a execução do algoritmo memoizado implementado em JavaScript, assista a este vídeo ou execute a visualização você mesmo.

Para

n = 5

, o computador faz 9 chamadas:

Invólucro do vídeo da Khan Academy

Memoized Recursive Fibonacci Calls (Diagrammed)Ver transcrição do vídeo

A versão original do algoritmo exigia 15 chamadas de função, então a memoização eliminou 6 chamadas de função.

Esta tabela mostra o número de chamadas necessárias de

n = 5

até

n = 10

$n$ ‍	Original	Memoizado
5	15	9
6	25	11
7	41	13
8	67	15
9	109	17
10	177	19

O número total de chamadas de função aumenta a uma taxa exponencial para o algoritmo original, mas a uma taxa linear muito mais lenta para o algoritmo memoizado.

O algoritmo memoizado requer mais espaço, no entanto; o suficiente para que o memorando armazene cada valor de retorno de

n

Abordagem de baixo para cima

Às vezes, a melhor maneira de aprimorar a eficiência de um algoritmo recursivo é não usar a recursão, ou recursividade.

No caso da geração de números de Fibonacci, uma técnica iterativa chamada abordagem de baixo para cima pode economizar tempo e espaço. Ao usar uma abordagem de baixo para cima, o computador encontra primeiro os subproblemas e usa os resultados parciais para chegar ao resultado final.

Uma abordagem de baixo para cima para a geração de números de Fibonacci se parece com isto:

Se $n$ ‍ for 0 ou 1, retorne $n$ ‍
Caso contrário,
- Crie a variável $doisAtrás$ ‍ para lembrar o resultado de $(n - 2)$ ‍ e inicie com 0
- Crie a variável $umAtrás$ ‍ para lembrar o resultado de $(n - 1)$ ‍ e inicie com 1
- Crie a variável $resultado$ ‍ para armazenar o resultado final e inicie com 0
- Repita $(n - 1)$ ‍ vezes:
  - Atualize $resultado$ ‍ para a soma de $doisAtrás$ ‍ mais $umAtrás$ ‍
  - Atualize $doisAtrás$ ‍ para armazenar o valor atual de $umAtrás$ ‍
  - Atualize $umAtrás$ ‍ para armazenar o valor atual de $resultado$ ‍
  - Retorne $resultado$ ‍

Essa abordagem nunca faz uma chamada recursiva; em vez disso, usa a iteração para somar os resultados parciais e calcular o número.

Se você quiser visualizar a execução do algoritmo de baixo para cima implementado em JavaScript, assista a este vídeo ou execute a visualização você mesmo.

O algoritmo de baixo para cima tem a mesma complexidade de tempo

O (n)

que o algoritmo memoizado, mas requer apenas o espaço

O (1)

, já que só guarda na memória três números por vez.

Programação dinâmica

Memoização e abordagem de baixo para cima são técnicas da programação dinâmica, uma estratégia de resolução de problemas usada em matemática e ciência da computação.

A programação dinâmica pode ser usada quando um problema tem subestrutura ótima e subproblemas sobrepostos. Subestrutura ótima significa que a solução ótima para o problema pode ser criada a partir de soluções ótimas de seus subproblemas. Em outras palavras, fib(5) pode ser calculado com fib(4) e fib(3). Subproblemas sobrepostos acontecem sempre que um subproblema é resolvido várias vezes, o que vimos quando fib(5) fez várias chamadas para fib(3) e fib(2) tipicamente recursivos.

A programação dinâmica pode ser usada para uma variedade de problemas e envolve técnicas além das que aprendemos aqui. Se você estiver trabalhando em um problema com subestrutura ótima e subproblemas sobrepostos, considere se uma abordagem de programação dinâmica pode funcionar.

Quer participar da conversa?

Entrar

Classificar por:

Nenhuma postagem por enquanto.

Você entende inglês? Clique aqui para ver mais debates na versão em inglês do site da Khan Academy.

Computer science theory

Curso: Computer science theory > Unidade 1

Memoização do fatorial

Memoização de Fibonacci

Abordagem de baixo para cima

Programação dinâmica

Quer participar da conversa?