.. -*- coding: utf-8 -*- 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. .. Funções recursivas são um ambiente em descuitos acabam custando bem caro, seja em questão de tempo ou espaço gasto pelas nossas soluções.. 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. .. Em funções recursivas também são amplificados problemas de visão. A visão a que estamos nos referindos são as *vistas* que são um conceito que implementamos na nossa classe ``Array2D`` e que já vem embutidas em ``ndarray``'s do NumPy. Olharemos |:eye:| mais de perto para a questão *vistas* :math:`\times` *clone*. .. Na poliopia o doente observa múltiplas imagens fantasmas em vez de apenas uma, ou seja, é um sintoma em que um único objeto é percecionado como várias imagens. .. e não é algo Da mesma forma que com seres vimos, dependendo do ponto de vista, não é uma característica desejável. Como de seres vimos não entemos nada, voltemos aos programas. .. image:: ./imgs/escher_tesselation.* :width: 597 :height: 600 :scale: 60 :alt: M.C. Escher, 1939 :align: center :target: https://www.wikiart.org/en/m-c-escher/development-ii 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. |:anguished:| Junto com esse zigue-zague veremos alguns rudimentos sobre como fazer a análise da eficiência experimental e analítica de algoritmos. .. Cada tópicos tem várias facetas e pode ser explorado e visto por novos ângulos. 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?! |:confused:| 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 |:thinking:|. Fibonacci --------- .. image:: ./imgs/Fibonacci_Spiral.* :width: 740 :height: 200 :scale: 100 :alt: By Romain - Own work, CC BY-SA 4.0 :align: center :target: https://commons.wikimedia.org/w/index.php?curid=114415511 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 :math:`n`-ésimo número :math:`\mathtt{F_n}` depende dos valores de :math:`\mathtt{F_{n-1}}` e :math:`\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: .. math:: \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*} Assim, os primeiros valores da sequência são: .. math:: \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} Para escrever uma versão recursiva de uma função ``fibonacciR()`` que calcula e retorna o :math:`n`-ésimo número de Fibonacci basta traduzir a especificação para Python. .. code:: 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. .. code:: python 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. .. code:: python 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. .. raw:: html 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. |:thinking_face:| 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. |:woman_detective_dark_skin_tone:| Como boas detetives vamos examinar as evidências. Examinaremos os rastros deixados pela execução de ``fibonacciR()`` para alguns valores de ``n``. |:woman_detective_tone1:| :: 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 :math:`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 :math:`F_5`. Vejamos o que ocorre para `n = 8`. |:woman_detective_tone5:| :: 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! |:thermometer_face:| 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. Estimativa do trabalho ---------------------- Quantas adições faz a chamada ``fibonacciR(n)``? Não deveriam ser muitas, mas parece que são... |:disappointed_relieved:| Vamos chamar de :math:`\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 :math:`\mathtt{T(n)}` e que cresça com a mesma velocidade. A tabela abaixo mostra :math:`F_n` e :math:`T(n)`, calculados na mão, para alguns valores de :math:`n`. .. math:: \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} Antes de prosseguir, vamos reescrever ``fibonacciR()`` de uma forma que seja mais conveniente para a nossa análise, inclusive numerando algumas linhas. .. code:: python 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 .. math:: \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} Assim, obtemos a seguinte descrição de :math:`\mathtt{T(n)}` que se parece muito com a especificação da função de Fibonacci: .. math:: \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*} Fazendo algumas contas é possível verificar que para :math:`\mathtt{n \geq 6}` vale que :math:`\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 :math:`\mathtt{T(n) \geq (3/2)^{40}> 11057332}` adições. Isso é mais do que 11 milhões de adições! |:face_with_spiral_eyes:| |:facepalm_tone4:| Enquanto isso, na *bat caverna*, ``fibonacciI(40)`` faz não mais que 40 adições. |:1st_place_medal:| .. admonition:: Mais sobre a estimativa para :math:`\mathtt{T(n)}` Para :math:`\mathtt{n \geq 6}` vale que :math:`\mathtt{T(n) \geq (3/2)^n}`, em que :math:`\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 :math:`\mathtt{n = 6}` e :math:`\mathtt{n = 7}` Calculando diretamente obtivemos que :math:`\mathtt{T(6)=12 > 11.40 > (3/2)^6}` e que :math:`\mathtt{T(7)=20 > 18 > (3/2)^7}`. Suponha por hipótese de indução que :math:`\mathtt{T(k) \geq (3/2)^k}` para todo :math:`\mathtt{k}`, :math:`\mathtt{6 \leq k < n}` para algum :math:`\mathtt{n \geq 8}`. Verifique que essa hipótese implica que :math:`\mathtt{T(n) \geq (3/2)^n}`. De fato .. math:: \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*} Portanto, pelo Princípio da Indução, concluímos que :math:`\mathtt{T(n) \geq (3/2)^n}` para todo :math:`\mathtt{n \geq 6}`. De maneira curta e grossa, isso, como dizem por ai, significa que o **consumo de tempo** de ``FibonacciR()`` é **exponencial**. |:thumbdown_tone5:| .. admonition:: De forma mais precisa ... Na verdade é possível calcular *exatamente* o número :math:`\mathtt{T(n)}` de adições feitas por ``FibonacciR(n)`` |:astonished:|. Para :math:`\mathtt{n = 0, 1, 2,\ldots}` tem-se que .. math:: \begin{align*} \mathtt{T(n)} = \frac{\phi^{n+1}- \hat{\phi}^{n+1}}{\sqrt{5}} - 1 \end{align*} em que .. math:: \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 :math:`n` e usando-se o fato de que :math:`1 + \phi = \phi^2` e de que :math:`1 + \hat{\phi} = \hat{\phi}^2`. Vejamos alguns valores de :math:`\mathtt{T(n)}`; .. math:: \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} Deu para sentir o que significa gastar ou consumir tempo exponencial? |:woman_facepalming_tone5:| |:woman_facepalming_tone3:| |:woman_facepalming_tone1:| .. o número exato de adições feitas pela chamada ``Fibonacci(10)`` é :math:`T(10) = 88`. O número exato de adições feitas pela chamada ``Fibonacci(20)`` é :math:`T(20) = 10945`. O número exato de adições feitas pela chamada ``Fibonacci(30)`` é :math:`T(30) = 1346268`, mais de 1 milhão |:confounded:|. O número de adições feitas pela chamada ``Fibonacci(40)`` é :math:`T(40) = 165580140`, mais de 165 milhões |:woman_facepalming_tone5:|. O número de adições feitas por ``Fibonacci(50)`` é :math:`T(50) = 20365011073`, mais de 20 bilhões |:woman_facepalming_tone5:| |:woman_facepalming_tone3:|. O número de adições feitas por ``Fibonacci(60)`` é :math:`T(60) = 2504730781960`, mais de 2 trilhões |:woman_facepalming_tone5:| |:woman_facepalming_tone3:| |:woman_facepalming_tone1:|. Á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 |:confounded:|. As árvores em computação crescem para baixo. |:thinking:| Lembram árvores genealógicas. .. .. image:: ./imgs/automatic_bare_tree-inverted.svg.hi.* :width: 480 :height: 597 :scale: 50 :alt: Árvore crescem para baixo :align: center :target: https://www.ime.usp.br/~pf/algoritmos/aulas/bint.html Aqui está a árvore da recursão para determinar :math:`\mathtt{F_5}` associada a chamada ``fibonacciR(5)``. :math:`F_5` é a **raiz** da árvore. Nas **folhas da árvore** temos os valores da base da recursão, :math:`\mathtt{F_1}` e :math:`\mathtt{F_0}` Os dois :math:`\mathtt{F_4}` e três :math:`\mathtt{F_2}` aparecem no que chamamos de **nós internos** da árvore, aqueles que não são raiz nem folhas. .. image:: ./imgs/arvore_recursao_fibonacci.* :width: 901 :height: 521 :scale: 50 :alt: Árvore de recursão :align: center 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 :math:`\mathtt{F_5}` é **mãe** de :math:`\mathtt{F_4}` e de :math:`\mathtt{F_3}`. Por sua vez, :math:`\mathtt{F_4}` é **filha** :math:`\mathtt{F_5}` e mãe de :math:`\mathtt{F_3}` e de :math:`\mathtt{F_2}`. Veja que há um nó :math:`F_3` que é filha de :math:`\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 :math:`\mathtt{F_{60}}` terá mais de 1 trilhão de nós internos e folhas. A copa dessa árvore será muito bonita mesmo. |:astonished:| Depois desta pausa, vamos ao tratamento da amnésia. 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*. .. code:: python 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()``: .. code:: python 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. 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 :math:`\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. .. code:: python 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. .. image:: ./imgs/animacao_hanoi3.* :width: 796 :height: 248 :scale: 60 :alt: Animação da solução das Torres de Hanoi com 3 discos :align: center 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 :math:`\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 :math:`\mathtt{T(n)}`. Para aquecer os motores, aqui estão alguns valores de :math:`\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. .. math:: \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} 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 :math:`\mathtt{T(n)}`, também chamada de **relação de recorrência**: .. math:: \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*} Quanto vale :math:`\mathtt{T(n)}`? *Desenrolando telescopicamente* :math:`\mathtt{T(n)}` observamos que .. math:: \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*} Logo, .. math:: \begin{align*} \mathtt{T(n)} & = { \mathtt{2^{n-1}} + \cdots + { 2^3} +{ 2^2} + { 2} + 1} \\ & = \mathtt{2^{n} - 1} \, . \end{align*} Aqui aparece novamente uma função exponencial que não é sinal de boa coisa. .. admonition:: 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 :math:`\mathtt{2^n-1}` movimentos! Voltemos aos sacerdotes :math:`\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: .. math:: 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 .. math:: \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*} 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 |:relieved:|. Exercícios ---------- #. 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. #. Determine o número exato de adições feitas pela execução de ``fibonacciI(n)``. #. 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. #. Estime o número de adições feitas pela chamada ``fibonacciRM(n)``. #. 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? #. 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 é: :math:`\mathtt{F_{1000}, F_{762}, F_{80}, F_{812}, F_{564}, F_{700}, F_{2}, F_{212}, F_{1}}`. #. 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 é :math:`\mathtt{F_{1000}, F_{762}, F_{80}, F_{812}, F_{564}, F_{700}, F_{2}, F_{212}, F_{1}}`. #. 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 :math:`\mathtt{F_n}` associada a chamada ``FibonacciR(n)``. #. 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 :math:`\mathtt{F_n}` associada a chamada ``FibonacciR(n)``. #. Dê argumentos que comprovem que :math:`\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. #. Escreva uma função **recursiva** ``binomialR()`` que **recebe** dois números inteiros não-negativos ``n`` e ``k`` e **retorna** :math:`\mathtt{\binom{n}{k}}`. ``binomialR()`` deve ser uma tradução para Python da seguinte `regra de Pascal `_ : .. math:: \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} #. 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 :math:`\mathtt{(n+1) \times (k+1)}` em que cada posição ``[i][j]`` tem o velor de :math:`\mathtt{\binom{i}{j}}` para :math:`\mathtt{i=0,1,\ldots,n}` e :math:`\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: .. math:: \binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}. #. 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 :math:`\mathtt{(n+1) \times (k+1)}` em que cada posição ``[i][j]`` tem o valor de :math:`\mathtt{\binom{i}{j}}` para :math:`\mathtt{i=0,1,\ldots,n}` e :math:`\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 :math:`\mathtt{(n+1) \times (k+1)}` e **retorna** :math:`\mathtt{\binom{n}{k}}`, **preenchendo** com :math:`\mathtt{\binom{i}{j}}` toda posição ``[i][j]`` de ``cache`` necessária durante os cálculos de :math:`\mathtt{\binom{n}{k}}`. #. 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? #. Escreva uma função **recursiva** ``binomialRC()`` que **recebe** dois números inteiros não-negativos ``n`` e ``k`` e **retorna** :math:`\mathtt{\binom{n}{k}}`. A função ``binomialRC()`` deve ser baseada na seguinte igualdade: .. math:: \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 `_). #. 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. Para saber mais --------------- * `Recursão e algoritmos recursivos `_ de `Projeto de Algoritmos `_ de Paulo Feofiloff. * `Recursão `_ de `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ de Brad Miller e David Ranum. * `Recursão `_ de `Como Pensar Como um Cientista da Computação `_ de Brad Miller e David Ranum. * `Recursion `_ de `Introduction to Programming in Python `_. de Robert Sedgewick, Kevin Wayne e Robert Dondero.