Lesson16

Recursão em árvore

Os processos computacionais gerados por funções recursivas podem apresentar diferentes padrões de evolução. Na última aula vimos recursão linear, mas existe um outro padrão bastante comum.

Consideremos novamente os números de Fibonacci, \[\begin{align} fib(n) = & \left\{ \begin{array}{cl} 0 & \text{se } n = 1,\\ 1 & \text{se } n = 2,\\ fib(n-1) + fib(n-2) & \text{se } n > 2 \end{array} \right. \end{align}\]

Podemos definir uma função para determinar o $n$-ésimo número de Fibonacci como se segue,

def fib(n):
    if n == 1:
        return 0
    elif n == 2:
        return 1
    else return fib(n - 1) + fib(n - 2)

Se avaliarmos fib(5), o processo computacional gerado pela função fib apresenta a seguinte evolução:

fib(5)
| fib(4)
| | fib(3)
| | | fib(2)
| | | return 1
| | | fib(1)
| | | return 0
| | return 1
| | fib(2)
| | return 1
| return 2
| fib(3)
| | fib(2)
| | return 1
| | fib(1)
| | return 0
| return 1
return 3

Podemos constatar que este padrão de evolução é bastante diferente da recursão linear. Neste caso, ainda que recursivo, podemos observar várias fases de crescimento, em que são criados vários ambientes relativos à função fib, seguidas de fases de contracção em que todos, ou apenas alguns, ambientes são destruídos. Devido à existência de várias fases de crescimento e de contracção, que podem ser vistos como ramos numa árvore, este padrão de evolução denomina-se por recursão em árvore.

Se observarmos uma segunda vez a evolução anterior podemos constatar que é um processo muito ineficiente, existindo cálculos que são repetidos múltiplas vezes para os mesmos parâmetros e, portanto, com o mesmo resultado. Por outro lado o número de passos não cresce linearmente com o valor de $n$, de facto cresce exponencialmente.

Podemos evitar os cálculos repetidos guardando os valores já calculados, ou seja, guardando estado. Como vimos na última aula, podemos fazê-lo através de parâmetros extra e utilizando recursão de cauda. A observação fundamental é que podemos obter o próximo número de Fibonacci somando os dois anteriores e, por outro lado, temos dois casos base. Neste caso precisamos portanto de três variáveis/parâmetros para guardar o estado, i.e., os dois últimos números calculados até ao momento e o número de vezes que ainda temos de somar para chegar ao resultado pretendido. Portanto,

def fib(n):
    def fib_aux(s, t, n):
        if n == 0:
            return s
        else:
            return fib_aux(t, s+t, n - 1)
    
    return fib_aux(0, 1, n-1)

Neste caso obtemos a seguinte evolução, ou seja, um processo recursivo linear:

fib(5)
fib_aux(0, 1, 3)
| fib_aux(1, 1, 2)
| | fib_aux(1, 2, 1)
| | | fib_aux(2, 3, 0)
| | | return 3
| | return 3
| return 3
return 3
return 3

Exercício: Redefinir esta função utilizando a função tco vista na última aula de forma a evitar a acumulação de ambientes criados e, eventualmente, a exaustão da pilha de execução.

Podemos também obter um processo iterativo definindo a função fib como se segue,

def fib(n):
    s, t = 0, 1
    for i in range(n-1):
        s, t = t, s + t
    return s

Notar a correspondência entre as variáveis utilizadas nesta última definição e as variáveis utilizadas na penúltima definição da função fib.

Exercício: Definir uma função que resolva o problema da Torre de Hanoi.

Considerações sobre eficiência

Os exemplos anteriores permitem-nos verificar que os processos gerados por diferentes funções, mesmo quando as funções calculam um mesmo valor ou efectuam uma mesma operação, podem diferir drasticamente na sua evolução e quanto aos recursos computacionais consumidos.

Os recursos computacionais que consideramos são o tempo e o espaço. O tempo refere-se ao tempo que um programa ou algoritmo demora a executar, ou seja, o número de passos atómicos ou instruções realizados durante a sua execução. A memória diz respeito ao espaço de memória que um programa ou algoritmo utiliza durante a sua execução (nota-se que em geral queremos saber o máximo necessário durante a execução, e não a soma da memória utilizada durante toda a duração do processo computacional).

A minimização dos recursos computacionais consumidos por um programa ou algoritmo é um dos aspectos que nos preocupa quando desenhamos algoritmos e estruturas de dados, e quando escrevemos programas.

A quantificação dos recursos necessários por um algoritmo ou programa é expressa em geral em função dos parâmetros, e faz parte do estudo da complexidade computacional de programas, algoritmos e problemas.

Exercício: Indique uma estimativa da taxa de consumo de recursos computacionais, quer no que diz respeito a espaço quer no que diz respeito a tempo, para as funções definidas acima.