Chega de historinhas, agora a coisa fica séria! Para mostrar o quão séria a coisa fica, vamos começar falando dos aspectos mais abstratos de recursão. Mas não se assuste, eles não são tão abstratos assim e são importantes para entendermos os detalhes técnicos de recursão.

Uma forma bem resumida de explicarmos recursão é dizermos que recursão é auto-referência. Recursão ocorre quando algo é definido em termos de si mesmo ou de suas variações, ou seja, recursão envolve estruturas aninhadas.

Nós humanos, por exemplo, estamos acostumados com os seguintes cenários recursivos: alguém que escreve um livro sobre escrita, uma pessoa que está assistindo a um filme que mostra outra pessoa assistindo a um filme, uma imagem que contém uma cópia de dela prória (talvez em menor escala). Este último caso é mostrado na figura abaixo, criada por Paul Noth para o The New Yorker.

Dissemos acima que recursão ocorre quando algo é definido em termos de si mesmo ou de suas variações, mas como definir algo recursivamente de forma útil e precisa? Se uma coisa é definida unicamente em termos de si própria, existe uma circularidade inerente que não nos permite concluir nada sobre o que está sendo definido. Um exemplo desse tipo de definição circular seria a seguinte:

Definição (inútil): Um procedimento recursivo é um procedimento que usa recursão.

A definição acima é um exemplo de como não fazer uma definição recursiva. Ela define um procedimento recursivo valendo-se da própria palavra sendo definida (recursão). Se o leitor não souber o que é recursão, a definição não vale de nada. E se o leitor souber o que é recursão, a definição é desnecessária.

Um outro exemplo de definição recursiva formulada de forma errada (incompleta) é a definição abaixo:

Definição (incompleta): O fatorial de um número $n$, denotado por $n!$, é calculado como a seguir:

A definição acima é incompleta porque não dos diz como calcular o fatorial de nenhum número específico. Se tentarmos aplicá-la ao cálculo do fatorial de algum número, nunca seremos capazes de parar. Continuaremos calculando indefinidamente.

Essa definição é um pouco parecida com a forma com que o gênio descreveu como construir um prédio de três andares. Ele só disse que antes seria necessário construir um prédio de dois andares. Entretanto, uma informação que falta na definição acima (quando parar de calcular), não acontece no caso do gênio, pois sabemos que só seria preciso fazer perguntas ao gênio até que ele explicasse como construir um prédio de um andar. No caso de definições recursivas, também precisamos saber quando parar.

Definições recursivas (quando propriamente formuladas) nunca definem algo unicamente em termos de si mesmas, mas sempre em termos de versões mais simples de si mesmas, até que seja possível parar, ou seja, até chegarmos a um caso tão simples que seja possível resolvê-lo muito facilmente. Um exemplo disso é a definição matemática de fatorial, agora feita de modo correto.

Definição (correta): O fatorial de um número $n$, denotado por $n!$, é calculado como a seguir:

Com a adição de mais uma regra, sabemos que, ao chegar no zero, conseguiremos calcular o fatorial e poderemos usar esse resultado no cálculo do fatorial dos demais números, até chegarmos ao fatorial do número desejado inicialmente. O procedimento não executará indefinidamente.

É importante pararmos um pouco para entendermos (em termos simples) o que a definição acima nos diz. O que ela está nos dizendo é: para calcular o fatorial de 100 (por exemplo), tudo que você precisa é saber como calcular o fatorial de 99, pegar esse resultado, e multiplicá-lo por 100. Simples assim! Aí você se pergunta: e como eu faço para calcular o fatorial de 99? É simples também: basta você calcular o fatorial de 98 e multiplicar o resultado por 99. E a coisa continua assim, até você se perguntar: como eu faço para calcular o fatorial de 0? Milagrosamente, a resposta é que o fatorial de 0 é 1. Agora, basta você pegar esse resultado e ir multiplicando…​ até chegar ao ponto em que consegue calcular o fatorial de 100.

Se seguirmos a definição recursiva dada anteriormente e o raciocínio que acabamos de explicar, teremos o cálculo abaixo do fatorial de 5:

$ \begin{equation} \begin{split} fatorial(5) & = 5 \times fatorial(4) \\ & = 5 \times (4 \times fatorial(3)) \\ & = 5 \times (4 \times (3 \times fatorial(2))) \\ & = 5 \times (4 \times (3 \times (2 \times fatorial(1)))) \\ & = 5 \times (4 \times (3 \times (2 \times (1 \times fatorial(0))))) \\ & = 5 \times (4 \times (3 \times (2 \times (1 \times 1)))) \\ & = 5 \times (4 \times (3 \times (2 \times 1))) \\ & = 5 \times (4 \times (3 \times 2)) \\ & = 5 \times (4 \times 6) \\ & = 5 \times 24 \\ & = 120 \\ \end{split} \end{equation} $

Neste momento, é importante observarmos algumas coisas sobre o cálculo de $fatorial(5)$ realizado acima:

Um benefício de conceitos recursivos é que, em geral, a implementação da definição do conceito em uma linguagem de programação é uma tarefa relativamente simples. Por exemplo, veja abaixo a implementação do cálculo do fatorial de um número. Mesmo que você não entenda alguns detalhes do código, tente ver a correspondência entre a definição recursiva do fatorial de um número e a implementação recursiva desta definição.

No código acima, foi simples traduzir para uma linguagem de programação (Python, neste caso) as duas partes da definição recursiva do fatorial de um número. É possível ler o código e identificar facilmente o que ele está fazendo. Na maioria dos casos, se um algoritmo pode ser definido de forma recursiva, a implementação do algoritmo será direta (mas nem sempre simples).

Outra vantagem de algoritmos recursivos é que eles são, em geral, fáceis de serem lidos. A correspondência entre a definição e a implementação é óbvia. Por outro lado, como veremos em breve, algoritmos recursivos não são muito eficientes em alguns casos, pois pode ser que eles realizem grandes quantidades de trabalho repetido. Nosso próximo exemplo irá ilustrar melhor essa ineficiência.

Mas antes disso, a título de curiosidade, aqui está uma possível implementação iterativa da função fatorial(n):

Definiremos agora uma sequência matemática muito famosa chamada Sequência de Fibonacci: $1, 1, 2, 3, 5, 8, 13, \dots$. Nessa sequência, os dois termos iniciais são $0$ e $1$, e cada termo subsequente é igual à soma dos dois termos anteriores. O cálculo do $n$-ésimo termo da sequência de Fibonacci pode ser definido recursivamente da seguinte forma:

Definição: O $n$-ésimo termo da sequência de Fibonacci, denotado por $F_{n}$, pode ser calculado assim:

A partir da definição acima, podemos implementar o cálculo do $n$-ésimo termo da sequência assim:

Novamente, note a correspondência direta entre a definição e sua implementação. Entretanto, a implementação acima é ineficiente porque ela faz uma grande quantidade de trabalho repetido. Para ilustrar isso, veja a figura abaixo, ilustrando o cálculo de fib(5), que mostra as muitas chamadas repetidas da função fib, que, por questões de espaço, escrevemos simplesmente como f.

Apesar de a função fib possuir alguma semelhança em sua estrutura com a função fatorial, a complexidade da função fib é muito maior. Sua complexidade é $O(2^n)$. Isso ocorre por causa da quantidade de chamadas repetidas (desnecessárias) à função fib.

A título de curiosidade, existem formas mais eficientes de implementarmos a função fib, sem usar recursão, e sem fazer chamadas desnecessárias, como a seguinte:

A função acima calcula o $n$-ésimo termo da série de Fibonacci com complexidade $O(n)$.

Pelos exemplos de funções recursivas (e suas respectivas versões iterativas) que mostramos até agora, você pode estar pensando que recursão não é um recurso tão vantajoso assim. Afinal, a versão iterativa das funções que mostramos não é muito mais complicada que a versão recursiva correspondente, e a versão iterativa é mais eficiente em ambos os casos.

Na prática, a versão iterativa de um algoritmo tende a ser mais eficiente que a versão recursiva. Entretanto, em alguns casos a versão iterativa é tão mais complicada que acaba sendo mais vantajoso usar a versão recursiva (por questões de legibilidade e facilidade de manutenção) do que a versão iterativa. Em outros casos (como o nosso próximo exemplo), a própria natureza recursiva do problema e a elevada complexidade computacional inerente a ele (uma solução iterativa não traria ganho significativo de desempenho) fazem com que recursão seja a melhor escolha.

Um dos exemplos mais famosos de recursão é o problema conhecido como Torres de Hanoi, supostamente formulado no século XIX pelo matemático Francês Edouard Lucas. Esse problema também é conhecido como problemas das Torres de Lucas (em homenagem ao autor do problema), ou problema das Torres de Brahma (certamente não em homenagem à marca de cerveja). A lenda associada a esse problema é a seguinte.

No templo de Brahma em Benares, debaixo do domo que marca o centro do mundo, existem 64 discos de ouro puro que os monges carregam, um de cada vez, para três agulhas de diamante. Eles fazem isso em obediência à ordenança imutável do deus Brahma, segundo a qual nenhum disco pode ser colocado em cima de um disco menor que ele.

Segundo essa lenda, no começo do mundo, os 64 discos formavam uma torre (empilhados do maior para o menor) em uma das agulhas de diamante. O deus Brahma então ordenou aos monges que transferissem a torre de discos de uma agulha para outra, movendo um disco de cada vez e usando como "agulha auxiliar" a terceira agulha, e lhes disse que quando eles terminarem essa tarefa, chegará o fim do mundo.

Nesse momento, além dos questionamentos sobre os aspectos místicos da história, você pode estar se perguntando: O quê esse problema tem a ver com recursão? Por quê 64 discos? Por quê eles ainda não terminaram essa tarefa aparentemente simples?

Vamos examinar cada uma das perguntas acima.

A recursão aparece no problema se considermos que para mover 64 discos de uma agulha para a outra (usando uma outra agulha como auxiliar), basta saber como transferir 63 discos de uma agulha para a outra. Nesse momento, você, ainda descrente a respeito do funcionamento de recursão, pode estar rindo e pensando "é fácil assumir magicamente que se sabe como transferir os 63 discos de uma torre para a outra!" Mas, assim como no caso do fatorial, para mover 63 discos, precisamos somente saber mover 62 discos, e para mover 62 discos, precisamos somente saber como mover 61. Bom, nesse ponto você já deve antecipar aonde isso vai parar…​

Para resolver o problema das torres de Hanoi com $n$ discos, são necessários $2^n - 1$ movimentos, o que é deveras custoso computacionalmente. Isso nos leva à resposta da segunda pergunta que fizemos acima: por quê 64 discos? O deus Brahma quis ser generoso com o mundo e dar à humanidade tempo o bastante para se desenvolver.

Como os monges têm que mover 64 discos de uma torre para outra, usando uma terceira como auxiliar, e assumindo que cada movimento seja completado em 1 segundo, eles demorarão aproximadamente 584.942.417.355 anos, ou seja, 584 trilhões de anos para completar a tarefa. Estima-se que a Terra tenha menos de 5 bilhões de anos de idade, o que nos leva a crer que ainda tempos bastante tempo pela frente antes que os monges completem a tarefa e venha o fim do mundo.

A essa altura do campeonato, os monges já devem estar bastante cansados de executar essa entediante tarefa. Nós, como pessoas de bom coração, vamos construir um programa que imprime a sequência de movimentos necessários para resolver o problema. Depois disso, podemos enviar essa sequência a eles, que comprarão um robô avançadíssimo capaz de ler as sequências e mover os discos corretamente, poupando-os dessa tarefa chata. Mas espera, se fizermos isso, o mundo pode acabar antes do que acabaria? É isso mesmo que queremos? Bom, vamos construir o programa de decidimos isso depois.

A função acima pode ser invocada assim: