18. Amnésia recursiva

Estivemos trabalhando com recursão e continuaremos apreciando alguns dos seus aspectos. Na realidade estaremos a todo momento trabalhando com tudo que vimos até agora.

A perda parcial ou total da memória, a amnésia, é um mal que assola alguns programas. Ocasionalmente seus efeitos são sentidos. Funções recursivas constituem uma área onde a amnésia tem seus sintomas muito amplificados. Portanto, este parece ser um momento apropriado para abordarmos este tópico.

M.C. Escher, 1939

18.1. Objetivos de aprendizagem

Cada tópico que estudamos, por mais simples que possa parecer, pode ser aprofundado em diversas direções. O nosso progresso de aprendizagem é meio que em zigue-zague. Neste ponto, por assim dizer, o nosso zigue será a amnésia em programação e, em particular, a amnésia em recursão. O nosso zague será o antídoto para amnésia que serão as variáveis e seu papel na memorização. 😧 Junto com esse zigue-zague veremos alguns rudimentos sobre como fazer a análise da eficiência experimental e analítica de algoritmos.

18.2. Introdução

Váriáveis são nomes ou apelidos que damos às coisas, objetos, valores, …, que pretendemos utilizar mais tarde. Algo bem básico, não? Talvez…

Variáveis nos permitem reacessar, rapidamente, objetos que já atravessaram o nosso caminho. Dependendo do número de vezes que necessitamos acessar alguns valores, o uso de nomes, apelidos, rótulos, referências para revisitar valores pode ser a diferença entre realizarmos uma tarefa em um tempo aceitável ou em um tempo que pode ser algo como a idade da Terra!

Confusa?! Confuso?! 😕 Bem vamos por a mão na massa e depois você pode reler estes parágrafos iniciais e refletir se fazem algum sentido. No caso, a nossa mão será um conjunto de variáveis e a nossa massa será o problema de calcular os números de Fibonacci, que tem características intrinsicamente recursivas.

Tenha em mente que os números de Fibonacci são um contexto muito simples utilizado apenas como pretexto para apresentar ideias muito sofisticadas. Neste momento, aplicar ideias absolutamente envolventes a problemas complexos não parece ser algo pedagogicamente promissor 🤔.

18.3. Fibonacci

By Romain - Own work, CC BY-SA 4.0

Os número de Fibonacci formam uma sequência de números em que cada número é a soma dos dois números que o antecedem. A sua definição é, portanto, recursiva. O valor do \(n\)-ésimo número \(\mathtt{F_n}\) depende dos valores de \(\mathtt{F_{n-1}}\) e \(\mathtt{F_{n-2}}\).

Como sabemos, toda recursão tem um caso base e com os número de Fibonacci não é diferente. Sem mais delongas, aqui está a especificação recursiva dos números de Fibonacci, com base e tudo mais:

\[\begin{split}\begin{align*} \mathtt{F_n} &= \begin{cases} 0 & \text{ se $\mathtt{{n} = 0}$},\\ 1 & \text{ se $\mathtt{{n} = 1}$},\\ \mathtt{F_{n-1} + F_{n-2}} & \text{ se $\mathtt{{n\geq 2}}$}. \end{cases} \end{align*}\end{split}\]

Assim, os primeiros valores da sequência são:

\[\begin{split}\begin{array}{c|cccccccccc} \mathtt{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \mathtt{F_n} & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13& 21& 34 \end{array}\end{split}\]

Para escrever uma versão recursiva de uma função fibonacciR() que calcula e retorna o \(n\)-ésimo número de Fibonacci basta traduzir a especificação para Python.

def fibonacciR(n):
    '''(int) -> int
    RECEBE um inteiro não negativo n.
    RETORNA o n-ésimo número de Fibonacci.
    '''
    if n == 0: return 0
    if n == 1: return 1
    return fibonacciR(n-1) + fibonacciR(n-2)

Escrever uma versão iterativa fibonacciI() também é uma tarefa simples.

def fibonacciI(n):
    '''(int) -> int
    RECEBE um inteiro não negativos n.
    RETORNA o n-ésimo número de Fibonacci.
    '''
    if n == 0: return 0
    if n == 1: return 1
    anterior = 0
    atual    = 1
    for i in range(1, n):
        proximo = atual + anterior
        anterior = atual
        atual = proximo
    return atual

Agora vamos ao que interessa! Qual versão é mais eficiente em termos de tempo? Para responder essa pergunta faremos alguns experimentos e usaremos a função time.time() do módulo time do Python para cronometrar o tempo de execução por meio da seguinte função.

def cronometro(f, n):
    '''(callable, int) -> float, valor
    RECEBE uma função f e um argumento n para f().
    RETORNA o tempo gasto e valor retornado pela execução de f(n).
    '''
    # dispare o cronômetro
    inicio = time.time()
    # execute a função
    valor = f(n)
    # pare o cronometro
    fim = time.time()
    # calcule quantos segundos foram gastos.
    elapsed = fim-inicio
    return elapsed, valor

Execute a função main() no Trinket ou baixe o arquivo main.py e fibonacci,.py para o seu computador.

Ao executar a função main() no meu computador obtive os seguinte valores para as funções fibonacciR() e fibonacciI():

        fibonacciR()                  fibonacciI()
  n         f(n)   tempo (s)    n         f(n)   tempo (s)
----------------------------   ---------------------------
 30        832040      0.39     30        832040      0.00
 31       1346269      0.49     31       1346269      0.00
 32       2178309      0.77     32       2178309      0.00
 33       3524578      1.16     33       3524578      0.00
 34       5702887      1.87     34       5702887      0.00
 35       9227465      3.02     35       9227465      0.00
 36      14930352      4.93     36      14930352      0.00
 37      24157817      7.94     37      24157817      0.00
 38      39088169     12.85     38      39088169      0.00
 39      63245986     20.87     39      63245986      0.00
 40     102334155     35.66     40     102334155      0.00

Hmm. 🤔 Será que tem algo errado? Os tempos de fibonacciI() foram praticamente zero!

A propósito, é claro que os tempos não foram zero. Algum tempo essas execuções gastaram. O ponto é que o tempo gasto foi abaixo da nossa medida padrão.

Bem, voltando. Tudo é meio estranho pois fibonacciR() é muito simples e é até mais curta que fibonacciI(). Gastar mais que meio minuto para calcular fibonacciR(40) é muita coisa. Precisamos investigar o que está acontecendo. 🕵🏿‍♀️ Como boas detetives vamos examinar as evidências. Examinaremos os rastros deixados pela execução de fibonacciR() para alguns valores de n. 🕵🏻‍♀️

In [18]: fibonacciR(5)
fibonacciR(5)
    fibonacciR(4)
        fibonacciR(3)
            fibonacciR(2)
                fibonacciR(1)
                fibonacciR(1)=1
                fibonacciR(0)
                fibonacciR(0)=0
            fibonacciR(2)=1
            fibonacciR(1)
            fibonacciR(1)=1
        fibonacciR(3)=2
        fibonacciR(2)
            fibonacciR(1)
            fibonacciR(1)=1
            fibonacciR(0)
            fibonacciR(0)=0
        fibonacciR(2)=1
    fibonacciR(4)=3
    fibonacciR(3)
        fibonacciR(2)
            fibonacciR(1)
            fibonacciR(1)=1
            fibonacciR(0)
            fibonacciR(0)=0
        fibonacciR(2)=1
        fibonacciR(1)
        fibonacciR(1)=1
    fibonacciR(3)=2
fibonacciR(5)=5
Out[18]: 5

Hmm. Aqui tem algo estranho. Para calcular \(F_5\) deveria ser suficiente fazermos umas quatro adições e estamos vendo várias chamadas de fibonacciR(0), fibonacciR(1) e fibonacciR(2), duas chamadas de fibonacciR(3) e uma chamada de fibonacciR(4). É muita coisa para calcular apenas \(F_5\). Vejamos o que ocorre para n = 8. 🕵🏿‍♀️

In [20]: fibonacciR(8)
fibonacciR(8)
    fibonacciR(7)
        fibonacciR(6)
            fibonacciR(5)
                fibonacciR(4)
                    fibonacciR(3)
                        fibonacciR(2)
                            fibonacciR(1)
                            fibonacciR(1)=1
                            fibonacciR(0)
                            fibonacciR(0)=0

[... montes de linhas apagadas ...]

                fibonacciR(1)
                fibonacciR(1)=1
                fibonacciR(0)
                fibonacciR(0)=0
            fibonacciR(2)=1
        fibonacciR(4)=3
    fibonacciR(6)=8
fibonacciR(8)=21
Out[20]: 21

Vixe! Nem cabe na página! O rastro tem mais de 130 linhas! Pelo menos descobrimos o que está ocorrendo. A função fibonacciR() resolve o mesmo subproblema várias vezes. Por exemplo, fibonacci(8) fez 13 chamadas de fibonacci(2), que tem valor 1.

Assim o diagnóstico da lentidão da função fica fácil, fibonacciR() está sofrendo de amnésia! 🤒

Felizmente esse mal tem tratamento. A nossa receita para fibonacciR() é um escalda pés de variáveis com treinamento em memorização.

Mais adiante veremos como tratar fibonacciR() de uma maneira sistemática, usando protocolos muito bem estabelecidos. Esse tratamento para amnésia de funções é utilizado na cura de funções que resolvem problemas muito mais complicados, mas muito mesmo! Antes do tratamento, vamos fazer umas contas para estimar o trabalho feito por fibonacciR() com adições.

18.4. Estimativa do trabalho

Quantas adições faz a chamada fibonacciR(n)? Não deveriam ser muitas, mas parece que são… 😥

Vamos chamar de \(\mathtt{T(n)}\) o número de adições + feitas por fibonacciR(n). É claro que o número de adições cresce a medida que n cresce. É de se esperar que o tempo gasto por fibonacciR(n) seja proporcional a \(\mathtt{T(n)}\) e que cresça com a mesma velocidade. A tabela abaixo mostra \(F_n\) e \(T(n)\), calculados na mão, para alguns valores de \(n\).

\[\begin{split}\begin{array}{c|cccccccccc} \mathtt{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7& 8& 9 \\ \hline \mathtt{F_n} & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13& 21& 34 \\ \hline \mathtt{T(n)} & 0 & 0 & 1 & 2 & 4 & 7 & 12 & 20& 33& 54 \end{array}\end{split}\]

Antes de prosseguir, vamos reescrever fibonacciR() de uma forma que seja mais conveniente para a nossa análise, inclusive numerando algumas linhas.

   def fibonacciR(n)
1      if n == 0: return 0
2      if n == 1: return 1
3      return fibonacciR(n-1) +
4           fibonacciR(n-2)

Examinando o número de adições feitas em cada linha do código temos que

\[\begin{split}\begin{array}{ll} \text{linha} & \text{número de somas}\\ \hline \rule[0mm]{0mm}{6mm}% 1 & = 0 \\ 2 & = 0 \\ 3 & = \mathtt{T(n-1)}\\ 4 & = \mathtt{T(n-2)} + 1\\ \hline \rule[0mm]{0mm}{8mm}% \mathtt{T(n)} & = \mathtt{T(n- 1) + T(n-2) + 1} \end{array}\end{split}\]

Assim, obtemos a seguinte descrição de \(\mathtt{T(n)}\) que se parece muito com a especificação da função de Fibonacci:

\[\begin{split}\begin{align*} \mathtt{T(n)} &= \begin{cases} 0 & \text{ se $\mathtt{{n} = 0}$},\\ 0 & \text{ se $\mathtt{{n} = 1}$},\\ \mathtt{T(n-1) + T(n-2) + 1} & \text{ se $\mathtt{{n\geq 2}}$}. \end{cases} \end{align*}\end{split}\]

Fazendo algumas contas é possível verificar que para \(\mathtt{n \geq 6}\) vale que \(\mathtt{T(n) \geq (3/2)^n}\).

Em português, o número de adições feitas por fibonacciR(n) cresce exponencialmente a medida que n cresce. Portanto, o tempo gasto por fibonacciR(n) para fazer o seu serviço deve também crescer muito rapidamente a medida que n cresce. Para termos uma ideia, essa estimativa diz que fibonacciR(40) faz pelo menos \(\mathtt{T(n) \geq (3/2)^{40}> 11057332}\) adições. Isso é mais do que 11 milhões de adições! 😵‍💫 🤦🏾

Enquanto isso, na bat caverna, fibonacciI(40) faz não mais que 40 adições. 🥇

Mais sobre a estimativa para \(\mathtt{T(n)}\)

Para \(\mathtt{n \geq 6}\) vale que \(\mathtt{T(n) \geq (3/2)^n}\), em que \(\mathtt{T(n)}\) é o número de adições feita por fibonacciR(n).

Vejamos uma demonstração desse fato. A demonstração será por indução no número n. A base da indução são os casos em que \(\mathtt{n = 6}\) e \(\mathtt{n = 7}\) Calculando diretamente obtivemos que \(\mathtt{T(6)=12 > 11.40 > (3/2)^6}\) e que \(\mathtt{T(7)=20 > 18 > (3/2)^7}\). Suponha por hipótese de indução que \(\mathtt{T(k) \geq (3/2)^k}\) para todo \(\mathtt{k}\), \(\mathtt{6 \leq k < n}\) para algum \(\mathtt{n \geq 8}\). Verifique que essa hipótese implica que \(\mathtt{T(n) \geq (3/2)^n}\). De fato

\[\begin{split}\begin{align*} \mathtt{T(n)} & = \mathtt{T(n-1) + T(n-2) + 1}\\ & > \mathtt{(3/2)^{n-1} + (3/2)^{n-2} + 1} \text{ (pela hipótese de indução)}\\ & = \mathtt{(3/2 + 1)\,(3/2)^{n-2} + 1}\\ & > \mathtt{(5/2)\,(3/2)^{n-2}}\\ & > \mathtt{(9/4)\,(3/2)^{n-2}}\\ & = \mathtt{(3/2)^2(3/2)^{n-2}}\\ & = \mathtt{(3/2)^{n}}. \end{align*}\end{split}\]

Portanto, pelo Princípio da Indução, concluímos que \(\mathtt{T(n) \geq (3/2)^n}\) para todo \(\mathtt{n \geq 6}\).

De maneira curta e grossa, isso, como dizem por ai, significa que o consumo de tempo de FibonacciR() é exponencial. 👎🏿

De forma mais precisa …

Na verdade é possível calcular exatamente o número \(\mathtt{T(n)}\) de adições feitas por FibonacciR(n) 😲.

Para \(\mathtt{n = 0, 1, 2,\ldots}\) tem-se que

\[\begin{align*} \mathtt{T(n)} = \frac{\phi^{n+1}- \hat{\phi}^{n+1}}{\sqrt{5}} - 1 \end{align*}\]

em que

\[\phi = \frac{1 + \sqrt{5}}{2} \approx 1.61803 \text{ e } \hat{\phi} = \frac{1 - \sqrt{5}}{2} \approx -0.61803.\]

Esse fato pode ser verificado por indução em \(n\) e usando-se o fato de que \(1 + \phi = \phi^2\) e de que \(1 + \hat{\phi} = \hat{\phi}^2\).

Vejamos alguns valores de \(\mathtt{T(n)}\);

\[\begin{split}\begin{array}{lll} \mathtt{n} & \mathtt{T(n)} & \text{mais de} \\ \hline \rule[0mm]{0mm}{6mm}% 10 & 88 & \\ 20 & 10945 & \\ 30 & 1346268 & \text{1 milhão}\\ 40 & 165580140 & \text{165 milhões} \\ 50 & 20365011073 & \text{ 20 bilhões}\\ 60 & 2504730781960 & \text{2 trilhões} \\[2mm] \hline \end{array}\end{split}\]

Deu para sentir o que significa gastar ou consumir tempo exponencial? 🤦🏿‍♀️ 🤦🏽‍♀️ 🤦🏻‍♀️

18.5. Árvores de recursão

Vamos fazer uma pequena pausa e antes de apresentarmos um tratamento para amnésia, vejamos uma outra maneira de visualizarmos esse comportamento exponencial de fibonacciR() por meio do que é chamado de uma árvore de recursão. Curiosamente, em Ciência da Computação, frequentemente, as raízes das árvores são desenhadas para cima e suas folhas para baixo 😖. As árvores em computação crescem para baixo. 🤔 Lembram árvores genealógicas.

Árvore crescem para baixo

Aqui está a árvore da recursão para determinar \(\mathtt{F_5}\) associada a chamada fibonacciR(5). \(F_5\) é a raiz da árvore. Nas folhas da árvore temos os valores da base da recursão, \(\mathtt{F_1}\) e \(\mathtt{F_0}\) Os dois \(\mathtt{F_4}\) e três \(\mathtt{F_2}\) aparecem no que chamamos de nós internos da árvore, aqueles que não são raiz nem folhas.

Árvore de recursão

A árvore da recursão acima tem 6 nós internos, 8 folhas e, evidentemente, uma raíz.

Como em uma árvore genealógica, dizemos que a raiz \(\mathtt{F_5}\) é mãe de \(\mathtt{F_4}\) e de \(\mathtt{F_3}\). Por sua vez, \(\mathtt{F_4}\) é filha \(\mathtt{F_5}\) e mãe de \(\mathtt{F_3}\) e de \(\mathtt{F_2}\). Veja que há um nó \(F_3\) que é filha de \(\mathtt{F_5}\) e outro que é neta. Bem , como você pode imaginar, temos todas as relações familiares na árvore, mães, filhas, netas, bisnetas, tias, bisavó, … Essa nomenclatura será utilizada mais tarde.

Veja que a árvore da recursão para \(\mathtt{F_{60}}\) terá mais de 1 trilhão de nós internos e folhas. A copa dessa árvore será muito bonita mesmo. 😲

Depois desta pausa, vamos ao tratamento da amnésia.

18.6. Tratamento para amnésia

A ideia é usar uma tabela para mantermos os resultados já calculados por chamadas anteriores da função. Dessa forma assim que a função é chamada novamente com o mesmo argumento, o valor armazenado é prontamente retornado. Essa técnica para deixar programas mais velozes é chamada de memorização ou Memoization. Frequentemente a tabela utilizada pela técnina é batizada com o nome de cache.

O tratamento para curar amnésia consiste em inicialmente construir uma função envoltória para a função recursiva. Nesta envoltória é criada a memória cache que será usada pela função recursiva como rascunho para anotar o que andou fazendo. Assim, quando a função recursiva necessitar se lembrar de algo basta primeiro consultar suas anotações no rascunho. Se a função não encontrar algum registro em suas anotações saberá que deverá fazer algo para completar o serviço que lhe foi pedido.

No caso de fibonacciR(), chamaremos essa envoltória de fibonacciRM() de Fibonacci recursiva com memorização.

def fibonacciRM(n):
    '''(int) -> int
    envoltória para fibonacciRCache().
    '''
    # -1 indica que o valor correspondente a posição não foi calculado
    cache    = [0] + [-1]*n
    return fibonacciRCache(n, cache)

A função recursiva é então substituida por uma versão modificada que utiliza os recursos da memória cache. No caso de fibonacciR(), a função substituta será fibonacciRCache():

def fibonacciRCache(n, cache):
    '''(int) -> int
    RECEBE um inteiro não negativos n.
    RETORNA o n-ésimo número de Fibonacci.
    '''
    # BASE
    # se FinonacciR(n) está no cache, retorne seu valor
    if cache[n] > -1: return cache[n]
    elif n < 2: cache[n] = n
    else:
        # REDUZA: se Finonacci(n) não está no cache, calcule-o recursivamente
        cache[n-1] = fibonacciRCache(n-1, cache)
        # cache[n-2] = fibonacciRCache(n-2, cache) # Supérflua. Por quê?

        # RESOLVA: calcule Fibonacci(n)
        cache[n] = cache[n-1] + cache[n-2]
    return cache[n]

Note a semelhança estrutural de fibonacciRCache() e fibonacciR(). Vejamos agora como a dobradinha fibonacciRM() e fibonacciRCache() se comportam nos testes:

       fibonacciRM()
 n         f(n)   tempo (s)
---------------------------
 30        832040      0.00
 31       1346269      0.00
 32       2178309      0.00
 33       3524578      0.00
 34       5702887      0.00
 35       9227465      0.00
 36      14930352      0.00
 37      24157817      0.00
 38      39088169      0.00
 39      63245986      0.00
 40     102334155      0.00

Muito melhor, não?! Esta nova versão de fibonacciR() está completamente curada da amnésia.

18.7. Hanoi e o fim do mundo

Vimos como amnésia pode causar que uma função simples e elegante gaste uma quantidade de tempo absurda para fazer seu serviço. Vejamos agora uma função que gasta muito, mas muito tempo mesmo para fazer seu serviço, mas a culpa não é dela. Ela tem realmente muito serviço a fazer.

Diz a lenda que \(\ldots\)

No grande templo de Brahma em Benares, na Índia, em uma placa de bronze sob a cúpula que marca o centro do mundo, há 64 discos de ouro puro que os sacerdotes carregam um de cada vez entre três agulhas de diamante de acordo com a lei imutável de Brahma: nenhum disco pode ser colocado em um disco menor. No início do mundo todos os 64 discos formaram a Torre de Brahma em um agulha. Agora, porém, o processo de transferência da torre de uma agulha para outra está no meio do caminho. Quando o último disco for finalmente colocado no seu lugar, mais uma vez formando a Torre de Brahma, mas em uma agulha diferente, então virá o fim do mundo e tudo se transformará em pó.

  • W.W. Rouse Ball & H.S.M. Coxeter, Mathematical Recreations and Essays, 12th edition. Univ. of Toronto Press, 1974. The De Parville account of the origen from La Nature, Paris, 1884, part I, pp. 285-286.

A função hanoi() do capítulo anterior seria de ajuda para os sacerdotes já que apresentam uma sequência de movimentos para resolver o quebra-cabeça.

def hanoi(n, origem, auxiliar, destino):
     '''(int, str, str, str) -> None
     Recebe o numero de discos n, os apelidos origem, auxiliar e destino dos pinos.
     Imprime as messagens com os movimentos para resolver o quebra-cabeça das Torres de Hanoi
         para movimentar n discos do pino origem para o pino destino usando o pino auxiliar.
     '''
     if n == 0: return None
     hanoi(n-1, origem, destino, auxiliar)
     print(f"mova o disco {n} do pino {origem} para o pino {destino}")
     hanoi(n-1, auxiliar, origem, destino)

A chamada hanoi(3,'A','B','C') produz as mensagens:

mova o disco 1 do pino A para o pino C
mova o disco 2 do pino A para o pino B
mova o disco 1 do pino C para o pino B
mova o disco 3 do pino A para o pino C
mova o disco 1 do pino B para o pino A
mova o disco 2 do pino B para o pino C
mova o disco 1 do pino A para o pino C

A animação abaixo mostra uma sequência de movimentos que resolve o quebra-cabeça com 3 discos.

Animação da solução das Torres de Hanoi com 3 discos

A questão que queremos tratar é determinar ou pelo menos estimar quantos movimentos são feitos por hanoi(n,'A','B','C') para solucionar o quebra-cabeça com n discos.

Se \(\mathtt{T(n)}\) é o número de movimentos feitos pela função para resolver o quebra-cabeça com n discos, então desejamos determinar o valor de \(\mathtt{T(n)}\). Para aquecer os motores, aqui estão alguns valores de \(\mathtt{T(n)}\) determinados por uma modificação da função hanoi() que além de imprimir os movimentos retorna o número de movimentos feitos.

\[\begin{split}\begin{array}{c|cccccccccc} \mathtt{n} & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline \mathtt{T(n)} & 0 & 1 & 3 & 7 & 15 & 31 & 63 & 127& 255& 511 \\ \end{array}\end{split}\]

Vemos pela estratégia usada pela função que, para resolver o quebra-cabeça com n discos, devemos:

  • resolver o quebra-cabeça com n-1 discos;
  • fazer o movimento do maior disco para sua posição final; e
  • resolver o quebra-cabeça com n-1 discos;

Desta solução obtemos a seguinte relação recursiva que descreve \(\mathtt{T(n)}\), também chamada de relação de recorrência:

\[\begin{split}\begin{align*} \mathtt{T(n)} = \begin{cases} 0 & \text{se } \mathtt{n = 0},\\ \mathtt{2 \, T(n - 1) + 1} & \text{para } \mathtt{n=1,2,3\ldots} \end{cases} \end{align*}\end{split}\]

Quanto vale \(\mathtt{T(n)}\)? Desenrolando telescopicamente \(\mathtt{T(n)}\) observamos que

\[\begin{split}\begin{align*} \mathtt{T(n)} & = \mathtt{2 \, T(n-1) + 1}\\ & = \mathtt{2 \, ({ 2}\, T(n-2)+{ 1}) + 1}\\ &= \mathtt{2 \, ({ 2}\, ({ 2} \, T(n-3)+{ 1}) + { 1}) + 1}\\ &= \mathtt{2 \, ({ 2}\, ({ 2} \, ({ 2} \, T(n-4)+{ 1}) +{ 1}) + { 1}) + 1}\\ &= \cdots \\ &= \mathtt{2 \, ({ 2}\, ({ 2} \, ({ 2} \, (\cdots ({ 2}\, T(0)+{ 1})) +{ 1}) + { 1}) + 1} \end{align*}\end{split}\]

Logo,

\[\begin{split}\begin{align*} \mathtt{T(n)} & = { \mathtt{2^{n-1}} + \cdots + { 2^3} +{ 2^2} + { 2} + 1} \\ & = \mathtt{2^{n} - 1} \, . \end{align*}\end{split}\]

Aqui aparece novamente uma função exponencial que não é sinal de boa coisa.

Uma observação mais sutil.

A função hanoi() faz o número mínimo de movimentos possível para resolver o quebra-cabeça. Não é possível resolver o quebra-cabeça com n discos fazendo menos do que \(\mathtt{2^n-1}\) movimentos!

Voltemos aos sacerdotes \(\ldots\) Vamos estimar o tempo que eles podem gastar para mover a Torre de Brahma, associando um tempo para realizar cada movimento. O número de movimentos necessários são:

\[T({64}) = 18.446.744.073.709.551.615 \approx {1{,}84 \times 10^{19}}.\]

Suponhamos que os monges consigam mover 1 disco por segundo. Parece bem rápido, certo?! Nessas condições, eles conseguiriam mover a torre (completar os movimentos) em

\[\begin{split}\begin{align*} {1{,}84 \times 10^{19}}\, \mbox{seg} & \approx 3{,}07 \times 10^{17}\, \mbox{min} \\ & \approx 5{,}11 \times 10^{15}\, \mbox{horas} \\ & \approx 2{,}13 \times 10^{14}\, \mbox{dias} \\ & \approx 5{,}83 \times 10^{11}\, \mbox{anos}. \\ & = \mathbf{ 583 \, \mbox{bilhões de anos}}. \end{align*}\end{split}\]

A idade da estimada Terra é de 4,54 bilhões de anos. Ufa, parece que, pelo menos por enquanto, não é pela resolução do quebra-cabeça pelos sacerdotes que devemos nos preocupar 😌.

18.8. Exercícios

  1. Mofifique a função finonacciR() para que retorne, além do número de Fibonacci, o número de adições feitas durante o processo recursivo.

  2. Determine o número exato de adições feitas pela execução de fibonacciI(n).

  3. Escreva uma versão da função fibonacciR() que retorna dois números de Fibonacci consecutivos e com isso faz apenas uma chamada recursiva em cada nível da recursão. Faça experimentos para determinar qual das versões é mais rápida.

  4. Estime o número de adições feitas pela chamada fibonacciRM(n).

  5. Escreva uma versão da função fibonacciRM() que utiliza como cache um array do NumPy (numpy.ndarray) em vez de uma lista do Python (list). Faça experimentos para determinar qual das versões é mais rápida, a que usa uma lista ou a que usa um array. Qual possível vantagem listas tem em comparação a arrays?

  6. Em termos de tempo, qual função você acha que calculará mais rapidamente a seguinte sequência de números de Fibonacci, a função FibonacciI() ou FibonacciRM()? A sequência é: \(\mathtt{F_{1000}, F_{762}, F_{80}, F_{812}, F_{564}, F_{700}, F_{2}, F_{212}, F_{1}}\).

  7. Em termos de espaço, qual função você acha que gastará menos espaço para calcular a seguinte sequência de números de Fibonacci, a função FibonacciI() ou FibonacciRM()? A sequência é \(\mathtt{F_{1000}, F_{762}, F_{80}, F_{812}, F_{564}, F_{700}, F_{2}, F_{212}, F_{1}}\).

  8. Escreva uma função que recebe um número não negativo n e retorna o número de nós internos da árvore da recursão para o cálculo de \(\mathtt{F_n}\) associada a chamada FibonacciR(n).

  9. Escreva uma função que recebe um número não negativo n e retorna o número de folhas da árvore da recursão para o cálculo de \(\mathtt{F_n}\) associada a chamada FibonacciR(n).

  10. Dê argumentos que comprovem que \(\mathtt{2^n-1}\) é o menor números de movimentos possível para resolver o quebra-cabeça das Torres de Hanoi com n discos.

  11. Escreva uma função recursiva binomialR() que recebe dois números inteiros não-negativos n e k e retorna \(\mathtt{\binom{n}{k}}\). binomialR() deve ser uma tradução para Python da seguinte regra de Pascal :

    \[\begin{split}\binom{\mathtt{n}}{\mathtt{k}} = \begin{cases} \mathtt{0} & \mbox{quando $\mathtt{n = 0}$ e $\mathtt{k > 0}$}, \\ \mathtt{1} & \mbox{quando $\mathtt{n} \geq 0$ e $\mathtt{k = 0}$}, \\ \binom{\mathtt{ n}-1}{\mathtt{ k}} + \binom{\mathtt{n-1}}{\mathtt{k-1}}& \mbox{quando $\mathtt{ n}, \mathtt{{ k}>0}$}.\\ \end{cases}\end{split}\]

  12. Escreva uma função iterativa binomialI() que recebe dois dois números inteiros não-negativos n e k e retorna uma matriz de dimensão \(\mathtt{(n+1) \times (k+1)}\) em que cada posição [i][j] tem o velor de \(\mathtt{\binom{i}{j}}\) para \(\mathtt{i=0,1,\ldots,n}\) e \(\mathtt{j=0,1,\ldots,k}\).

    Dica: Para fazer o seu trabalho binomialI() pode inicialmente preencher a linha 0 e coluna 0 da matriz com valores sabidos e em seguida percorrer linha a linha a matriz aplicando a regra de Pascal:

    \[\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}.\]

  13. Escreva o par de funções binomialRM() e binomialRCache() que formam a versão com memória da função binomialR(). A função binomialRM() recebe dois números inteiros não-negativos n e k e retorna uma matriz cache de dimensão \(\mathtt{(n+1) \times (k+1)}\) em que cada posição [i][j] tem o valor de \(\mathtt{\binom{i}{j}}\) para \(\mathtt{i=0,1,\ldots,n}\) e \(\mathtt{j=0,1,\ldots,k}\). A função binomialRCache() deve ser recursiva e, além dos inteiros n e k, recebe uma matriz cache de de dimensão \(\mathtt{(n+1) \times (k+1)}\) e retorna \(\mathtt{\binom{n}{k}}\), preenchendo com \(\mathtt{\binom{i}{j}}\) toda posição [i][j] de cache necessária durante os cálculos de \(\mathtt{\binom{n}{k}}\).

  14. Reescreva as funções binomialI(), binomialRM() e binomialRCache() para que utilizem ndarray s do NumPy em vez de matrizes representadas como lista de listas, list[list]. Quais são as possíveis vantagens dessas novas versões? Quais são as possíveis desvantagens?

  15. Escreva uma função recursiva binomialRC() que recebe dois números inteiros não-negativos n e k e retorna \(\mathtt{\binom{n}{k}}\). A função binomialRC() deve ser baseada na seguinte igualdade:

    \[\binom{n}{k} = \frac{n!}{(n-k)! k!} = \frac{(n-1)!}{(n-k)!(k-1)!} \times \frac{n}{k} = \binom{n-1}{k-1} \times \frac{n}{k}\]

    A estrutura da função recursiva binomialRC(), como a da função fatorialR() e de outras que vimos, é chamada de recursão de calda (tail recursion).

  16. Faça uma análise experimental das funções binomiaR(), binomiaRC(), binomialI() e binomialRM() para estimar as suas limitações em termos de tempo gasto, espaço de memória utilizado e recursos com recursão que são necessários. Determine as possíveis vantagens e desvantagens da utilização de cada uma dessas funções.

18.9. Para saber mais