Construir algoritmos do jeito que fizemos até agora é algo intuitivo: repetimos um conjunto de instruções até que obtenhamos uma resposta desejada. Se você parar para pensar, a própria definição que fizemos no início do curso sugere que devemos escrever algoritmos assim: uma sequência de passos bem definidos para se resolver um determinado problema. Mais tarde, quando você estudar linguagens de programação, descobrirá que estamos falando de linguagens imperativas.
Para resolvermos problemas mais complicados de maneira estruturada, definimos laços e aprendemos a escrever algoritmos iterativos. Assim, temos que estabelecer um subconjunto de instruções, chamado de iteração, que altera os dados de entrada sucessivamente. Isso nos obriga a pensar em um resultado intermediário dessas operações, ao invés de pensar no resultado do algoritmo. Por exemplo, para multiplicar uma lista de números, precisamos definir uma variável acumuladora que, em cada iteração, guarda o produto dos primeiros números da lista.
Essa não é a única maneira de se resolver esse problema. Iremos aprender que recursão é uma estratégia para se pensar e escrever algoritmos que utiliza a estrutura recursiva do problema. Hum, antes de podermos explicar o que é recursão, precisamos entender o que é recursão.
Introdução
Observe a figura a seguir. Provavelmente você já construiu uma estrutura parecida. Ela é a foto de um castelo de cartas.
Repare que os alicerces do castelo são, eles mesmo, castelos de carta. Assim, antes de construir um castelo com 4 andares, tivemos antes que construir um castelo com 3 andares e assim por diante. A estrutura desse castelo na verdade inclui diversos outros castelos menores. Podemos desenhar alguns.
Podemos então fazer a seguinte pergunta.
Quantos castelos há em um castelo de cartas com quatro andares?
Para formalizar o nosso problema, vamos definir uma grade de triângulos como a figura definida à esquerda, que tem altura quatro. O nosso objetivo é contar o número de triângulos que tem a base na posição inferior (ver exemplos coloridos). Há alguns outros triângulos de ponta a cabeça, mas eles não são castelos de carta e não estamos interessados neles. Denotemos por $t(n)$ o número de triângulos de pé em um castelo de altura $n$.
Para o castelo de quatro andares, há muitos triângulos escondidos. Mas quando estamos começando a construir o castelo, é fácil contar diretamente.
Para um castelo de altura um, temos somente um triângulo e para um castelo de altura dois, temos quatro triângulos, três pequenos e um grande. Assim, sabemos que $t(1) = 1$ e $t(2) = 4$. Mas, à medida em que os castelos crescem, essa contagem torna-se mais difícil.
Para contar os triângulos de um castelo de altura $n = 4$, precisamos de um pouco mais de cuidado. Podemos pensar na estrutura que sustenta as duas cartas superiores e lembrar que um castelo é fundado sobre outros castelos menores. Se quisermos contar apenas os triângulos com a ponta no parte superior, teremos $4$ triângulos.
Além desses, ainda faltam os triângulos do lado esquerdo e do lado direito. Vamos colori-los para poder enxergar melhor.
Assim, precisamos somar os triângulos pintados de laranja e os pintados de verde. Há alguns triângulos que pintamos duas vezes, então também precisamos remover da conta os triângulos pintados de rosa.
Mas como calcular $t(3)$? Caímos no mesmo problema anterior, mas agora para uma instância menor! De maneira mais geral, podemos escrever
$$ t(n) = \begin{cases} 1 & \text{se } n = 1 \\ 4 & \text{se } n = 2 \\ n + 2\cdot t(n-1) - t(n-2) & \text{se } n \ge 3 \\ \end{cases} $$
Agora fica mais fácil calcular $t(4)$? Vamos supor que já conhecemos o valor de $t(m)$ para cada número $m < 4$, ou seja, suponha que já sabemos quanto vale $t(1), t(2)$ e $t(3)$. Você pode pensar que conhecemos um oráculo que nos dá o valor correto de $t(m)$ sempre que $m$ seja estritamente menor que $4$. Assim, $$ t(4) = 4 + 2 \cdot t(3) - t(2) = 4 + 2 \cdot 10 - 4 = 20. $$
A maneira com que o oráculo descobre o valor de $t(3)$ ou de $t(2)$ é
indiferente, contando que ele nos dê uma resposta correta. Assim,
digamos que o oráculo é uma função oraculo(m) que devolve o número
de triângulos de um castelo de cartas de altura $m < n$. Se você
confia que essa função oraculo está correta, então podemos escrever
uma função para calcular o número de triângulos de um castelo de
cartas de altura $n$. Para testar, vamos imprimir uma
tabela com os $10$ primeiros valores de $t(n)$.
def triangulos(n): if n == 1: return 1 elif n == 2: return 4 else: return n + 2 * oraculo(n - 1) - oraculo(n - 2) def main(): for i in range(1, 11): print(f"t({i}) = {triangulos(i)}") main()
Se tentarmos executar, não vai dar certo.
user@notebook:~/ra123456/recursao$ python3 triangulos.py t(1) = 1 t(2) = 4 Traceback (most recent call last): File "triangulos.py", line 13, in <module> main() File "triangulos.py", line 11, in main print(f"t({i}) = {triangulos(i)}") File "triangulos.py", line 7, in triangulos return n + 2 * oraculo(n - 1) - oraculo(n - 2) NameError: name 'oraculo' is not defined
É claro que para podemos executar esse programa, precisamos
implementar a função oraculo. Vejamos o que é preciso: queremos uma
função para calcular o número de triângulos de um castelo de cartas de
altura $m$. Mas essa é justamente a descrição da função triangulos
que estamos construindo! Vamos substituir oraculo por triangulos.
def triangulos(n): if n == 1: return 1 elif n == 2: return 4 else: return n + 2 * triangulos(n - 1) - triangulos(n - 2)
Pronto! Agora o interpretador Python não poderá reclamar que a função chamada não existe.
user@notebook:~/ra123456/recursao$ python3 triangulos.py t(1) = 1 t(2) = 4 t(3) = 10 t(4) = 20 t(5) = 35 t(6) = 56 t(7) = 84 t(8) = 120 t(9) = 165 t(10) = 220
E funciona! Na primeira vez que vemos isso, pode ser que pareça
mágica, mas há um nome mais apropriado. Observe que a função
triangulos chama a própria função triangulos. Chamamos isso de
recursão.
Recursão
Recursão é a estratégia para se resolver um problema da seguinte maneira:
-
Começamos identificando casos básicos e computando suas soluções diretamente.
-
Em seguida, tentamos resolver um caso geral fazendo o seguinte:
a) primeiro construímos uma ou mais instâncias menores do mesmo problema;
b) depois, obtemos soluções para essas instâncias fazendo chamadas recursivas;
c) finalmente, transformamos as soluções para as instâncias menores a fim de se obter um resultado do problema original.
Vamos ver um exemplo. Você deve se lembrar de que o fatorial de um número $n$ é o produto $1 \cdot 2 \cdot \ldots \cdot (n-1) \cdot n$. Se escrevermos esse produto com parênteses, podemos ver que para calcular o fatorial de $n$, precisamos antes calcular o fatorial de $n - 1$:
\[ n! = \big(1 \cdot 2 \cdot \ldots \cdot (n - 1)\big) \cdot n = (n-1)! \cdot n \]
Na verdade, quando definimos o fatorial de $n$ de uma maneira mais formal, fazemos isso recursivamente:
$$ n! = \begin{cases} 1 & \mbox{se } n = 0 \\ n \cdot (n-1)! & \mbox{se } n > 0. \end{cases} $$
Com essa definição, é trivial escrever um programa recursivo para calcular o fatorial de um número. Vamos fazer isso destacando cada parte da estratégia recursiva descrita acima.
def fatorial(n): # 1 caso básico if n == 0: resposta = 1 # 2. caso geral else: # a) instância menor m = n - 1 # b) chamada recursiva solucao = fatorial(m) # c) transformando a solução resposta = n * solucao return resposta
Normalmente escolhemos como casos básicos as instâncias irredutíveis, isso é, cujo o tamanho não podemos diminuir. Nesse exemplo, só há um caso básico, que corresponde à entrada $n = 0$. O caso geral corresponde a uma entrada arbitrária $n$ tal que $n > 0$. O fato de que no caso geral $n$ é diferente de zero é importante para que possamos construir uma instância menor do problema, $m = n - 1$. Resolvemos o subproblema recursivamente e obtemos uma solução para a instância menor. Finalmente, transformamos a solução da instância menor e obtemos a resposta do problema original.
Na função acima, criamos diversas variáveis para explicitar que estamos utilizando uma estratégia recursiva. Mas muitas pessoas escreveriam menos.
def fatorial(n): if n == 0: return 0 else: return fatorial(n - 1) * n
Com o tempo, você irá preferir essa segunda versão.
Pensando recursivamente
Vamos ver mais um exemplo para praticar.
Suponha que queremos cortar um pedaço de papel retangular, digamos, para fazer um cartão ou um bilhete. É bem provável que não exista folha disponível na papelaria com exatamente esse tamanho. Então precisamos descobrir qual o menor formato de papel em que cabe nosso retângulo.
O formato de papel mais utilizado no Brasil (e no mundo) é o formato A4. Na verdade, esse é apenas um formato de uma série cuidadosamente pensada, A0, A1, A2... Uma das vantagens dessa série é que podemos cortar uma folha A0 no meio e obter duas folhas A1 e assim por diante. Todas as medida são em milímetros, então descartamos a fração de milímetro quando dividirmos um número ímpar por dois.
O maior formato da série é o A0, que tem $841mm$ de largura e $1189mm$ de altura. Se dividirmos o maior lado de uma folha sucessivamente, podemos construir uma tabela com as dimensões dos primeiros formatos.
| Formato | Largura | Altura |
|---|---|---|
| A0 | 841 | 1189 |
| A1 | 594 | 841 |
| A2 | 420 | 594 |
| A3 | 297 | 420 |
| A4 | 210 | 297 |
| A5 | 148 | 210 |
Podemos fazer um desenho para visualizar os vários tamanhos.
Agora podemos tentar resolver nosso problema. Não é muito difícil resolver esse problema iterativamente, mas nesse exemplo queremos insistir numa solução recursiva. Utilizar recursão nem sempre é trivial como foi para a função fatorial, cuja a definição é ela mesma recursiva. Então, pode não parecer intuitivo tentar resolver esse problema de maneira recursiva. De qualquer forma, vamos tentar.
Suponha que recebemos uma folha de papel A0 e nos perguntam qual o menor subtipo de A0 em que cabe o retângulo? Vamos supor que o retângulo recebido cabe na folha A0, já que do contrário não há muito o que fazer. Será que a folha em mãos é de fato a menor possível? Se o retângulo não couber em uma folha A1, então a reposta é sim, a folha A0 é o menor subtipo. Mas se ele couber, então podemos voltar a nos perguntar: qual o menor subtipo de A1 em que cabe o retângulo? Repare que fizemos a mesma pergunta, mas agora para uma folha A1.
A primeira coisa para se escrever uma função recursiva — ou qualquer outra — é entender exatamente que problema queremos resolver. Aqui, queremos responder qual o menor subtipo de um papel A$n$ em que cabe o retângulo. Com isso, não é difícil escrever a seguinte função recursiva.
LARGURA_A0 = 841 ALTURA_A0 = 1189 def menor_subtipo(larg_folha, alt_folha, tipo_folha, larg_retangulo, alt_retangulo): """ Devolve o menor subtipo da folha em que cabe o retângulo. """ # cria instância menor larg_menor = alt_folha // 2 alt_menor = larg_folha tipo_menor = tipo_folha + 1 # se não cabe na folha menor if larg_retangulo > larg_menor or alt_retangulo > alt_menor: return tipo_folha else: return menor_subtipo(larg_menor, alt_menor, tipo_menor, larg_retangulo, alt_retangulo) def main(): larg_retangulo = int(input("digite a largura do retângulo: ")) alt_retangulo = int(input("digite a altura do retângulo: ")) tipo = menor_subtipo(LARGURA_A0, ALTURA_A0, 0, larg_retangulo, alt_retangulo) print(f"Utilize um papel A{tipo}") main()
Escrever algoritmos recursivos não é um aprendizado que ganhamos de graça, principalmente porque primeiro aprendemos algoritmos iterativos. Essa dificuldade inicial vale a pena porque normalmente os algoritmos recursivos que construímos são muito mais simples do que alguns algoritmos iterativos. Mais importante, talvez, é que é muito mais fácil nos convencermos de que os algoritmos recursivos estão corretos.
Como não podemos deixar de praticar, vamos resolver mais um problema.
Suponha que queremos construir nossa própria série de papeis quadrados, a série Q1, Q2, etc. Dessa vez, quanto maior o número do tipo, maior o papel. Construímos essa série assim, os papeis Q1 e Q2 são iguais e têm $1mm$ de lado. Para definir Q3, reusamos o lado de Q1 e Q2, formando um quadrado de lado $2mm$. Para construir Q4, usamos o lado de Q2 e Q3 e assim por diante, como na figura. Qual o lado do papel Q$n$?
Você consegue identificar essa série? Implemente uma função recursiva para resolver esse problema.
Pilha de chamadas
Depois que já nos acostumamos a escrever funções recursivas, podemos tentar investigar a dinâmica de execução de uma função recursiva. Quando estudamos funções, descobrimos que existe um mecanismo para executar e retornar de uma função. O mesmo mecanismo funciona para funções recursivas, não há nada de especial para elas.
Vamos simular uma chamada à primeira função fatorial definida
antes. Copiamos e adicionamos uma função main para teste.
def fatorial(n): if n == 0: resposta = 1 else: m = n - 1 solucao = fatorial(m) resposta = n * solucao return resposta def main(): resultado = fatorial(4) print(resultado) main()
A primeira instrução a ser executada nesse programa é uma chamada a
função main. Sempre que fazemos uma chamada, criamos um novo escopo
para a chamada. Logo em seguida, é feita uma chamada a fatorial(4) e
a mesma coisa acontece: criamos um novo escopo para a chamada e
associamos os parâmetros. Assim, imediatamente antes da chamada
fatorial(4) começar a executar, a memória do computador deve se
parecer com a seguinte figura.
Como nesse caso $n = 4$, é executado o ramo do else que define uma
nova variável $m = 3$ e é feita uma nova chamada fatorial(3).
Toda vez que chamamos uma função, criamos um novo escopo e
associamos os parâmetros, então não é diferente para essa.
Esse processo se repete até que $n$ seja igual a $0$, quando
chegamos a um caso básico.
No momento em que a chamada fatorial(0) retorna, o seu escopo é
destruído e o valor devolvido é guardado na variável solucao da
chamada fatorial(1). Essa chamada calcula o resultado, a execução
retorna à chamada fatorial(2) e assim ocorre sucessivamente. Por
exemplo, logo depois que a chamada fatorial(2) termina, a memória do
programa estaria assim:
Quando a última chamada termina, a execução continua na função main,
que recebe o resultado e o mostra na tela.
Entender o mecanismo que faz uma função recursiva funcionar é importante quando queremos avaliar o impacto de usar recursão ou quando queremos descobrir um erro em nosso programa. Mas quando estivermos criando um algoritmo recursivo para um problema não devemos nos preocupar com todas essas chamadas. Em outras palavras, quando estivermos pensando recursivamente, devemos nos concentrar somente no escopo da chamada inicial.
Estruturas recursivas
Algumas vezes, tratamos de objetos que têm estruturas recursivas. Essas estruturas podem representar as soluções de algum problema, ou podem ser algum objetos concretos. Por exemplo, os ramos e sub-ramos de algumas plantas podem ter a mesma estrutura que a planta inteira.
Entre as estruturas recursivas bem estudadas estão os fractais. Vamos
tentar desenhar alguns fractais usando recursão. Antes, vamos aprender
a usar um módulo de Python chamado
turtle, que foi
feito para ensinar programação para crianças. Para usar esse módulo,
você precisa ter instalado Python com o módulo de interfaces gráficas
tk.
Imagine uma grande tela de pintura e, sobre ela, uma tartaruga carregando uma caneta. Essa tartaruga é treinada e responde a alguns comandos simples, como andar por uma certa distância e virar à esquerda ou à direita por um certo número de graus. Mas não sabe fazer muito mais do que isso.
Podemos ensinar a tartaruga a desenhar um quadrado na tela. Vejamos.
from turtle import * PASSO = 100 def quadrado(): forward(PASSO) right(90) forward(PASSO) right(90) forward(PASSO) right(90) forward(PASSO) right(90) def main(): pensize(3) shapesize(2) color("green") speed(3) quadrado() done() main()
Deve ser fácil descobrir o que cada uma das instruções faz. Para ter certeza, executamos e vemos que uma janela é aberta. A tartaruga anda, vagarosamente, desenhando um quadrado verde na tela.
É importante perceber que a tartaruga está em determinada posição virada em alguma direção. Então, se pedirmos para a tartaruga desenhar dois quadrados em seguida, ela obedecerá, mas o resultado não vai ser muito mais interessante.
Então vamos prestar atenção na posição inicial e na posição final da tartaruga. Essas posições fazem parte da descrição do problema sendo resolvido pela função de desenho.
Em seguida, faremos algumas figuras mais interessantes desenhadas por Koch.
Repare que, para desenhar $K_2$, substituímos cada risco de $K_1$ por uma cópia de $K_1.$ Podemos fazer uma função que recebe um parâmetro $n = 0, 1 , 2$ e faz o desenho correspondente.
def koch(n): if n == 0: forward(PASSO) elif n == 1: forward(PASSO) left(60) forward(PASSO) right(120) forward(PASSO) left(60) forward(PASSO) elif n == 2: koch(1) left(60) koch(1) right(120) koch(1) left(60) koch(1)
Qual seria a figura correspondente à $K_3$? Ou melhor, como será a figura $K_n$, para um $n$ arbitrário? A estrutura recursiva pode ser visualizada nas figuras, mas é mais interessante que a descubramos olhando o código da função. Olhando com atenção, perceberemos que para obter uma figura $K_n$, temos que fazer quatro figuras $K_{n-1}$. Assim, podemos fazer uma implementação recursiva.
def koch(n): if n == 0: forward(PASSO) else: koch(n - 1) left(60) koch(n - 1) right(120) koch(n - 1) left(60) koch(n - 1)
Executamos koch(3) ajustando o tamanho do passo apropriadamente.
Experimente outros parâmetros. Como a figura cresce muito à medida em
que $n$ aumenta, pode ser útil aumentar a velocidade da tartaruga. A
instrução speed(10) pede para que a tartaruga ande o mais rápido
possível.
Vamos desenhar mais um fractal, chamado de triângulo de Sierpinski. A primeira imagem da sequência do fractal é um triângulo equilátero. Para obter o n-ésimo elemento da sequência, fazemos três cópias da figura anterior, uma em cada ponta de um triângulo. Veja os exemplos.
Nesse exemplo, vamos ter que tomar cuidado redobrado com as posições de início e de fim da figura. Por exemplo, suponha que para desenhar $S_3$, primeiro fazemos duas cópias de $S_2$, como na figura abaixo.
Para desenhar a terceira cópia de $S_2$, precisamos posicionar a tartaruga acima do segundo $S_2$. Como sempre que nossa tartaruga anda, ela deixa sua marca, vamos girar a cabeça da tartaruga e desenhar mais duas cópias de $S_2$ em sequência.
Nesse momento já desenhamos $S_3$, então podemos escrever a seguinte função recursiva.
def sierpinski(n): if n == 1: forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) else: sierpinski(n-1) sierpinski(n-1) left(120) sierpinski(n-1) sierpinski(n-1)
Mas essa função recursiva tem um erro crucial, você sabe identificar
qual é? Vamos testar executando sierpinski(3).
Nós não cumprimos o combinado na definição do problema! Quando fizemos uma chamada recursiva para a instância de tamanho $n-1$, supusemos que tartaruga terminaria o desenho na ponta inferior direita, mas nós não garantimos esse propriedade para a instância de tamanho $n$. Podemos entender recursão como um contrato: se exigimos alguma propriedade da solução obtida na chamada recursiva, então também nós devemos garantir essa propriedade na solução que construirmos.
Nesse exemplo, você deve se convencer de que basta repetir as instruções para que a tartaruga termine na ponta inferior direita.
def sierpinski(n): if n == 1: forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) else: sierpinski(n-1) sierpinski(n-1) left(120) sierpinski(n-1) sierpinski(n-1) left(120) sierpinski(n-1) sierpinski(n-1) left(120) sierpinski(n-1) sierpinski(n-1)
Parece um exagero termos oito chamadas recursivas, enquanto a definição do triângulo de Sierpinski fala apenas em três cópias. Mas funciona.
O que talvez seja frustrante é que o tempo que essa função leva é muito muito grande — e não podemos culpar a tartaruga por isso.
Tempo de execução e sobreposição de problemas
A razão pela qual nossa função recursão demora tanto é que ela realiza
uma série de passos desnecessários. Quando para resolver um problema
recursivamente resolvemos várias vezes uma mesma instância menor do
problema, dizemos que há sobreposição do problema. No caso da função
sierpinski, o desenho de uma chamada literalmente sobrepõe-se ao
outro.
Uma consequência é que o tempo de funções com várias chamadas
recursivas pode ser proibitivamente alto. Por exemplo, vamos executar
nosso programa que imprime a tabela de número de triângulos no castelo
de carta, mas agora queremos uma tabela com 40 linhas. Depois
de ajustar a função main, esperamos
user@notebook:~/ra123456/recursao$ python3 triangulos.py t(1) = 1 t(2) = 4 t(3) = 10 ... t(29) = 4495 t(30) = 4960 t(31) = 5456 t(32) = 5984 t(33) = 6545 t(34) = 7140 t(35) = 7770 t(36) = 8436 t(37) = 9139 t(38) = 9880 t(39) = 10660 t(40) = 11480
No meu computador isso demorou pouco menos de um minuto. A partir de
linha t(30) = 4960, já é possível contar o tempo que a função
triangulos demora para executar — o que praticamente dobra a cada
nova linha. Para entender porque essa função demora tanto, vamos fazer
um desenho que representa as chamadas da função quando a chamada
inicial é triangulos(6).
Se fizermos as contas, descobriremos que o número de chamadas cresce exponencialmente com o valor de $n$. Mas, na grande maioria das vezes, executamos a função passando os mesmos valores de entrada.
Uma maneira de evitar fazer chamadas desnecessárias é guardar os
resultados em uma tabela. Repare que se não fizermos uma chamada de
função na segunda vez em que fôssemos executar triangulos(3), então
evitaríamos também as chamadas a triangulos(2) e triangulos(1).
A estratégia de guardar o resultado das chamadas da função em uma
tabela para evitar o recálculo é chamada de memorização ou
memoização. Como os valores de entradas da função $t$ são números de
$1$ a $n$, podemos representar essa tabela usando uma lista. Para
inicializar essa lista, precisamos de uma função auxiliar, que será
a função chamada pela main. A função recursiva agora, além
da entrada do problema, receberá a tabela de valores.
def triangulos_rec(n, t): if t[n] is None: if n == 1: t[n] = 1 elif n == 2: t[n] = 4 else: t[n] = n + 2 * triangulos_rec(n - 1, t) - triangulos_rec(n - 2, t) return t[n] def triangulos(n): # cria tabela com índices de 0 a n t = [None for i in range(n + 1)] return triangulos_rec(n, t) def main(): for i in range(1, 41): print(f"t({i}) = {triangulos(i)}") main()
Na função triangulos criamos uma tabela t com $n+1$ elementos.
Inicializamos todos os valores dessa lista com None para representar
que ainda não computamos a função para um determinado índice.
Executando a versão atualizada, toda a tabela é impressa
imediatamente.
Já que, para calcular $t(n)$, precisamos preencher toda entrada da
tabela, não é necessário chamar a função triangulos para cada valor
de $i$. Modifique o programa de forma a fazer uso dessa ideia.
Comparando funções recursivas e iterativas
Já vimos implementações iterativas e recursivas da função fatorial e da função de Fibonacci. Assim, você pode se perguntar se deve usar recursão ou iteração. Como esperado, não existe resposta universal, então essa é uma pergunta que iremos nos fazer para cada problema encontrado.
Algumas vezes, pensamos primeiro em um algoritmo iterativo para o problema, particularmente quando ainda estamos começando a entender recursão. Mas, muitas vezes, é mais fácil e mais simples escrever uma função recursiva, principalmente quando o problema sendo resolvido é definido recursivamente, ou tem alguma estrutura recursiva. Também, pode acontecer de só sabermos resolver um determinado problema de maneira recursiva.
Muitas pessoas alegam que funções recursivas são mais elegantes. Por exemplo, podemos comparar duas implementações da função de Fibonacci, uma iterativa e outra recursiva.
def fibonacci(n): a = 1 b = 1 for _ in range(2, n): c = a + b a = b b = c return a def fibonacci(n): if n == 1 or n == 2: return 1 else: return fibonacci(n - 1) + fibonacci(n - 2)
Eu não sei você, mas eu acho a segunda versão muito mais bonita. Mas um algoritmo mais simples não é questão meramente cosmética. Quanto mais simples, mais fácil é entender o algoritmo e mais fácil é convencer alguém de que ele não contém erros. Ah, você testou a função iterativa acima?
O principal motivo para preferirmos uma versão iterativa quando temos uma versão recursiva mais simples é o tempo de execução. A função de Fibonacci recursiva gasta um tempo muito grande — e, de fato, sabemos que o tempo cresce exponencialmente com $n$. Podemos utilizar memorização, o que resolve grande parte da lentidão. Ainda assim, a versão iterativa será bem mais rápida por causa da sobrecarga das chamadas de função.
Tudo é uma questão de escolhas e balanceamento (ou em inglês, tradeoff). Uma estratégia é escrever uma versão recursiva sempre que for mais fácil resolver o problema assim. Se por um acaso essa função for uma função crítica para o desempenho, então tentamos reescrevê-la de maneira iterativa depois.
Funções co-recursivas
Vamos voltar ao problema do triangulo de Sierpinski. Nesse caso, tentar usar memorização não irá evitar que o tempo que a tartaruga gasta desenhando cresça rapidamente, já que o número de riscos de uma figura da sequência cresce exponencialmente. Mas podemos pelo menos tentar evitar repetir os mesmos riscos.
Repensar a nossa estratégia pode ajudar a escrever um algoritmo mais
rápido. Não vamos escrever um algoritmo iterativo; pode existir vários
algoritmos recursivos que resolvem o mesmo problema. Na função
sierpinski(n) acima, primeiro desenhamos uma cópia de $S_{n-1}$ à
esquerda, depois desenhamos uma cópia à direita.
Só depois, desenhamos a cópia de cima. O motivo por que redesenhamos $S_{n-1}$ à direita foi para que a tartaruga se deslocasse à posição de um vértice da cópia superior de $S_{n-1}$. Para melhorar, podemos primeiro desenhar o triangulo de baixo à esquerda, depois o triângulo de cima e depois o triângulo de baixo à direita.
Para isso, depois de desenhar o primeiro triângulo, precisamos que a tartaruga termine em um vértice do triângulo de cima. Uma ideia é girar a tartaruga antes de desenhar o primeiro triângulo.
def sierpinski(n): if n == 1: forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) else: left(60) sierpinski(n - 1) right(60) sierpinski(n - 1) right(60) sierpinski(n - 1) left(60)
Executando para $n = 2$.
O problema é que, embora garantimos que a tartaruga será posicionada corretamente antes e depois de cada chamada recursiva, os triângulos da esquerda e da direita estão desenhados no lado oposto ao que precisávamos. Isso sugere que precisamos tanto de uma função que desenha o triângulo de Sierpinski virado cima, quanto de uma função que o desenha virado para baixo.
Suponha que existe uma função sierpinski_baixo que desenha o
triângulo de Sierpinski virado para baixo. Então podemos escrever a
seguinte função.
def sierpinski_cima(n): if n == 1: forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) left(120) forward(PASSO) else: left(60) sierpinski_baixo(n - 1) right(60) sierpinski_cima(n - 1) right(60) sierpinski_baixo(n - 1) left(60)
Para de fato completar o programa, precisamos implementar
sierpinski_baixo. Usando uma ideia simétrica da função anterior,
não é difícil escrever o seguinte.
def sierpinski_baixo(n): if n == 1: forward(PASSO) right(120) forward(PASSO) right(120) forward(PASSO) right(120) forward(PASSO) else: right(60) sierpinski_cima(n - 1) left(60) sierpinski_baixo(n - 1) left(60) sierpinski_cima(n - 1) right(60)
Se exercutarmos agora sierpinski_cima(3), deve ser gratificante ver
como a tartaruga desenha o triângulo de Sirpinski muito mais rápido e
ordenadamente.
O curioso é que a função sierpinski_cima utiliza a função
sierpinski_baixo e a função sierpinski_baixo utiliza a função
sierpinski_cima. Esse é um tipo de recursão indireta. Chamamos essas
funções de co-recursivas. Não há nada que impeça que tenhamos mais do
que duas funções co-recursivas. Além disso, o relacionamento entre
essas chamadas pode ser tão sofisticado quanto necessário.
Algoritmos baseados em funções co-recursivas aparecem quando há dois ou mais problemas intimamente relacionados (muitas vezes, um é uma pequena modificação de outro). Eles não são tão frequentes quanto algoritmos recursivos em geral, então você não deverá escrever muitos deles. Mas há pelo menos uma aplicação em que algoritmos co-recursivos são imbatíveis: implementar um analisador sintático de um compilador.
Generalizando problemas
Considere o seguinte quebra-cabeça.
A torre de Hanói é um brinquedo com três estacas A, B e C e discos de tamanhos diferentes. O objetivo é mover todos os discos da estaca A para a estaca C respeitando as seguintes regras:
- Apenas um disco pode ser movido de cada vez.
- Um disco só pode ser colocado sobre um disco maior.
- Queremos realizar o menor número de movimentos possível.
Você talvez já tenha ouvido falar das torres de Hanoi ou talvez já tenha ate tido a oportunidade de manuseá-las. Se não, então tente resolver esse quebra-cabeça antes de continuar lendo. Você pode clicar aqui ou procurar alguma outra versão interativa na internet.
Sempre devemos prestar atenção na definição do problema que queremos resolver. Para definir um problema precisamente, precisamos descrever a entrada e a saída. Enquanto isso é claro na maioria dos exemplos que estudamos, nesse exemplo nosso objetivo é descrito apenas como “mover todos os discos da estaca A para a estaca C”. Como não temos disponível alguma máquina que mova os discos para nós, diremos que a saída do problema é uma sequência de instruções para se resolver o quebra-cabeça. Como entrada, vamos receber um número $n$, que é toda a informação de que precisamos para descrever uma instância do problema.
Como de costume, podemos esboçar o nosso programa criando um stub da função que resolve o problema e uma função principal.
def hanoi(n): """ Imprime uma sequência de instruções para mover n discos da estaca A para a estaca C com ajuda da estaca B. """ pass def main(): n = int(input("Digite o número de discos: ")) hanoi(n) main()
Veja que a documentação da função descreve o problema precisamente.
Primeiro, é sempre bom tentar resolver instâncias pequenas. Se só temos um disco, então tudo que precisamos fazer é mover um disco da estaca A para a estaca C. Se tivermos dois discos, também não é difícil se convencer de que a forma mais rápida de resolver o quebra-cabeça é movendo um disco de A para B, depois de A para C e depois de B para C.
Para encontrar um algoritmo para uma instância geral, devemos partir de uma torre inicial com $n$ discos, digamos $5$. Como temos que retirar todos os discos da estaca $A$, em particular, precisamos retirar o maior disco. A primeira regra diz que só podemos mover um disco de cada vez, então no momento em que formos mover o maior disco, todos os outro discos estarão na estaca B ou na estaca C. Mas a segunda regra diz que só podemos colocar um disco sobre um disco maior, então nesse momento todos os outros discos estarão somente na estaca B, ou somente estaca C.
Como queremos utilizar a menor quantidade de movimentos possível, o
que queremos é mover $n-1$ discos da estaca A para a estaca B usando
a estaca C como auxiliar. Essa é exatamente a descrição do problema
que estamos tentando resolver, com a exceção de que as estacas B e C
estão com papeis trocados. Por esse motivo, não podemos simplesmente
fazer uma chamada recursiva a hanoi(n-1) para resolver o
subproblema, já que isso moveria os discos para a estaca C.
Para utilizar recursão, poderíamos criar uma outra função co-recursiva que resolve esse problema um pouco diferente, como fizemos antes. Dessa vez, é mais fácil adotar uma ideia diferente e generalizar o problema. Generalizar um problema significa que aumentamos o conjunto de entradas válidas. Nesse caso, iremos fazer o seguinte.
def hanoi(n, origem, destino, auxiliar): """ Imprime uma sequência de instruções para mover n discos da estaca origem para a estaca destino com ajuda da estaca auxiliar. """ pass
A generalização é um problema novo, mas que contém o problema
original. Para resolver o problema original, podemos chamar
hanoi(n, 'A', 'C', 'B'), mas agora podemos resolver vários outros
problemas ligeiramente distintos, dependendo da escolha das estacas.
Assim, primeiro podemos mover $n-1$ discos da estaca de origem
para a estaca auxiliar.
Depois, movemos o maior disco da estaca de origem para a estaca de destino.
Finalmente, movemos $n-1$ discos da estaca auxiliar para a estaca de destino.
Agora fica fácil terminar nosso programa.
def hanoi(n, origem, destino, auxiliar): """ Imprime uma sequência de instruções para mover n discos da estaca origem para a estaca destino com ajuda da estaca auxiliar. """ if n > 0: hanoi(n - 1, origem, auxiliar, destino) print(f"Mova um disco de {origem} para {destino}") hanoi(n - 1, auxiliar, destino, origem)
Leia e releia o algoritmo com atenção. Uma pergunta que você pode se
fazer é quais são os casos básicos da função hanoi? Uma outra
pergunta é se essa função realmente realiza o menor número de
movimentos.
Divisão e conquista
Parte importante da estratégia recursiva é decompor a instância do problema em uma ou mais instâncias menores. Intuitivamente, quanto menor for a instância, mais fácil é o problema. Uma forma de recursão recorrente é a divisão e conquista. Nela, queremos dividir os dados da entrada em instâncias do problema substancialmente menores.
Por exemplo, vamos considerar o problema de multiplicar os elementos de uma lista de números. Primeiro, vamos relembrar um algoritmo iterativo.
def multiplicar(lista): produto = 1 for valor in lista: produto = produto * valor return produto
Não é muito difícil escrever um algoritmo recursivo para esse problema.
def multiplicar(lista, n): """ Devolve o produto dos n primeiros elementos de lista. """ if n == 1: return lista[0] else: return lista[n - 1] * multiplicar(lista, n - 1) def main(): lista = [1, 2, 3, 4, 5] produto = multiplicar(lista, len(lista)) print(f"O produto é {produto}") main()
Identifique o caso básico e o caso geral. Nós alteramos os parâmetros de entrada para permitir distinguir entre os subproblemas. Repare que o problema que queremos resolver é multiplicar os $n$ primeiros elementos da lista e a instância menor do problema a que reduzimos a instância original corresponde a multiplicar os $n - 1$ primeiros elementos da lista.
Para poder fazer uma chamada recursiva, basta diminuir o tamanho da instância. Enquanto a função acima cria um subproblema de tamanho uma unidade menor, poderíamos também considerar dois subproblemas, cujo tamanho de cada um corresponde a metade do tamanho da instância original.
def multiplicar(lista, inicio, fim): """ Devolve o produto dos elementos de lista[inicio:fim]. """ if inicio == fim: return lista[inicio] else: meio = (inicio + fim) // 2 return (multiplicar(lista, inicio, meio) * multiplicar(lista, meio + 1, fim)) def main(): lista = [1, 2, 3, 4, 5] produto = multiplicar(lista, 0, len(lista) - 1) print(f"O produto é {produto}") main()
Mudamos a entrada do problema para que pudéssemos representar
subproblemas mais convenientemente. Vamos chamar os parâmetros
inicio e fim de guardas da sublista.
Dessa vez, criamos subproblemas muito menores do que a instância original. Para o problema de multiplicar elementos de uma lista, ambas as funções recursivas irão executar exatamente o mesmo número de multiplicações que a função iterativa, então não há vantagem em utilizar recursão nesse caso. Mas a segunda função recursiva é um exemplo simples de como podemos resolver um problema usando divisão e conquista.
Um caso em que é vantajoso usar divisão e conquista ocorre quando não precisemos resolver um dos subproblemas. Por exemplo, se todos os números da lista são iguais a um número $b$, então o produto calculado corresponderá à potência $b^n$. Nesse caso, podemos evitar uma das chamadas recursivas, diminuindo significativamente o número de multiplicações quando comparado com o algoritmo iterativo. Esse algoritmo é chamado de algoritmo de potenciação rápida.
Em um outro exemplo, suponha que queremos encontrar um elemento em uma lista ordenada. Relembre que na busca binária, sempre dividimos essa lista em duas partes. Esse algoritmo de busca binária pode ser implementado como um algoritmo recursivo de divisão e coquista, em que cada metade da lista corresponde a um subproblema.
Implemente funções recursivas para a potenciação rápida e busca binária!
Na prática, utilizamos divisão e conquista quando for mais fácil combinar o resultado de subproblemas menores ou quando for mais rápido resolver subproblemas muito menores. Para ver isso, vamos voltar ao problema da ordenação. Vamos ver que usando divisão e conquista obtemos um algoritmo muito mais rápido do que os algoritmos de ordenação que já conhecemos.
Para podermos comparar, aqui está o algoritmo de ordenação por inserção, na versão mais rápida que conseguimos.
def insertion_sort(lista): n = len(lista) for i in range(1, n): chave = lista[i] j = i - 1 while j >= 0 and lista[j] > chave: lista[j + 1] = lista[j] j = j - 1 lista[j + 1] = chave
Primeiro, vamos criar uma lista de números razoavelmente grande. Para termos um tempo base com o que comparar, vamos executar o algoritmo de ordenação por inserção com essa lista.
def ler_arquivo(nome_arquivo): with open(nome_arquivo) as arquivo: lista = [] for linha in arquivo: numero = int(linha) lista.append(numero) return lista def guardar_arquivo(nome_arquivo, lista): with open(nome_arquivo, "w") as arquivo: for valor in lista: print(valor, file=arquivo) def main(): lista = ler_arquivo("muitos.txt") insertion_sort(lista) guardar_arquivo("muitos_ordenados.txt", lista) main()
Damos uma olhada no arquivo, contamos o número de linhas e em seguida
executamos esse programa com ajuda do comando time.
user@notebook:~/ra123456/recursao$ head muitos.txt 5164 9405 3687 8847 4689 4362 3895 6247 5601 6540 user@notebook:~/ra123456/recursao$ wc -l muitos.txt 100000 muitos.txt user@notebook:~/ra123456/recursao$ time python3 insertion_sort.py real 4m44,423s user 4m44,409s sys 0m0,040s
Vamos utilizar índices de guarda para representar as sublistas sendo ordenadas.
A animação acima sugere um algoritmo de divisão e conquista. Vamos
detalhar esse algoritmo. Primeiro, precisamos definir um caso básico.
Assim como no algoritmo multiplicar_lista, definiremos como caso
básico as instâncias do problema em que inicio == fim. Nesses casos,
a sublista contém apenas um elemento, então não há nada a ser feito.
As instâncias menores são duas, a primeira e a segunda metades da
lista. Resolvemos essas duas instâncias recursivamente e, para
combinar as soluções dos subproblemas, basta intercalar as sublistas
ordenadas.
Por causa da forma com que combinamos as soluções dos subproblemas, chamamos esse algoritmo de ordenação por intercalação ou merge sort. Podemos esboçar uma implementação.
def intercalar(lista, inicio, meio, fim): pass def merge_sort(lista, inicio, fim): if inicio < fim: meio = (inicio + fim) // 2 merge_sort(lista, inicio, meio) merge_sort(lista, meio + 1, fim) intercalar(lista, inicio, meio, fim) def main(): lista = ler_arquivo("muitos.txt") merge_sort(lista, 0, len(lista) - 1) guardar_arquivo("muitos_ordenados.txt", lista) main()
No fundo, todo o trabalho de ordenação é feito pela função
intercalar, então é importante que ela seja implementada com
cuidado. Faça isso.
Depois de já termos resolvido o problema e implementado a função
recursiva, podemos entender melhor as instruções sendo executadas
investigando as chamadas recursivas. Na etapa de divisão, cada chamada
de merge_sort realiza duas outras chamadas recursivas.
Cada retângulo da figura corresponde a uma sub-instância do problema
de ordenação a ser resolvida recursivamente. Há 19 retângulos; você
consegue dizer a ordem em que essas chamadas são realizadas? Além
disso, cada chamada que não corresponde a um caso básico realiza uma
operação de intercalação; quantas vezes a função intercalar é
chamada?
Finalmente, podemos ordenar nossa lista de números pelo algoritmo de ordenação por intercalação utilizando o programa que acabamos de implementar.
user@notebook:~/ra123456/recursao$ time python3 merge_sort.py real 0m0,453s user 0m0,445s sys 0m0,008s
Mais de 600 vezes mais rápido! Nunca nos esqueçamos da estratégia de divisão e conquista.