4.4. As Três Leis da Recursão¶
Como os robôs de Asimov, todos os algoritmos recursivos devem obedecer três leis importantes:
Um algoritmo recursivo deve possuir um caso base (base case).
Um algoritmo recursivo deve modificar o seu estado e se aproximar do caso base.
Um algoritmo recursivo deve chamar a si mesmo, recursivamente.
Vamos olhar para cada uma dessas leis em detalhes e ver como foi
usado no algoritmo somalista. Primeiro, um caso base é a condição
que permite que o algoritmo termine a recursão. Um caso base é tipicamente um
problema que é pequeno o suficiente para ser resolvido diretamente.
No algoritmo somalista o caso base é uma lista de comprimento 1.
Para obedecer a segunda lei, devemos providenciar uma mudança de estado que mova
o algoritmo em direção ao caso base. Uma mudança de estado significa que parte
dos dados que o algoritmo está usando são modificados. Geralmente os dados que
representam nosso problema ficam menores de alguma forma. No algoritmo somalista
nossa estrutura de dados primária é uma lista, por isso devemos focar nossos
esforços de mudança de estado na lista. Como o caso base é uma lista de
comprimento 1, uma progressão natural em direção ao caso base é encurtar a
lista. Isto é exatamente o que acontece na linha 5 do ActiveCode 2
quando chamamos somalista com uma lista menor.
A última lei é que o algoritmo deve chamar a si mesmo. Esta é a própria definição de recursão. A recursão é um conceito confuso para muitos programadores iniciantes. Como um programador novato, você aprendeu que funções são boas porque permitem você pode pegar um problema grande e quebrá-lo em problemas menores. Os problemas menores podem ser resolvidos escrevendo uma função para resolver cada problema. Quando falamos de recursão, parece que estamos falando em círculos. Nós temos um problema para resolver com uma função, mas essa função resolve o problema chamando a si mesma! Mas a lógica não é circular de forma alguma; a lógica da recursão é uma expressão elegante de resolver um problema, dividindo-o em problemas menores e mais fáceis.
No restante deste capítulo, veremos mais exemplos de recursão. Em cada caso, vamos nos concentrar em projetar uma solução para um problema usando as três leis da recursão.
Auto Avaliação
Q-1: Quantas chamadas recursivas são feitas ao calcular a soma da lista [2,4,6,8,10]?
Q-2: Suponha que você vai escrever uma função recursiva para calcular o fatorial de um número. fat(n) retorna n * n-1 * n-2 * …. onde o fatorial de zero é definido como 1. Qual seria o caso base mais apropriado?