16. 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. 😮

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. 🤓

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 👑.

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. 😮

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.

16.1. 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: 🤨

• As Torres de Hanoi nos mostra como com simplicidade, com uma certa ingenuidade 👧🏼 🧒🏽 e com muita engenhosidade 🌝 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.

16.2. Introduçã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. 🤔 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 😕. Para entender essa ideia confusa resolveremos vários problemas de forma recursiva. Com uma certa prática e os exercícios 🚴, a ideia passará ser mais ou menos natural e menos mágica 😌.

16.3. 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 😲.

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

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.

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.

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! 🤨

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.

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! 😵. Parece que a cobra mordeu o rabo. 🐍 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?! 🤔 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?! 🤔 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! 😯) para resolvermos a Torre de Hanoi com 10 discos basta resolvermos o quebra-cabeça (pasmem! pasmem!) com zero discos. 😵‍💫 Sim! Zero discos! 😵 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.

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.

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.

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.

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 😫, apesar de poder parecer misteriosa 🤨. 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. 🤨 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. 🤔

16.4. Anatomia

✋ Antes de continuarmos, pausa para reflexão…

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.

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 👁️

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

16.5. 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 \(\mathtt{n}\), calcular o valor do seu fatorial, em símbolos \(\mathtt{n!}\).

O valor de \(\mathtt{n!}\) é \(\mathtt{1 \times 2 \times 3 \cdots \times n}\). Pode parecer estranho, mais é certamente muito conveniente, que combinemos que o valor de \(\mathtt{0!}\) seja 1 🤔.

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.

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 \(\mathtt{n!}\) é mostrado de maneira recursiva como em:

\[\begin{split}\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*}\end{split}\]

Olhe 👀 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 \(\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 \(\mathtt{0!}\). O valor de \(\mathtt{n!}\) é descrito em termos do valor de \(\mathtt{(n-1)!}\) já que, para os valores positivos de \(\mathtt{n}\), o \(\mathtt{n-1}\) está mais próximo de 0 do que \(\mathtt{n}\).

A função fatoriaR() a seguir é apenas uma tradução da linguagem matemática da especificação para a linguagem 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 \(\mathtt{n!}\) para \(\mathtt{n \geq 1}\) a função recursivamente obtem o valor de \(\mathtt{(n-1)!}\) e o multiplica por \(\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.

Você também pode assistir fatorialR() trabalhando na página do cscircles.

16.6. Máximo divisor comum e Euclides

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 \(\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 \(\mathtt{mdc}(12,20) = 4\);
• o maior divisor comum de 65 e 36 é 1;

Em 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

Uma fração a/b é redutível se existe um número inteiro \(\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

\[\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 \(\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 Classe Fraction ou a classe Fraction do módulo fractions do Python, um operação fundamental é transformar as frações em suas versões irredutíveis.

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. 📝 😏

Para transformar uma fração a/b em uma fração irredutível equivalente devemos determinar o número \(\mathtt{d = \textup{mdc}(a,b)}\) e passar a considerar a fração

\[\mathtt{\frac{a//d}{b//d}}.\]

Por exemplo, \(6391608\) é o maior número que divide \(3447882627912\) e \(17436306624\).

In [11]: import math

In [12]: math.gcd(3447882627912, 17436306624)
Out[12]: 6391608

e a correspondente fração irredutível é

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 \(\mathtt{mdc}(a, b)\).

Para calcular o \(\mathtt{mdc}(a,b)\) a ideia do Euclides se apoia na seguintes fórmula recursiva:

\[\begin{split}\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}\end{split}\]

Observemos que a fórmula de Euclides apresenta um caso base que é quando \(\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 \(\mathtt{a}\) e \(b\) número inteiros tais \(\mathtt{a \geq 0}\) e \(\mathtt{b > 0}\). Temos que o par \(\mathtt{a, b}\) tem os mesmos divisores comuns que o par \(\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, \(\mathtt{a = 11 \times d}\) e \(\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. 🤔

|---|  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 \(\mathtt{a = qb + r}\), em que \(\mathtt{q = a//b}\) e \(\mathtt{r= a\%b}\). Assim,

\[\mathtt{a = (a//b) \times b + a\%b}\]

e portanto

\[\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 \(\mathtt{a\%b}\). Reciprocamente, se d divide b e d divide a%b, então d tem que dividir a já que \(\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

\[\begin{split}\begin{array}{ c|c } \mathtt{a} & \mathtt{b} \\ \hline \mathtt{a\%b} & \mathtt{a//b} \end{array}\end{split}\]

Aqui escrevemos

\[\begin{split}\begin{array}{ c|c } & \mathtt{a//b} \\ \hline \mathtt{a} & \mathtt{b} \\ \hline \mathtt{a\%b} & \end{array}\end{split}\]

Para aplicar o algoritmo de Euclides com papel e lápis fazemos

\[\begin{split}\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}\end{split}\]

Em que na linha inferior \(\mathtt{48, 18, 12, 6, 0}\) são os restos das divisões e na linha superior \(\mathtt{2, 3, 2, 1, 2}\) são os quocientes das divisões.

Em Python temos duas versões do algoritmo de Euclides. A função euclideR() é a versão em que a recursividade está evidente.

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)

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. 😮

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

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:

Para acessar diretamente a função euclidesR() no cscircles vá para cá.

16.7. 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.

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. 👣 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. 👩‍👧 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 👩🏿‍🦱 de fatorialR(3) ou, equivalentemete, fatorial(3) é filha 👧🏿 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 😜, 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.

A estrutura das chamadas recursivas originadas por fatorialR(4) assemelham-se a das bonecas Matryoshka 🪆. 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).

16.8. Diagramas das execuções

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).

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').

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 …

16.9. 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. 👍🏾

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().

16.10. Exercícios

1. Do ponto de vista de recursão, qual o erro da tirinha no início deste capítulo?

2. Do ponto de vista de recursão, qual o erro na afirmação: Para entender recursão é necessário entender recursão?

3. O que acontence se a função fatorialR() é chamada com um número negativo como argumento?

4. 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
   

5. 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
   

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 \(3n+1\).

   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.

7. 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
   

8. 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
   

9. Escreva uma função recursiva que recebe um número inteiro não-negativo \(\mathtt{n}\) e retorna o valor de \(\mathtt{\ln(n!)}\).

10. Escreva uma função recursiva que recebe um número inteiro não-negativo \(\mathtt{n}\) e retorna uma string com a representação binária de \(\mathtt{n}\).

11. Escreva uma função recursiva que recebe um número inteiro não-negativo \(\mathtt{n}\) e retorna a soma de seus dígitos.

12. Escreva uma função recursiva que recebe ums string s e retorna True se s é palíndromo e retorna False em caso contrário.

13. Escreva uma função recursiva que recebe um número inteiro positivo \(\mathtt{n}\) e retorna uma lista com os comprimentos dos traços das subdivisões de uma régua de ordem \(\mathtt{n}\). Em uma régua de ordem \(\mathtt{n}\) o traço no ponto médio da régua tem comprimento \(\mathtt{n}\). os traços nos pontos médios das subdivisões esquerda e direta têm comprimento \(\mathtt{n-1}\), e assim por diante.

    Para \(\mathtt{n = 3}\) a régua se parece com

          |
      |   |   |
    | | | | | | |
    

    e a correspondente lista é [1, 2, 1, 3, 1, 2, 1] Para \(\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].

14. 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.

15. 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.

16. Há algo estranho com a função a seguir?

    def f(n):
        '''(int) -> str'''
        s = f(n-3) + str(n) + f(n-2) + str(n)
        if n == 0: return ''
        return s
    

17. Do ponto de vista de recursão, qual o erro na animação a seguir?

    

16.11. O que é …

Aqui vai um lista de termos que usamos nesse capítulo e os seus significados. 🤓

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. 😵

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. 👣

Rastro de um função recursiva

Representação que exibe a sequência e a interdependência das chamadas de uma função recursiva. 👣

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. 😕 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.

16.12. 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.