Recursividade

Você já viu um jogo de bonecas russas? A princípio, você vê apenas uma boneca, geralmente de madeira pintada, parecida com esta:

Você pode tirar a metade de cima da primeira boneca, e o que vê dentro dela? Outra boneca, um pouco menor!

Você pode tirar essa boneca de dentro da outra e separar suas metades inferior e superior. E você verá outra boneca, ainda menor:

E de novo:

Você pode continuar fazendo isso. Eventualmente você vai encontrar uma boneca russa pequenininha. Ela é formada por uma peça única, e não se abre:

Começamos com uma boneca grande, e vimos bonecas cada vez menores, até encontrar uma tão pequena que não podia conter nenhuma outra.

O que as bonecas russas têm a ver com algoritmos? Assim como uma boneca russa tem dentro de si uma boneca menor, que tem dentro de si uma boneca ainda menor, até chegarmos a uma boneca pequena demais para ter outra dentro de si, veremos como projetar um algoritmo para solucionar um problema solucionando uma instância menor do mesmo problema, a menos que o problema seja tão pequeno que possamos resolvê-lo diretamente. We call this technique recursion.

A recursividade tem muitas, muitas aplicações. Neste módulo, veremos como usar recursividade para calcular a função fatorial, para determinar se uma palavra é um palíndromo, para calcular potências de um número, para desenhar um tipo de fractal e para solucionar o antigo problema das torres de Hanói. Nos módulos mais adiante usaremos recursividade para solucionar outros problemas, incluindo ordenação.

Este conteúdo é uma colaboração entre os professores de ciência da computação da Universidade de Dartmouth, Thomas Cormen e Devin Balkcom, juntamente com a equipe do currículo de computação da Khan Academy. O conteúdo é licenciado CC-BY-NC-SA.