Pular para o conteúdo principal

1.2.2 Recursão em Árvore

Outro padrão comum de computação é chamado de recursão em árvore. Como exemplo, considere o cálculo da sequência de números de Fibonacci, na qual cada número é a soma dos dois anteriores:

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

Em geral, os números de Fibonacci podem ser definidos pela regra:

  • Fib(n) = 0 se n = 0
  • Fib(n) = 1 se n = 1
  • Fib(n) = Fib(n - 1) + Fib(n - 2) caso contrário

Podemos traduzir imediatamente esta definição em uma função recursiva para calcular números de Fibonacci:

Exemplo de Código
function fib(n) {
  return n === 0
         ? 0
         : n === 1
         ? 1
         : fib(n - 1) + fib(n - 2);
}
Open on CodeSandboxOpen Sandbox

O processo recursivo em árvore gerado ao calcular fib(5)

Figura: O processo recursivo em árvore gerado ao calcular fib(5).

Considere o padrão desta computação. Para calcular fib(5), calculamos fib(4) e fib(3). Para calcular fib(4), calculamos fib(3) e fib(2). Em geral, o processo evoluído parece uma árvore, como mostrado na figura. Observe que os ramos se dividem em dois em cada nível (exceto na base); isso reflete o fato de que a função fib chama a si mesma duas vezes cada vez que é invocada.

Esta função é instrutiva como uma recursão em árvore prototípica, mas é uma maneira terrível de calcular números de Fibonacci porque faz muita computação redundante. Observe na figura que toda a computação de fib(3) — quase metade do trabalho — é duplicada. Na verdade, não é difícil mostrar que o número de vezes que a função calculará fib(1) ou fib(0) (o número de folhas na árvore acima, em geral) é precisamente Fib(n + 1). Para ter uma ideia de quão ruim isso é, pode-se mostrar que o valor de Fib(n) cresce exponencialmente com n. Mais precisamente (veja o exercício 1.13), Fib(n) é o inteiro mais próximo de φⁿ/√5, onde

φ = (1 + √5)/2 ≈ 1.6180

é a proporção áurea, que satisfaz a equação

φ² = φ + 1

Assim, o processo usa um número de passos que cresce exponencialmente com a entrada. Por outro lado, o espaço necessário cresce apenas linearmente com a entrada, porque precisamos apenas acompanhar quais nós estão acima de nós na árvore em qualquer ponto da computação. Em geral, o número de passos necessários para um processo recursivo em árvore será proporcional ao número de nós na árvore, enquanto o espaço necessário será proporcional à profundidade máxima da árvore.

Também podemos formular um processo iterativo para calcular os números de Fibonacci. A ideia é usar um par de inteiros a e b, inicializados em Fib(1) = 1 e Fib(0) = 0, e aplicar repetidamente as transformações simultâneas

a ← a + b b ← a

Não é difícil mostrar que, após aplicar essa transformação n vezes, a e b serão iguais, respectivamente, a Fib(n + 1) e Fib(n). Assim, podemos calcular números de Fibonacci iterativamente usando a função:

Exemplo de Código
function fib(n) {
  return fib_iter(1, 0, n);
}
function fib_iter(a, b, count) {
  return count === 0
         ? b
         : fib_iter(a + b, a, count - 1);
}
Open on CodeSandboxOpen Sandbox

Este segundo método para calcular Fib(n) é uma iteração linear. A diferença no número de passos necessários pelos dois métodos — um linear em n, outro crescendo tão rápido quanto o próprio Fib(n) — é enorme, mesmo para entradas pequenas.

Não se deve concluir disso que processos recursivos em árvore são inúteis. Quando consideramos processos que operam em dados estruturados hierarquicamente em vez de números, descobriremos que a recursão em árvore é uma ferramenta natural e poderosa. Mas mesmo em operações numéricas, processos recursivos em árvore podem ser úteis para nos ajudar a entender e projetar programas. Por exemplo, embora a primeira função fib seja muito menos eficiente do que a segunda, ela é mais direta, sendo pouco mais do que uma tradução para JavaScript da definição da sequência de Fibonacci. Para formular o algoritmo iterativo foi necessário perceber que a computação poderia ser reformulada como uma iteração com três variáveis de estado.

Exemplo: Contando moedas​

Leva apenas um pouco de criatividade para criar o algoritmo iterativo de Fibonacci. Em contraste, considere o seguinte problema: De quantas maneiras diferentes podemos fazer troco de $1.00 (100 centavos), dado moedas de meio dólar, quartos de dólar, dimes, nickels e pennies (50 centavos, 25 centavos, 10 centavos, 5 centavos e 1 centavo, respectivamente)? Mais geralmente, podemos escrever uma função para calcular o número de maneiras de trocar qualquer quantia de dinheiro?

Este problema tem uma solução simples como uma função recursiva. Suponha que pensemos nos tipos de moedas disponíveis como organizados em alguma ordem. Então a seguinte relação vale:

O número de maneiras de trocar uma quantia a usando n tipos de moedas é igual a

  • o número de maneiras de trocar a quantia a usando todos os tipos de moedas, exceto o primeiro tipo, mais
  • o número de maneiras de trocar a quantia a - d usando todos os n tipos de moedas, onde d é a denominação do primeiro tipo de moeda.

Para ver por que isso é verdade, observe que as maneiras de fazer troco podem ser divididas em dois grupos: aquelas que não usam nenhuma moeda do primeiro tipo, e aquelas que usam. Portanto, o número total de maneiras de fazer troco de alguma quantia é igual ao número de maneiras de fazer troco da quantia sem usar nenhuma moeda do primeiro tipo, mais o número de maneiras de fazer troco assumindo que usamos o primeiro tipo de moeda. Mas este último número é igual ao número de maneiras de fazer troco da quantia que resta após usar uma moeda do primeiro tipo.

Assim, podemos reduzir recursivamente o problema de trocar uma determinada quantia para problemas de trocar quantias menores ou usar menos tipos de moedas. Considere cuidadosamente essa regra de redução e convença-se de que podemos usá-la para descrever um algoritmo se especificarmos os seguintes casos degenerados:

  • Se a é exatamente 0, devemos contar isso como 1 maneira de fazer troco.
  • Se a é menor que 0, devemos contar isso como 0 maneiras de fazer troco.
  • Se n é 0, devemos contar isso como 0 maneiras de fazer troco.

Podemos facilmente traduzir esta descrição em uma função recursiva:

Exemplo de Código
function count_change(amount) {
  return cc(amount, 5);
}

function cc(amount, kinds_of_coins) {
  return amount === 0
         ? 1
         : amount < 0 || kinds_of_coins === 0
         ? 0
         : cc(amount, kinds_of_coins - 1)
           +
           cc(amount - first_denomination(kinds_of_coins),
              kinds_of_coins);
}

function first_denomination(kinds_of_coins) {
  return kinds_of_coins === 1 ? 1
       : kinds_of_coins === 2 ? 5
       : kinds_of_coins === 3 ? 10
       : kinds_of_coins === 4 ? 25
       : kinds_of_coins === 5 ? 50
       : 0;
}
Open on CodeSandboxOpen Sandbox

(A função first_denomination recebe como entrada o número de tipos de moedas disponíveis e retorna a denominação do primeiro tipo. Aqui estamos pensando nas moedas como organizadas em ordem da maior para a menor, mas qualquer ordem funcionaria igualmente bem.) Agora podemos responder nossa pergunta original sobre trocar um dólar:

Exemplo de Código
count_change(100);
Open on CodeSandboxOpen Sandbox
292

A função count_change gera um processo recursivo em árvore com redundâncias semelhantes às da nossa primeira implementação de fib. Por outro lado, não é óbvio como projetar um algoritmo melhor para calcular o resultado, e deixamos este problema como um desafio. A observação de que um processo recursivo em árvore pode ser altamente ineficiente, mas muitas vezes fácil de especificar e entender, levou as pessoas a propor que se poderia obter o melhor dos dois mundos projetando um "compilador inteligente" que pudesse transformar funções recursivas em árvore em funções mais eficientes que calculam o mesmo resultado.

Exercícios​

Exercício 1.11​

Uma função f é definida pelas regras f(n) = n se n < 3 e f(n) = f(n - 1) + 2f(n - 2) + 3f(n - 3) se n ≥ 3. Escreva uma função JavaScript que calcula f por meio de um processo recursivo. Escreva uma função que calcula f por meio de um processo iterativo.

Exercício 1.12​

O seguinte padrão de números é chamado de triângulo de Pascal.

        1
      1   1
    1   2   1
  1   3   3   1
1   4   6   4   1
      ...

Os números na borda do triângulo são todos 1, e cada número dentro do triângulo é a soma dos dois números acima dele. Escreva uma função que calcula elementos do triângulo de Pascal por meio de um processo recursivo.

Exercício 1.13​

Prove que Fib(n) é o inteiro mais próximo de φⁿ/√5, onde φ = (1 + √5)/2. Dica: Use indução e a definição dos números de Fibonacci para provar que Fib(n) = (φⁿ - ψⁿ)/√5, onde ψ = (1 - √5)/2.