Para Entender Recursão

Intro

Na computação existe um ditado que diz que para entender recursão primeiro você precisa entender recursão! Uma das grandes dificuldades de estudantes de programação, a recursão é um recurso poderoso que vai te ajudar a ser um programador melhor. Minha intenção aqui, portanto, é mostrar os principais conceitos da recursividade e como aplicá-los no dia-a-dia.

Drawing hands

O quadro acima foi criado pelo artista holandês Maurits Cornelis Escher(1972) que se interessava por representar construções impossíveis, como na figura abaixo, mas também se interessava por padrões geométricos e o infinito.

Relativity

A Recursão acontece quando algum objeto/tipo/coisa é definida em termos dela própria. Quando estamos falando de programação, a recursividade aparece na definição de funções, na qual um dos passos desse algoritmo envolve a chamada da própria função e aparece também na definição de estruturas de dados (Listas e Árvores por ex.). Nesse post eu vou me ater apenas às funções recursivas, deixando a parte de estruturas para uma próxima conversa. Vale ressaltar que as funções recursivas são equivalentes aos laços de repetição (for e while por ex.).

Recursão

Motivação

Imagine que você precisa implementar uma função de potenciação onde:

power(x,n) = xⁿ

Vamos resolver esse problema inicialmente de forma iterativa como estamos acostumados.

def power(x, n):
    res = 1
    if n != 0:
        for i in range(n):
            res = res * x
    return res

A ideia desse programa é que devemos multiplicar x por ele mesmo n vezes. Começamos com o valor 1 na variável res (neutro da multiplicação) e vamos acumulando a multiplicação de x na mesma. Vamos testar nossa função:

> power(2,5)
32
> power(10,0)
1

Aparentemente nossa função está funcionando corretamente. Porém se nós prestarmos bastante atenção ao procedimento de potenciação, veremos que existe uma estrutura recursiva que grita nas nossas caras, vejamos:

Power(x, n) = x * Power(x, n-1)

Ex1.: 2^3 = 2 * 2^2
          = 2 * 2 * 2^1
          = 2 * 2 * 2 * 2^0
          = 2 * 2 * 2 * 1
          = 2 * 2 * 2
          = 2 * 4
          = 8

Da mesma forma:
Power(2, 3) = 2 * Power(2, 2)
            = 2 * 2 * Power(2,1)
            = 2 * 2 * 2 * Power(2,0)
            = 2 * 2 * 2 * 1
            = 2 * 2 * 2
            = 2 * 4
            = 8

Quais os aspectos mais importantes que devemos destacar nesse exemplo?

O procedimento é executado em termos dele próprio: xⁿ = x * x^n-1
A existência de um caso base, que define quando o procedimento deve terminar.

O caso base é fundamental para a construção de qualquer algoritmo recursivo, pois ele é o responsável por terminar a execução do procedimento, evitando-se assim loops infinitos.

Vamos então definir a mesma função de forma recursiva utilizando a definição acima?

Definição formal: power(x,n) = 1,                 se n = 0
                  power(x,n) = x * power(x, n-1), caso contrário

def power_rec(x, n):
   if (n == 0):
       return 1
   else:
       return x * power_rec(x, n-1)

Podemos ver que nossa função recursiva é praticamente a tradução literal da definição formal. Esse procedimento deve executar da mesma forma que o Exemplo 1. O caso base é testado inicialmente na linha 2 e a chamada recursiva aparece na linha 5. Perceba que no exemplo acima nenhum tipo de laço explícito foi utilizado (for ou while). A recursão, neste caso, faz as vezes dos laços de repetição.

Outro exemplo bem comum que vemos nos cursos de programação é o cálculo de fatorial de um número. Por ex.: 5! = 5 * 4 * 3 * 2 * 1 = 120. Podemos perceber as duas estruturas necessárias para construirmos um algoritmo recursivo:

Caso base: n = 1 ou n=0, nesse caso tanto faz.
Passo recursivo: fat(n) = n * fat(n-1)

Vamos expandir a seguinte chamada:

fat(n) = 1, se n = 0
       = n * fat(n-1), caso contrário

fat(5) = 5 * fat(4)
       = 5 * 4 * fat(3)
       = 5 * 4 * 3 * fat(2)
       = 5 * 4 * 3 * 2 * fat(1)
       = 5 * 4 * 3 * 2 * 1 * fat(0)
       = 5 * 4 * 3 * 2 * 1 * 1
       = 5 * 4 * 3 * 2 * 1
       = 5 * 4 * 3 * 2
       = 5 * 4 * 6
       = 5 * 24
       = 120

A tradução da definição formal para a função recursiva é bem direta:

def fat_rec(n):
    if (n==0):
        return 1
    else:
        return n * fat_rec(n-1)

Basicamente é isso, no if, temos o caso base ou condição de parada e no else temos a chamada recursiva. Outro ponto importante a se notar nos exemplos é que as chamadas recursivas se parecem muito com uma pilha (de fato elas formam pilhas de chamadas) e que isso pode causar problemas caso a profundidade dessa pilha seja muito grande. Quem nunca aí recebeu um StackOverflow por conta de chamadas recursivas muito profundas ou infinitas?

StackOverflowError - por quê ?

Como foi mostrado nos exemplos, as funções recursivas acabam criando uma pilha de chamadas de procedimento que as tornam inviáveis para tratarmos problemas grandes. Mas a pergunta que fica é: por que isso acontece ? Internamente, os interpretadores de linguagem mantém uma estrutura de dados chamada pilha de chamadas que nada mais é do que uma pilha que guarda as informações sobre as chamadas de procedimento em um programa. A cada chamada de procedimento, um novo Frame é adicionado a esta pilha. O frame nada mais é uma estrutura que guarda as informações sobre a chamada como por ex. a função que será executada, seus parâmetros, variáveis locais e endereço de retorno. Geralmente essa pilha possui um tamanho limitado e não permite que façamos chamadas recursivas muito profundas.

A solução para esse problema existe e se chama Tail call optimization, que é uma otimização que permite fazermos chamadas recursivas sem criar novos stack frames. Para isso, como o nome sugere, precisamos modificar nossas funções para que as chamadas recursivas sejam as últimas coisas a serem executadas na nossa função, por isso o nome Otimização de Calda. No exemplo do Power, se você notar, o ultimo procedimento que é executado dentro da função é a multiplicação de n pela chamada recursiva de n-1. Precisamos, portanto, modificar nossas funções da seguinte maneira:

Ao invés de guardarmos os resultados pendentes na pilha de chamadas, nós utilizaremos um argumento extra nas nossas funções que vai guardar os resultados parciais das chamadas. Dessa forma, a nossa função de Power que era assim:

1 def power_rec(x, n):
2     if (n == 0):
3         return 1
4     else:
5         return x * power_rec(x, n-1)

Vai ter a seguinte cara:

def power_tco(x, n, acc): # note o parâmetro a mais chamado acc pois é nele que o resultado será armazenado
    if (n == 0):
        return acc
    else:
        return power_tco(x, n-1, acc*x) # perceba que aqui eu estou calculando o valor e armazenando na variável acc


A chamada fica assim:

> power_tco(2, 5, 1) = power_tco(2, 5, 1*2) # acc = 2
                     = power_tco(2, 4, 2*2) # acc = 4
                     = power_tco(2, 3, 4*2) # acc = 8
                     = power_tco(2, 2, 8*2) # acc = 16
                     = power_tco(2, 1, 16*2) # acc = 32
                     = power_tco(2, 0, 32)  # aqui atingimos o caso base e acc é retornado com o valor 32
                     = 32

Basicamente estamos iterando sobre o valor de n e guardando os valores intermerdiários na variável acc. Algumas linguagens conseguem otimizar esse tipo de chamada evitando a criação de novos frames, uma vez que nossa função não precisa mais “esperar” o resultado das chamadas recursivas, ou seja, o nosso resultado não depende de chamadas que serão empilhadas na stack frame.

Da mesma forma faremos com nossa função de fatorial:

def fat(n):
    if n<2:
        return 1
    else:
        return n * fat(n-1)

Vamos transformar essa função em *tail call*:

def fatco(n, acc):
    if n < 2:
        return acc
    else:
        return fatco(n-1, acc*n)  # aqui a chamada recursiva está na calda e não a multiplicação, como no caso anterior.

> fatco(5, 1) = fat(5, 1)
              = fat(4, 5)
              = fat(3, 20)
              = fat(2, 60)
              = fat(1, 120)
              = 120