.. -*- coding: utf-8 -*- .. |Python| replace:: ``Python`` .. |IPython| replace:: ``IPython`` .. |PythonAnywhere| replace:: `PythonAnywhere `__ .. |RST| replace:: `reST `__ .. |Sphinx| replace:: `Sphinx `__ .. |HTML| replace:: ``HTML`` .. |Trinket| replace:: `Trinket `__ .. |Colab| replace:: `Google Colab `__ .. |Replit| replace:: `Replit `__ .. |Runestone| replace:: `Runestone `__ .. |cscircles| replace:: ``cscircles`` .. |fazsentido| replace:: Faz sentido? ``¯\_(ツ)_/¯`` .. |SURPRESO| replace:: ``(☉_☉)`` .. |HEIN| replace:: ``¯\_(ツ)_/¯`` .. |HELP| replace:: ``(҂◡_◡)`` .. |VALEU| replace:: ``\(•◡•)/`` .. |CONFUSO| replace:: ``ఠ_ఠ`` .. |LOUCO| replace:: ``(⊙_◎)`` .. |TRISTE| replace:: ``(ಥ﹏ಥ)`` .. |ENTER| replace:: ``ENTER`` .. |Return| replace:: ``Return`` .. |Forward| replace:: ``Forward >`` .. |Last| replace:: ``Last >>`` .. |First| replace:: ``<< First`` .. |Back| replace:: ``< Back`` .. |Run| replace:: ``Run`` Histórias dentro de histórias ============================= Quando usamos algo ou alguma coisa ou objeto, bagaça... de uma mesma forma, realizando tarefas idênticas e diárias costumamos colocar essas coisas ou objetos sobre um mesmo teto um mesmo arcabouço e dar o nome de ``abstração de dados`` a esse processo. Em linguagens orientadas a objetos a materialização dessa abstração é através das classes. |:open_mouth:| Praticamos o processo de materialização quando as classe ``Fraction``, ``Complexo``, ``Pilha``, ``Array1D``, ``Array2D`` foram implementadas e aplicadas na solução de problemas cotidianos em computação como, por exemplo, o cálculo do valor de uma expressão. Vimos como as ideias usadas na implementação da nossa ``Array2D`` aparecem em `NumPy `_ para realizar eficientemente operações com matrizes. |:nerd:| Organizar dados, informações, para eficientemente resolver algum problema marca de certa forma uma transição da abstração de dados para o *reino dos algoritmos* |:crown:|. Com *roteiros dentre de roteiros*, *histórias dentro de historias*, *pinturas dentro pinturas*, *bonecas dentro de bonecas*, *filmes dentro de filmes*, *sonhos dentro de sonhos* ... chegamos a essa coisa chamada de **recursão** e entramos com os dois pés nos domínios das ideias e dos métodos para resolvermos problemas computacionais. |:open_mouth:| .. de maneira mais efetiva que conseguimos. Maneira efetiva significa que procuramos encontrar uma resposta para o problema de maneira mais econômica que conseguimos, sem sermos esbanjadores em termos de tempo que gastamos ou espaço que utilizamos. .. image:: ./imgs/xkdc_350.* :width: 740 :height: 200 :scale: 100 :alt: Alternative text :align: center :target: http://xkcdsw.com/1105 As imagens neste texto que foram copiadas da internet possuem um link para a página original. A licença de todas as imagens é alguma das versões de `creative commons `__. Destino ------- Visitaremos vários assuntos e técnicas relacionadas a recursão. Cada problema e função nos apresentará uma nova faceta de algoritmos em geral e de recursão em particular. Aqui vai o roteiro deste ponto no nosso passeio por recursão: |:face_with_raised_eyebrow:| * As *Torres de Hanoi* nos mostra como com simplicidade, com uma certa ingenuidade |:girl_tone2:| |:child_tone3:| e com muita engenhosidade |:full_moon_with_face:| o raciocínio recursivo trabalhando na solução de um problema; * Com *fatorial*, de certa forma, damos um passo atrás, e procuramos compreender os meandros do mecanismo recursivo através de um exemplo simples. Neste momento o mais importante é *compreender esses tais meandros do mecanismo recursivo*. * Os rastros e diagramas de execução tem a missão de tornar transparente a mecânica da recursão. * O *máximo divisor comum* é um problema que evidencia que o pensamento recursivo já estava por ai há muito tempo. O algoritmo do Euclides de 2300 anos nos mostra isso. .. * *Torres de Hanoi* ``hanoi()``: um pouco de análise de algoritmos, relações de recorrência, número exponencial de movimentos; * *Números de Fibonacci* mostram o uso inapropriado de recursão em que resolvemos um mesmo subproblema várias, várias, várias vezes; valores calculados deveriam ser guardados/memorizados; * ``fibonacciRM()``: mostra a técnica de memorização; * ``maximoR()``: exercita o raciocínio recursivo; * ``maximoRF()``: evidência a diferença entre fatiamento de listas, que são *clones*, e de arrays, que são *vistas*, *apelidos* para uma mesma coisa * *Saída de um labirinto*: recursão que como o *problema das distancias* percorre uma rede; Esse problema ilustra a utilidade de recursão na resolução de problemas mais envolventes. * *Curvas de Hilbert*: são um exemplo da chamada recursão indireta Introdução ---------- .. index:: recursão Algumas vezes o método de resolução de um problema nos conduz a procurar resolver o **mesmo problema** em um contexto mais simples, mais tratável. Nestes casos a resolução do problema original pode ser obtida por meio da combinação das soluções desses subproblemas mais simples. |:thinking:| Recursão é uma ideia que vai muito além de programação. Ela existia antes dos computadores serem criados e está intimamente ligada a uma coisa chamada de `indução matemática `_. Em linguagens de programação, a recursão é materializada através de uma chamada de função para si mesma ou chamada indiretamente por meio de outras funções |:confused:|. Para entender essa ideia confusa resolveremos vários problemas de forma recursiva. Com uma certa prática e os exercícios |:bicyclist:|, a ideia passará ser *mais ou menos* natural e menos mágica |:relieved:|. .. _my_Hanoi: Hanoi ----- .. image:: ./imgs/Tower_of_Hanoi.* :width: 677 :height: 298 :scale: 60 :alt: A model set of the Tower of Hanoi (with 8 disks) :align: center :target: https://commons.wikimedia.org/wiki/File:Tower_of_Hanoi.jpeg .. index:: Torres de Hanoi O quebra-cabeça das Torres de Hanoi será a nossa porta de entrada para os domínios do *raciocínio recursivo* para resolução de problemas. Apesar da solução inerentemente recursiva do quebra-cabeça ser muito conhecida, ela não deixa de ser fascinante |:astonished:|. No quebra-cabeça das **Torres de Hanoi** temos três pinos e um certo número de discos de diferentes diâmetros. A imagem logo acima mostra o quebra-cabeça feito de madeira e com oito discos. Inicialmente todos os discos são colocados em um mesmo pino. Os discos de diâmetros menores são colocados sobre os de diâmetros maiores, como ilustra a figura .. image:: ./imgs/hanoi_config_inicial.* :width: 1438 :height: 331 :scale: 50 :alt: Configuração inicial do quebra-cabeça :align: center O objetivo do quebra-cabeça é *encontrar um sequência de movimentos* para transferir os discos do pino em que estão na configuração inicial para um dos outros pinos, na mesma ordem em que apareciam originalmente. A correspondente configuração final esta ilustrada abaixo. .. image:: ./imgs/hanoi_config_fim.* :width: 1438 :height: 333 :scale: 50 :alt: Configuração final do quebra-cabeça :align: center Da mesma forma que nas ilustrações anteriores, batizaremos de *A* o **pino origem** que está mais à esquerda e em que inicialmente estão os discos. Apelidaremos o **pino destino**, o que está mais à direita, de *C*. Finalmente, chamaremos de *B* o **pino auxiliar** que se encontra entre os pinos *A* e *C*. Cada movimento da sequência deve respeitar as seguintes regras. * podemos mover apenas um disco por vez; * o disco a ser movimentado não deve possuir nenhum disco sobre ele, deve estar livre no topo de um pino; e * jamais um disco de diâmetro maior pode ser colocado sobre um de diâmetro menor. A animação a 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 Bem... uma ideia em que o todo o espirito de recursão pula na nossa frente é baseada em uma observação bem, bem, bem simples e evidente. Podemos não saber a sequência de movimentos que leva a solução do quebra-cabeça, mas sabemos, temos certeza a respeito de um movimento que faz parte de toda solução, qualquer mesmo! |:face_with_raised_eyebrow:| Só há um movimento para o disco de maior diâmetro, ele só pode ser movido do pino origem para o pino destino!. Esse movimento está ilustrado abaixo com 3 discos. .. image:: ./imgs/hanoi_config_meio.* :width: 1438 :height: 337 :scale: 50 :alt: Configuração no meio da solução :align: center .. image:: ./imgs/hanoi_config_movimento.* :width: 1441 :height: 335 :scale: 50 :alt: Movimento obrigatório de qualquer solução :align: center Essa observação, evidente e, talvez aparentemente inocente, sugere uma estratégia para encontrar uma sequência de movimentos para resolver o quebra-cabeça. Antes de partirmos para a solução, vamos dar nomes aos bois. Se o quebra-cabeça têm `n` discos, indicaremos os discos pelos inteiros `1, 2, ..., n` em que `1` é o disco de menor diâmetroe, `2` é o disco de diâmetro imediatamente maior que o de `1`, `3` é o disco de diâmetro imediatamente maior que o de `2`,..., até o disco `n` que é o de maor diâmetro. A observação sobre a existência de apenas um movimento possível para o disco `n` sugere que, para resolver o quebra-cabeça, devemos: * mover os discos `1`, `2`, ..., `n-1`, que estão sobre `n`, do pino `A` para o pino `B`, usando o pino `C` como auxiliar; em seguida, * devemos mover o disco `n` para o pino `C`, a sua posição na eternidade, na base do pino destino; e finalmente, * mover os discos `1`, `2`, ..., `n-1` do pino `B` para o pino `C` usando o pino `A` como auxiliar. Se abreviarmos por `Hanoi(n, A, B, C)` o quebra-cabeça das Torres de Hanoi com `n` discos em que `A` é o pino origem, `B` é o pino auxiliar e `C` é o pino destino, então, escrevendo de uma forma mais compacta o que está acima, temos que para resolvermos devemos * resolver `Hanoi(n-1, A, C, B)`; * mover `n` de `A` para `C`; e * resolver `Hanoi(n-1, B, A, C)` Essa estratégia sugere que para resolvermos o quebra-cabeça da Torre de Hanoi devemos resolver duas vezes o quebra-cabeça da Torre de Hanoi! |:dizzy_face:|. Parece que a *cobra mordeu o rabo*. |:snake:| As coisas não são bem assim ... Veja bem ... Essa estratégia sugere que: para resolver o quebra-cabeça das Torres de Hanoi com, digamos, **10 discos**, basta resolvermos, duas vezes, o problema das Torres de Hanoi com **9 discos**, trocando convenientemente os papeis de pinos origem, auxiliar e destino. O quebra-cabeça continua sendo o mesmo, mas foi simplicado, certo?! Fomos de 10 discos para 9, certo?! |:thinking:| Por sua vez, para resolver o quebra-cabeça das Torres de Hanoi com 9 discos, basta resolvermos, duas vezes, o problema das Torres de Hanoi com 8 discos. Simplificamos mais ainda, certo?! |:thinking:| Isso indica que para resolvermos o quebra-cabeça das Torres de Hanoi com 10 discos basta resolvermos com 8 discos. Continuando nessa linha de raciocínio chegaremos em um ponto em que concluiremos que (pasmem! |:hushed:|) para resolvermos a Torre de Hanoi com 10 discos basta resolvermos o quebra-cabeça (pasmem! pasmem!) com zero discos. |:face_with_spiral_eyes:| Sim! Zero discos! |:dizzy_face:| Para relaxarmos um pouco e darmos um tempo para todas e todos se recomporem, assistam a seguir a animação com a resolução do quebra-cabeça com 7 discos. .. image:: ./imgs/animacao_hanoi7.* :width: 796 :height: 248 :scale: 60 :alt: Animação da solução das Torres de Hanoi com 3 discos :align: center Estão de volta? Podemos continuar. Vamos continuar. Como costumam dizer: Para entender recursão é preciso entender recursão! Honestamente, há um erro bem sério com a essa afirmação. Da mesma forma que há um erro bem sério com a tirinha no início desta página e com a animação no final. Bem, isso pode ficar para mais tarde como exercício. .. index:: ``hanoi()`` O código que reproduz a estratégia descrita é bem simples. A função ``hanoi()`` exibe uma sequência de mensagens indicando os movimentos que devem ser feitos para resolvermos o quebra-cabeça. .. code:: python def hanoi(n, origem, auxiliar, destino): '''(int, str, str, str) -> None RECEBE o numero n de discos, 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')`` da função acima 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 Ja a chamada ``hanoi(4,'A','B','C')`` produz: :: mova o disco 1 do pino A para o pino B mova o disco 2 do pino A para o pino C mova o disco 1 do pino B para o pino C mova o disco 3 do pino A para o pino B mova o disco 1 do pino C para o pino A mova o disco 2 do pino C para o pino B mova o disco 1 do pino A para o pino B mova o disco 4 do pino A para o pino C mova o disco 1 do pino B para o pino C mova o disco 2 do pino B para o pino A mova o disco 1 do pino C para o pino A mova o disco 3 do pino B para o pino C mova o disco 1 do pino A para o pino B mova o disco 2 do pino A para o pino C mova o disco 1 do pino B para o pino C E a chamada ``hanoi(7,'A','B','C')`` exibe: :: mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 4 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 3 do pino C para o pino B mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 6 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 3 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 4 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 3 do pino B para o pino A mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 7 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 3 do pino C para o pino B mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 4 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 3 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 6 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 3 do pino B para o pino A mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 4 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 3 do pino C para o pino B mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 3 do pino A para o pino C mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 4 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 1 do pino C para o pino B mova o disco 3 do pino B para o pino A mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 5 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 4 do pino A para o pino B mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 3 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 1 do pino A para o pino C mova o disco 5 do pino C para o pino B mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 3 do pino B para o pino A mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 3 do pino C para o pino B mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 5 do pino B para o pino A mova o disco 1 do pino A para o pino C mova o disco 1 do pino B para o pino A mova o disco 3 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 4 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 1 do pino B para o pino A mova o disco 5 do pino A para o pino C mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 3 do pino C para o pino B mova o disco 1 do pino B para o pino A mova o disco 1 do pino C para o pino B mova o disco 4 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 2 do pino B para o pino C mova o disco 3 do pino A para o pino C mova o disco 1 do pino C para o pino B mova o disco 2 do pino A para o pino B mova o disco 1 do pino A para o pino C mova o disco 1 do pino B para o pino A mova o disco 2 do pino C para o pino A mova o disco 1 do pino C para o pino B mova o disco 3 do pino B para o pino A Explorar a visualização da função é útil. Note que cada chamada da função cria uma cópia dela em que os parâmetros aparecem. É bom ter em mente que parâmetros são variáveis criadas durante a chamada e que são **apelidos** para os valores passados como argumentos. Bem, sem mais delongas, o visualizador com a palavra. .. raw:: html Você também pode assistir o visualizador trabalhando diretamente na página do `cscircles `__. As Torres de Hanoi são um exemplo bem conhecido de quebra-cabeça ou problema que admite uma solução recursiva simples |:tired_face:|, apesar de poder parecer misteriosa |:face_with_raised_eyebrow:|. Como costuma dizer o `Prof. Siang Wun Song `__ do DCC-IME-USP *Para escrever uma função recursiva é preciso ter fé!*. Como quase qualquer outro problema, as Torres de Hanoi ainda têm muito a nos ensinar. Voltaremos a falar sobre este quebra-cabeça mais adiante. A propósito, qualquer função recursiva admite uma versão iterativa, sem recursão, sem chamadas a si mesma. |:face_with_raised_eyebrow:| Entretanto, pelo exemplo que acabamos de ver do emprego de uma ideia fundamentalmente recursiva para resolver o quebra-cabeça das Torres de Hanoi que, no final das contas, não importa como o código foi escrito, a recursão está presente nas entranhas da solução, impregnando todas as suas células, todos os seu *bits*. |:thinking:| .. _my_Anatomia: Anatomia -------- |:hand:| Antes de continuarmos, pausa para reflexão... .. index:: anatomia recursiva Aqui vão algumas observações sobre um certo padrão típico de funções ou algoritmos recursivos. Procuraremos enfatizar e identificar as partes desse padrão nas soluções recursivas que fizermos. .. index:: instância Uma seleção específica de valores fornecidos como argumentos de uma função, subrotina, problema ... é chamado de uma **instância** da função, subrotina ou problema. No caso da função ``hanoi()``, que acabamos de escrever, a instância é o número de discos do quebra-cabeça junto com o nome dos pinos origem, auxiliar e destino. No caso, o argumento mais relevante é o valor ``n`` do número de discos. Quanto menor esse valor mais simples e fácil de ser resolvido é o quebra-cabeça. O capítulo `Recursão `__ do livro `Resolução de Problemas com Algoritmos e Estruturas de Dados usando Python `_ afirma que uma solução, função, algoritmo, ... em geral satisfaz certas regras ou leis. Um algoritmo ou função ou subrotina ou método ... recursivo deve: - Ter um **caso base** que é sinônimo de instância que pode ser resolvida prontamente, sem que seja necessário decompor ainda mais o problema em subproblemas menores. Na nossa solução do quebra-cabeça das Torres de Hanoi o caso base foi aquele em que o número ``n`` de discos é zero. Ou seja, não havia disco algum e nada necessitava ser feito para resolver o quebra-cabeça. - Alterar seu estado de maneira a se **aproximar do caso base**. Isto corresponde a simplificar o problema. Na função ``hanoi()``, quando havia algum disco no quebra-cabeça, o problema com ``n`` discos foi quebrado em dois subproblemas com ``n-1``. Os subproblemas se aproximavam do caso base ``n = 0``. - Chamar a si mesmo direta ou indiretamente. No caso de ``hanoi()`` a função chamava a si duas vezes diretamente. Na mesma linha de análise estrutural de soluções recursivas, o capítulo `Recursão e algoritmos recursivos `_ do livro `Projeto de Algoritmos `_ mostra a seguinte estrutura que é frequente a algoritmos recursivos: :: se a instância é pequena, simples: resolva-a diretamente e retorne reduza a instância a instâncias menores do mesmo problema aplique recursivamente o método de solução a cada uma das instâncias menores combine as soluções das instâncias menores para obter um solução da instância atual e retorne Revisitemos a função ``hanoi()`` para identificar sua partes |:eye:| .. code:: python def hanoi(n, origem, auxiliar, destino, mov=0): '''(int, str, str, str, int) -> None Recebe o numero de discos 'n', os apelidos origem, auxiliar e destino dos pinos. Imprime as mesagens com os movimentos para resolver o quebra-cabeça das Torres de Hanoi com n discos. ''' # 1. caso base if n == 0: return None # 2. reduza e resolva recursivamente e combine a solução dos subproblemas hanoi(n-1, origem, destino, auxiliar, mov) # reduza e resolva recursivamente print(f"{mov}: mova o disco {n} do pino {origem} para o pino {destino}") hanoi(n-1, auxiliar, origem, destino, mov) # reduza e resolva recursivamente .. _my_Fatorial: Fatorial -------- .. index:: Problema do fatorial O problema que resolveremos agora é muito simples. O objetivo agora é nos apronfundarmos na mecânica da recursão e como ela opera, sendo que o problema é apenas um mero pretexto: **Problema (fatorial)**: Dado um inteiro não-negativo :math:`\mathtt{n}`, calcular o valor do seu fatorial, em símbolos :math:`\mathtt{n!}`. O valor de :math:`\mathtt{n!}` é :math:`\mathtt{1 \times 2 \times 3 \cdots \times n}`. Pode parecer estranho, mais é certamente muito conveniente, que combinemos que o valor de :math:`\mathtt{0!}` seja 1 |:thinking:|. .. index:: ``fatorialI()`` A função ``fatorialI()``, que esta a seguir, faz o serviço e é muito manjada. Ela funciona *iterativamente*, com um comando de repetição, o ``for``. Ela não usa recursão. .. code:: python def fatorialI(n): '''(int) -> int Recebe um inteiro n. Retorna n!. ''' fat = 1 for i in range(2, n+1): fat *= i return fat Agora vamos a recursão... Frequentemente o valor de :math:`\mathtt{n!}` é mostrado de maneira *recursiva* como em: .. math:: \begin{align*} \mathtt{n!} &= \begin{cases} 1 & \text{ se $\mathtt{{n} = 0}$},\\ \mathtt{{n}\times ({n}-1)}!& \text{ se $\mathtt{{n}>0}$}. \end{cases} \end{align*} Olhe |:eyes:| atentamente a recursão que está de cabo a rabo na especificação. A origem, onde tudo começou, a *base* de tudo é o valor de :math:`\mathtt{0!}` que é 1. Esse valor é a base pois dará suporte, apoio, a todo valor que será calculado. Agora um outro ingrediente da recursão é o fato dos subproblemas se aproximarem do caso base :math:`\mathtt{0!}`. O valor de :math:`\mathtt{n!}` é descrito em termos do valor de :math:`\mathtt{(n-1)!}` já que, para os valores positivos de :math:`\mathtt{n}`, o :math:`\mathtt{n-1}` está mais próximo de 0 do que :math:`\mathtt{n}`. .. index:: fatorial recursivo .. index:: ``fatorialR()`` A função ``fatoriaR()`` a seguir é apenas uma tradução da linguagem matemática da especificação para a linguagem Python. .. code-block:: python def fatorialR(n): '''(int) -> int Recebe um inteiro n. Retorna n!. ''' # caso base if n == 0: return 1 # resolva uma simplificação do problemas e monte a solução da chamada atual return n * fatorialR(n-1) Para obter o valor de :math:`\mathtt{n!}` para :math:`\mathtt{n \geq 1}` a função recursivamente obtem o valor de :math:`\mathtt{(n-1)!}` e o multiplica por :math:`\mathtt{n}`. Este produto será o valor retornado nesse nível da recursão. Neste momento talvez seja bom fazer uma pausa. Talvez seja elucidativo perguntar ao visualizador do Python o que ele pode nos revelar sobra a execução da função ``fatorialR()``. Na versão que foi preparada para o visualizador o código foi dissecado em pequenas partes para explorarmos cada um dos componentes da solução em ação. .. raw:: html Você também pode assistir ``fatorialR()`` trabalhando na página do `cscircles `__. .. _my_Euclides: Máximo divisor comum e Euclides ------------------------------- .. index:: divisor comum .. index:: máximo divisor comum .. index:: maior divisor comum .. index:: mdc Um **divisor comum** de dois números inteiros ``a`` e ``b`` é um número que divide ambos. O **maior divisor comum** ou **máximo divisor comum** de ``a`` e ``b``, denotado por :math:`\mathtt{mdc}(a,b)`, é o maior inteiro positivo que é divisor comum de ``a`` e ``b``. Por exemplo: * os divisores positivos de ``20`` são ``1``, ``2``, ``4``, ``5``, ``10`` e ``20``; * os divisores positivos de ``12`` são ``1``, ``2``, ``3``, ``4``, ``6 e ``12``; * os divisores comuns de ``12`` e ``20`` são ``1``, ``2`` e ``4`` e o maior divisor comum de ``12`` e ``20`` é ``4``, em símbolos :math:`\mathtt{mdc}(12,20) = 4`; * o maior divisor comum de ``65`` e ``36`` é ``1``; Em |Python|: .. code-block:: python In [1]: import math In [2]: help(math.gcd) # greatest common divisor In [3]: math.gcd(20,12) # = mdc(20,12) Out[3]: 4 In [4]: math.gcd(65,36) Out[4]: 1 .. index:: fração redutível .. index:: fração irredutível .. index:: números coprimos .. index:: números relativamente primos Uma fração ``a/b`` é **redutível** se existe um número inteiro :math:`\mathtt{d > 1}` tal que ``d`` divide de ``a`` e ``d`` divide ``b``. Uma fração ``a/b`` é **irredutível** se o maior inteiro ``d`` que divide ``a`` e ``b`` é ``1``. A fração ``3447882627912/174363006624`` é um exemplo de fração redutível pois .. math:: \frac{3447882627912}{17436306624} = \frac{6391608 \times 539439}{6391608 \times 2728} = \frac{539439}{2728} Já a fração ``539439/2728`` é irredutível já que o maior divisor comum de ``539439`` e ``2728`` é 1, em símbolos :math:`\mathtt{mdc(539439,2728) = 1}`. Quando o maior divisor de dois números inteiros ``a`` e ``b`` é 1 dizemos que ``a`` e ``b`` são **relativamente primos** ou **coprimos**. Logo, ``539439`` e ``2728`` são relativamente primos. Em implementações de classes que representam números racionais como a classe ``Fraction`` que fizemos na seção :ref:`my_ClasseFraction` ou a classe ``Fraction`` do módulo ``fractions`` do |Python|, um operação fundamental é transformar as frações em suas versões irredutíveis. .. code-block:: python In [1]: import fractions In [7]: fractions.Fraction(3447882627912, 17436306624) Out[7]: fractions.Fraction(539439, 2728) In [8]: import fracao # nossa implementação de Fraction In [10]: fracao.Fraction(3447882627912, 17436306624) Out[10]: fracao.Fraction(539439, 2728) Essa simplicação é feita por questão de eficiência já que gastamos menos tempo e é mais fácil manipularmos frações com menos dígitos. |:memo:| |:smirk:| Para transformar uma fração ``a/b`` em uma fração irredutível equivalente devemos determinar o número :math:`\mathtt{d = \textup{mdc}(a,b)}` e passar a considerar a fração .. math:: \mathtt{\frac{a//d}{b//d}}. Por exemplo, :math:`6391608` é o maior número que divide :math:`3447882627912` e :math:`17436306624`. .. code-block:: python In [11]: import math In [12]: math.gcd(3447882627912, 17436306624) Out[12]: 6391608 e a correspondente fração irredutível é .. code-block:: python In [13]: d = math.gcd(3447882627912, 17436306624) In [13]: fractions.Fraction(3447882627912//d, 17436306624//d) Out[13]: Fraction(539439, 2728) In [14]: math.gcd(539439, 2728) Out[14]: 1 É verdade que a linguagem |Python| possui o módulo ``math`` que por sua vez possui a função ``gcd()`` que retorna o maior divisor comum de dois número inteiros dados. Apesar disso vamos explorar o problema abaixo a fim de descobrir o que ele tem a nos ensinar em termos de recursão e, em uma próxima oportunidade, de tempo gasto por programas. **Problema (máximo divisor comum)**: Dados dois números inteiros não-negativos ``a`` e ``b``, encontrar o máximo divisor comum de ``a`` e ``b``. O problema considera um par de números não-negativos apenas por conveniência para economizarmos um ou duas linhas de código que poderiam nos distrair um pouco e enevoando as ideias principais. Começaremos explorando uma solução simples que testa desnecessariamente vários candidados a :math:`\mathtt{mdc}(a, b)`. Para calcular o :math:`\mathtt{mdc}(a,b)` a ideia do `Euclides `_ se apoia na seguintes fórmula recursiva: .. math:: \mathtt{mdc(a, b)} = \begin{cases} \mathtt{a} & \mbox{se } \mathtt{b = 0} \nonumber \\ \mathtt{mdc(b, a \% b)} & \mbox{para } \mathtt{b > 0}. \nonumber \end{cases} Observemos que a fórmula de Euclides apresenta um caso base que é quando :math:`\mathtt{b = 0}`. Para valores de ``b`` maiores que ``0``, o problema é simplificado, devemos determinar o maior divisor comum entre um par de valores menores já que ``a % b`` é menor que ``a``. Essa formula é genuinamente recursiva! Fórmulas como essa não são chamadas de recursivas, são conhecidas pelo nome de **relações de recorrência**. A validade da recorrência proposta por Euclides é baseada no seguinte observação. Sejam :math:`\mathtt{a}` e :math:`b` número inteiros tais :math:`\mathtt{a \geq 0}` e :math:`\mathtt{b > 0}`. Temos que o par :math:`\mathtt{a, b}` tem os mesmos divisores comuns que o par :math:`\mathtt{b, a \% b}`. Essa afirmação nos diz que se ``d`` é um divisor de ``a`` e de ``b`` se e somente se ``d`` é um divisor de ``b`` e de ``a \% b``. Para nos conversermos desse fato podemos nos inspirar no rabiscos abaixo. Digamos que no rabiscos ``a`` e ``b`` representam linhas de comprimento múltiplo de ``d``, no caso, :math:`\mathtt{a = 11 \times d}` e :math:`\mathtt{b = 4 \times d}`. Se ``d`` representa um divisor de ``a`` e ``b``, examinando os rabiscos fica meio na cara que ``d`` também divide ``a % b``, independentemente de quem são ``d``, ``a`` e ``b``. |:thinking:| :: |---| d |---|---|---|---|---|---|---|---|---|---|---| a |---|---|---|---| b |---|---| a % b Por outro lado, se ``d`` é divisor de ``b`` e de ``a % b``, examinando os rabiscos, fica meio na cara que ``d`` também divide ``a``. :: |---| d |---|---|---|---| b |---|---| a % b |---|---|---|---|---|---|---|---|---|---|---| a Essa rabiscação toda pode ser tranformada em um demonstração com palavras e não apenas linhas ilustrativas. **Demonstração**: O algoritmo da divisão nos diz que :math:`\mathtt{a = qb + r}`, em que :math:`\mathtt{q = a//b}` e :math:`\mathtt{r= a\%b}`. Assim, .. math:: \mathtt{a = (a//b) \times b + a\%b} e portanto .. math:: \mathtt{a\%b = a - (a//b) \times b}. Dessa igualdade vemos que se ``d`` divide ``a`` e ``d`` divide ``b``, então ``d`` deve dividir :math:`\mathtt{a\%b}`. Reciprocamente, se ``d`` divide ``b`` e ``d`` divide ``a%b``, então ``d`` tem que dividir ``a`` já que :math:`\mathtt{a = (a//b)\times b + a\%b}`. Com papel e lápis, em vez de com um programa de computador, estamos habituados a executar o algoritmos de Euclides com tabelas Em geral seu irmãozinho ou irmazinha escreve .. math:: \begin{array}{ c|c } \mathtt{a} & \mathtt{b} \\ \hline \mathtt{a\%b} & \mathtt{a//b} \end{array} Aqui escrevemos .. math:: \begin{array}{ c|c } & \mathtt{a//b} \\ \hline \mathtt{a} & \mathtt{b} \\ \hline \mathtt{a\%b} & \end{array} Para aplicar o algoritmo de Euclides com papel e lápis fazemos .. math:: \begin{array}{ c|c|c|c|c|c|c } & 2 & 3 & 2 & 1 & 2 & \\ \hline 372 & 162 & 48 & 16 & 12 & 6 & 0 \\ \hline 48 & 18 & 12 & 6 & 0 & & \end{array} Em que na linha inferior :math:`\mathtt{48, 18, 12, 6, 0}` são os restos das divisões e na linha superior :math:`\mathtt{2, 3, 2, 1, 2}` são os quocientes das divisões. .. index:: ``euclidesR()`` Em |Python| temos duas versões do algoritmo de Euclides. A função ``euclideR()`` é a versão em que a recursividade está evidente. .. code-block:: python def euclidesR(a, b): """(int, int) -> int RECEBE dois inteiros a e b. RETORNA mdc(a, b); se a = 0 = b retorna 0 para indicar erro. PRÉ-CONDIÇÃO: a >= 0, b >=0 """ if b == 0: return a return euclidesR(b, a % b) .. index:: ``euclidesI()`` Já a função ``euclidesI()`` é a versão iterativa de ``euclidesR()``. Na versão iterativa a recursão está escondida na ideia recursiva que está nas suas entranhas. |:open_mouth:| .. code-block:: python def euclidesI(a, b): """ (int, int) -> int RECEBE dois inteiros a e b; se a = 0 = b retorna 0 para indicar erro. RETORNA mdc(a, b). PRÉ-CONDIÇÃO: a >= 0 e b >= 0 """ r = b while r != 0: r = a % b a = b b = r return a .. index:: recursão de cauda .. index:: tail recursion Da maneira semelhante a função ``fatorialR()`` e a função ``EuclidesR()`` têm uma **recursão de cauda** (= *tail recursion*). Isso significa a chamada recursiva é feita apenas uma vez no final da função. Recursões de cauda podem ser facilmente reescritas de forma a trocarmos recursão por iteração. Podemos reescrever a recursão através de comandos de repetição como um ``for...`` ou ``while...``. Aplicamos essa técnica de reescrita quando fizemos as funções ``fatorialI()`` e ``EuclidesI()``. Assista ``euclidesR()`` em pleno horário de expediente: .. raw:: html Para acessar diretamente a função ``euclidesR()`` no |cscircles| vá para `cá `__. .. _my_Rastros: Rastros ------- Entender o processo recursivo é exatamente o nosso objetivo neste momento. Acreditamos que nesta altura do campeonato sejamos fluentes em escrever uma função como a ``fatorialI()`` que calcula o fatorial de um número inteiro. Talvez este seja um bom momento para examinarmos alguns esquemas utilizados para enxergarmos a estrutura das chamadas sucessivas feitas por funções e algoritmos recursivos. Todos esses esquemas evidenciam a *ordem das chamadas* e *quem as evocou*. A *ordem das chamadas* tem a ver com **cronologia** e *quem as evocou* tem a ver com **hereditariedade**, qual execução é mãe ou filha de qual execução. Junto com o visualizador Python, esses esquemas serão úteis para desvendarmos o mecanismo da recursão. .. index:: rastro da execução Admiremos esse esquema de exibir chamadas quando ``fatorialR(7)`` é executado. Chamaremos esse esquema de **rastro da execução** e aceitamos sugestões para outros nomes. |:footprints:| Logo abaixo é feita a interpretação da estrutura exibida. :: fatorialR(7) fatorialR(6) fatorialR(5) fatorialR(4) fatorialR(3) fatorialR(2) fatorialR(1) fatorialR(0) = 1 fatorialR(1) = 1 fatorialR(2) = 2 fatorialR(3) = 6 fatorialR(4) = 24 fatorialR(5) = 120 fatorialR(6) = 720 fatorialR(7) = 5040 As linhas no rastro exibido, de cima para baixo, indicam a cronologia, o momento em que as chamadas e os retornos das chamadas ocorreram. A linha com ``fatorialR(4)`` indica o momento em que a execução desta chamada se iniciou e a linha ``fatorialR(4) = 24`` indica o instante em que ela se encerrou. O final de ``fatorialR(4)`` é quando o comando ``return 4 * fatorialR(3)`` é executado. Desta forma, a linha em que ``fatorialR(4) = 24`` é mostrado indica que nesse momento as chamadas ``fatorialR(7)``, ``fatorialR(6)`` e ``fatorialR(5)`` ainda não foram encerradas, são as únicas sendo executadas esperando por seu desfecho, enquanto que ``fatorialR(3)``, ``fatorialR(2)``, ``fatorialR(1)`` e ``fatorialR(1)`` terminaram. A tabulação indica quais chamadas foram feitas por quais execuções. Qual é a execução **mãe** e qual é a **filha**. |:family_woman_girl:| Como a tabulação de ``fatorialR(3)`` esta imediatamente à direita da tabulação de ``fatorialR(3)`` e **não existe** nenhum conteúdo de uma linha que atravessa essa tabulação, isso indica que a chamada ``fatorialR(3)`` foi realizada durante a execução de ``fatorialR(4)``. Em outros termos ``fatorialR(4)`` é **mãe** |:woman_curly_haired_tone5:| de ``fatorialR(3)`` ou, equivalentemete, ``fatorial(3)`` é **filha** |:girl_tone5:| de ``fatorialR(4)``. No que diz respeito à estrutura das chamadas recursivas da função ``fatorialR()`` há ainda uma metáfora que pode ser educativa. Evidentemente, os mesmos rastro de visualização para funções que possuem mais chamadas recursivas, como ``hanoi()``, é mais envolvente. A seguir está um rastro de execução para ``hanoi(3,'A','B','C')``. :: hanoi(3,'A','B','C') hanoi(2,'A','C','B') hanoi(1,'A','B','C') hanoi(0,'A','C','B') hanoi(0,'A','C','B') = None 1: mova o disco 1 do pino A para o pino C hanoi(0,'B','A','C') hanoi(0,'B','A','C') = None hanoi(1,'A','B','C') = None 2: mova o disco 2 do pino A para o pino B hanoi(1,'C','A','B') hanoi(0,'C','B','A') hanoi(0,'C','B','A') = None 3: mova o disco 1 do pino C para o pino B hanoi(0,'A','C','B') hanoi(0,'A','C','B') = None hanoi(1,'C','A','B') = None hanoi(2,'A','C','B') = None 4: mova o disco 3 do pino A para o pino C hanoi(2,'B','A','C') hanoi(1,'B','C','A') hanoi(0,'B','A','C') hanoi(0,'B','A','C') = None 5: mova o disco 1 do pino B para o pino A hanoi(0,'C','B','A') hanoi(0,'C','B','A') = None hanoi(1,'B','C','A') = None 6: mova o disco 2 do pino B para o pino C hanoi(1,'A','B','C') hanoi(0,'A','C','B') hanoi(0,'A','C','B') = None 7: mova o disco 1 do pino A para o pino C hanoi(0,'B','A','C') hanoi(0,'B','A','C') = None hanoi(1,'A','B','C') = None hanoi(2,'B','A','C') = None hanoi(3,'A','B','C') = None A linha cronológica, além do número associado ao movimento |:stuck_out_tongue_winking_eye:|, nos diz que a mensagem ``3: mova o disco 1 do pino C para o pino B`` foi produzida antes da mensagem ``5: mova o disco 1 do pino B para o pino A``. A numeração ou a cronologia nos diz qual é a sequência dos movimentos. A linha com ``hanoi(2,'B','A','C') = None`` nos indica o instante em que a chamada ``hanoi(2,'B','A','C')`` terminou o seu serviço e encerrou sua participação no trabalho de construção da sequência de movimentos da solução. Sob a administração de ``hanoi(2,'B','A','C')`` foram produzidas as mensagens: :: 5: mova o disco 1 do pino B para o pino A 6: mova o disco 2 do pino B para o pino C 7: mova o disco 1 do pino A para o pino C Já chamadas como ``hanoi(0,'C','B','A')`` não produziram movimento algum e imediatamente após iniciada foram encerradas com ``hanoi(0,'C','B','A') = None``. Bem, é difícil produzir algum movimento sem que tenhamos a matéria prima básica que são os discos. Em termos de hereditariedade ``hanoi(2,'B','A','C')``, após o movimento ``4: mova o disco 3 do pino A para o pino C``, tem como filhas ``hanoi(1,'B','C','A')`` e ``hanoi(1,'A','B','C')`` e como netas ``hanoi(0,'B','A','C')`` ``hanoi(0,'C','B','A')`` ``hanoi(0,'A','C','B')`` e ``hanoi(0,'B','A','C')``. ``hanoi(2,'B','A','C')`` não tem bisnetas, já ``hanoi(3,'A','B','C')`` evidentemente tem bisnetas. .. index:: Matryosha A estrutura das chamadas recursivas originadas por ``fatorialR(4)`` assemelham-se a das bonecas `Matryoshka `_ |:nesting_dolls:|. As Matryoshka estão umas dentro das outras. A maior boneca, a matriarca, a mais velha, contém todas as demais em seu interior. Ela se comporta como a chamada ``fatorialR(7)``. A maior boneca contém dentro de si a segunda maior, que por sua vez contém a terceira, que por sua vez contém a quarta maior ... e assim por diante. A execução ``fatorialR(7)`` se comporta como se estivessemos abrindo uma a uma as bonecas. A cada momento abrindo bonecas cada vez menores, até chegarmos à menor de todas, a boneca base, a tata...taraneta mais nova da matriarca, a boneca que não contém boneca alguma em seu interior. No caso de ``fatorialR(7)`` a *boneca base*, *a mais nova* é ``fatorialR(0)``. Em seguida, depois de chegar à mais nova, as chamadas originadas por ``fatorialR(7)`` passam a trilhar o caminho inverso, fechando uma a uma as bonecas, até voltar ao ponto de partida, a maior boneca, a mais velha, a matriaca, a própria boneca ``fatorialR(7)``. .. image:: ./imgs/Matryoshka_transparent.* :width: 1822 :height: 1172 :scale: 15 :alt: The concept of the Russian dolls is used as a visual example in various topics :align: center :target: https://en.wikipedia.org/wiki/Matryoshka_doll#/media/File:Matryoshka_transparent.png Diagramas das execuções ----------------------- .. index:: diagrama de execução Uma outra maneira para visualizarmos a execução de uma função é através de um **diagrama de execução**. Nesse diagrama abrimos um retângulo sempre que uma função começa a ser executada e só fechamos o retângulo após o encerramento de sua execução. As variáveis da chamada de uma função são colocadas dentro do correspondente retângulo. As primeiras variáveis no retângulo são os parâmetros da função que inicialmente são apelidos para os valores passados como argumentos. Quando uma chamada recursiva é feita, abrimos o retângulo da nova execução da função dentro do retângulo da função que fez a chamada. A seguir está o diagrama de execução obtido ao simular a chamada ``fatorialR(3)``, que no diagrama aparece com o nome ``fatorial(3)``. .. image:: ./imgs/diagrama_de_execucao_fatorial.* :width: 1413 :height: 898 :scale: 50 :alt: Diagrama de execução da chamada fatorialR(3) :align: center Aponte um dedo para qualquer ponto da ilustração. Os retângulos que contém o ponto ao qual o seu dedo está se referindo são aquelas que estão sendo executadas, ativas, naquele ponto da computação. Note que o diagrama, da mesma meneira que o visualizador do Python, mostra que cada chamada tem as suas própria variáveis. Há várias variáveis de nome ``n``. Entretanto, cada ponto da execução tem a sua própria variável ``n``. Na chamada ``fatorialR(3)`` a variável ``n`` é apelido para 3. Já, na chamada ``fatorialR(0)``, a variável ``n`` é apelido para 0. O contexto em que se encontra a computação indica qual é a variável ``n`` a qual estamos nos referindo. Agora é a vez de admirarmos o diagrama de execução da execução de ``hanoi(3, 'A', 'B', 'C')``. .. image:: ./imgs/diagrama_de_execucao_hanoi.* :width: 1422 :height: 1009 :scale: 50 :alt: Diagrama de execução da chamada hanoi(3, 2) :align: center Rastros de execução e diagramas de execução contêm basicamente as mesma informações. Diagramas de execução são convenientes quando estamos realizando alguma simulações com papel e lápis ou lousa e giz ou ... Paisagens vistas ---------------- Nesta nossa andança pelo reino da recursão vimos como com o pensamento recursivo nos leva a resolver um problema em termos das soluções de versões mais simples do **mesmo problema**. A função ``hanoi()`` nos mostrou como a solução de um problema pode ser descrita de maneira simples através de recursão. |:+1_tone4:| A ideia utilizada para resolver um problema pode ser inerentemente recursiva, apesar do código produzido não conter recursão. Presenciamos claramente esse fenômeno quando nos deparamos com as funções ``fatorialI()`` e ``euclidesI()``. Exercícios ---------- #. Do ponto de vista de recursão, qual o erro da tirinha no início deste capítulo? #. Do ponto de vista de recursão, qual o erro na afirmação: *Para entender recursão é necessário entender recursão*? #. O que acontence se a função ``fatorialR()`` é chamada com um número negativo como argumento? #. Modifique a função ``fatorialR()`` para que ela exiba um rastro de sua execução. Você pode adicionar ao protótipo da função algum parâmetro pré-definido. Por exemplo, a chamada ``fatorialR(7)`` deve produzir as mensagens: :: fatorialR(7) fatorialR(6) fatorialR(5) fatorialR(4) fatorialR(3) fatorialR(2) fatorialR(1) fatorialR(0) = 1 fatorialR(1) = 1 fatorialR(2) = 2 fatorialR(3) = 6 fatorialR(4) = 24 fatorialR(5) = 120 fatorialR(6) = 720 fatorialR(7) = 5040 #. Modifique a função ``euclidesR()`` para que ela exiba um rastro de sua execução. Você pode adicionar ao protótipo da função algum parâmetro pré-definido. Por exemplo, a chamada ``fatorialR(7)`` deve produzir as mensagens: :: euclidesR(372,162) euclidesR(162,48) euclidesR(48,18) euclidesR(18,12) euclidesR(12,6) euclidesR(6,0) = 6 euclidesR(12,6) = 6 euclidesR(18,12) = 6 euclidesR(48,18) = 6 euclidesR(162,48) = 6 euclidesR(372,162) = 6 #. (`Função de Collatz `_) Considere a função recursiva a seguir. Essa função é relacionada a um problema famoso em teoria dos números que está a espera de solução e é conhecido como *Problema de Collatz* ou *O problema* :math:`3n+1`. .. code:: python def collatz(n): '''(int) -> None Recebe um número inteiro positivo n. Imprime a sequência de collatz de n. ''' print(f"{n} ", end="") # caso base if n == 1: return None # simplifique? if n % 2 == 0: collatz(n//2) else: collatz(3*n+1) Por exemplo, ``collatz(7)``, que é responsável por 16 chamadas recursivas, produz a sequência: :: In [6]: collatz(7) 7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1 Chamaremos os inteiros que aparecem como argumento na chamada ``collatz(n)`` de **sequência de collatz** (*hailstone sequence*) de ``n``. Por exemplo a sequência de collatz de 7 é ``7 22 11 34 17 52 26 13 40 20 10 5 16 8 4 2 1``. Escreva uma função ``conte_collatz()`` que *recebe* um inteiro positivo ``n`` é *retorna* o número de chamadas recursivas feitas durante a execução de ``collatz(n)`` e *imprime* a sequência de collatz de ``n``. O problema envolvendo a função ``collatz()`` é que **não se sabe** se ela termina para todo inteiro positivo ``n``. :cold_face: Em termos equivalentes, **não se sabe** se a sequência de collatz de todo inteiro positivo ``n`` é finita. #. Modifique a função ``hanoi()`` para que ela imprima o número de ordem de cada movimento. Você pode mudar a especificação do valor retornado pela função. Por exemplo, a chamada ``hanoi(3,'A','B','C')`` deve produzir as mensagens: :: 1: mova o disco 1 do pino A para o pino C 2: mova o disco 2 do pino A para o pino B 3: mova o disco 1 do pino C para o pino B 4: mova o disco 3 do pino A para o pino C 5: mova o disco 1 do pino B para o pino A 6: mova o disco 2 do pino B para o pino C 7: mova o disco 1 do pino A para o pino C #. Modifique a função ``hanoi()`` para que exiba um rastro da execução. Você pode adicionar ao protótipo da função algum parâmetro pré-definido. Você pode mudar a especificação do valor retornado pela função. Por exemplo, a chamada ``hanoi(2,'A','B','C')`` deve produzir as mensagens: :: hanoi(2,'A','B','C') hanoi(1,'A','C','B') hanoi(0,'A','B','C') hanoi(0,'A','B','C') = None 1: mova o disco 1 do pino A para o pino B hanoi(0,'C','A','B') hanoi(0,'C','A','B') = None hanoi(1,'A','C','B') = None 2: mova o disco 2 do pino A para o pino C hanoi(1,'B','A','C') hanoi(0,'B','C','A') hanoi(0,'B','C','A') = None 3: mova o disco 1 do pino B para o pino C hanoi(0,'A','B','C') hanoi(0,'A','B','C') = None hanoi(1,'B','A','C') = None hanoi(2,'A','B','C') = None #. Escreva uma função recursiva que *recebe* um número inteiro não-negativo :math:`\mathtt{n}` e *retorna* o valor de :math:`\mathtt{\ln(n!)}`. #. Escreva uma função recursiva que *recebe* um número inteiro não-negativo :math:`\mathtt{n}` e *retorna* uma string com a representação binária de :math:`\mathtt{n}`. #. Escreva uma função recursiva que *recebe* um número inteiro não-negativo :math:`\mathtt{n}` e *retorna* a soma de seus dígitos. #. Escreva uma função recursiva que *recebe* ums string ``s`` e *retorna* ``True`` se ``s`` é palíndromo e *retorna* ``False`` em caso contrário. #. Escreva uma função recursiva que *recebe* um número inteiro positivo :math:`\mathtt{n}` e *retorna* uma lista com os comprimentos dos traços das subdivisões de uma régua de ordem :math:`\mathtt{n}`. Em uma régua de **ordem** :math:`\mathtt{n}` o traço no ponto médio da régua tem comprimento :math:`\mathtt{n}`. os traços nos pontos médios das subdivisões esquerda e direta têm comprimento :math:`\mathtt{n-1}`, e assim por diante. Para :math:`\mathtt{n = 3}` a régua se parece com :: | | | | | | | | | | | e a correspondente lista é ``[1, 2, 1, 3, 1, 2, 1]`` Para :math:`\mathtt{n = 4}` a régua se parece com :: | | | | | | | | | | | | | | | | | | | | | | | | | | e a correspondente lista é ``[1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1]``. #. Escreva uma função recursiva que *recebe* uma string representando uma sequência de parênteses, colchetes e chaves e *retorna* ``True`` se a sequência é bem-formada e ``False`` em caso contrário. #. Uma **cópia profunda** (*deepcopy*) de um objeto é uma cópia recursiva do objeto que não compartilha dados mutáveis, como listas (``list``) e dicionários (``dict``), com o objeto original. Escreva uma função que *recebe* um objeto em que os componentes mutáveis podem ser recursivamente das classes ``list`` e ``dict`` e os componentes imutáveis podem ser das classes ``int``, ``str``, ``float``, ``NoneType``, ``bool`` e que *retorna* uma cópia profunda do objeto. #. Há algo estranho com a função a seguir? .. code:: python def f(n): '''(int) -> str''' s = f(n-3) + str(n) + f(n-2) + str(n) if n == 0: return '' return s #. Do ponto de vista de recursão, qual o erro na animação a seguir? .. image:: ./imgs/debugging-recursive-code.gif :width: 384 :height: 384 :scale: 50 :alt: Debugging recursive code :align: center :target: https://devopsreactions.tumblr.com/post/42420931277/debugging-recursive-code O que é ... ----------- Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. |:nerd:| .. glossary:: Base da recursão: Situação em que uma função recursiva resolve o problema diretamente, sem fazer chamada recursiva alguma. Função recursiva Função que possui chamadas diretas ou indiretas a si mesma. |:dizzy_face:| Diagrama de execução de uma função Representação que exibe a sequência e a interdependência das chamadas de uma função recursiva. |:footprints:| Rastro de um função recursiva Representação que exibe a sequência e a interdependência das chamadas de uma função recursiva. |:footprints:| Recursão Método em que a solução de problema é descrita em termos da solução de versões mais simples do mesmo problema. |:confused:| Considere a recorrência de Euclides que descreve o maior divisor comum de dois inteiros ``a`` e ``b`` em termos do do maior divisor comum de ``b`` e ``a % b``. 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.