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
- 6
- Existem apenas cinco números na lista, o número de chamadas recursivas não será maior que o tamanho da lista.
- 5
- A chamada inicial para somalista não é uma chamada recursiva.
- 4
- A primeira chamada recursiva passa a lista [4,6,8,10], a segunda [6,8,10] e assim por diante até [10].
- 3
- Isso não seria suficiente para cobrir todos os números da lista
Q-1: Quantas chamadas recursivas são feitas ao calcular a soma da lista [2,4,6,8,10]?
- n == 0
- Embora isso funcione, há escolhas melhores e ligeiramente mais eficientes, já que fat(1) e fat(0) são os mesmos.
- n == 1
- Uma boa escolha, mas o que acontece se você chamar fat(0)?
- n >= 0
- Este caso base seria verdadeiro para todos os números maiores que zero, então o fat de qualquer número positivo seria 1.
- n <= 1
- Bom, esse caso é o mais eficiente e até mesmo evita que o seu programa falhe se você tentar calcular o fatorial de um número negativo.
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?