7.2 Cálculo Recursivo para Tamanho de Lista

Se você souber a resposta, responda-me; se não souber, faça a

mesma pergunta à pessoa à sua frente, some 1 à resposta e responda-me.

No caso do primeiro da fila, ele também vai perguntar à pessoa

da frente, mas essa pessoa não existe: é como se a pergunta retornasse zero. Nosso algoritmo poderia ser o seguinte:

Se não tem ninguém na frente:

retorne 0

senão:

retorne 1 mais a posição da pessoa à frente.

7.2 CÁLCULO RECURSIVO PARA TAMANHO

DE LISTA

Vamos usar uma lista para simular nossa fila de míopes. Não importa muito o que esta fila contenha, queremos apenas calcular seu tamanho. É claro, Python tem o método len() que fornece essa informação, mas quero mostrar como seria uma solução recursiva para este problema.

Vamos chamar esta função de tamanho(). Essa função recebe

uma lista e diz quantos elementos há nesta fila, sem usar a função len(). Da mesma forma que a fila de míopes, a função tamanho() sabe que o tamanho da lista é 1+ o tamanho da lista da qual foi retirado um elemento. Desse modo, a solução é retirar 1 elemento da lista e chamar a função tamanho com essa lista reduzida. O caso-limite será quando a lista estiver vazia. Ora, é fácil calcular o tamanho de uma lista vazia: é zero! Então a resposta vai voltando como uma cascata de respostas, cada nível acrescentando 1 ao valor obtido pela função chamada. Veja o Programa 7.1.

def tam(f):

“““Calcula tamanho da lista f.”””

if f == []:

return 0

else:

return 1 + tam(f[1:])

def main():

fila = [1, 43, 2, 3]

tamanho = tam(fila)

print(‘O tamanho da fila é’, tamanho)

main()

■ Programa 7.1: Tamanho de lista usando recursão.

Observe que são apenas duas informações: sei que uma lista vazia tem tamanho zero. Sei também que uma lista tem tamanho igual à lista imediatamente menor mais 1. Com isso resolvo o problema de calcular o tamanho da lista recursivamente.

Voltando ao algoritmo, poderíamos escrever:

Se você souber o tamanho da lista, responda-me; se não souber, pergunte o tamanho da lista imediatamente menor, some 1 e responda-me.

A execução deste programa fornece:

O tamanho da fila é 4

Esta solução oferece um roteiro para desenvolver sua própria solução recursiva de problemas:

1. Pense em como seria o problema se ele fosse um passo

mais simples. No exemplo, se meu problema é saber o tamanho de uma lista com n elementos, o caso com um passo mais simples é descobrir o tamanho de uma lista com n-1 elementos.

2. Descubra qual é a relação deste problema um passo mais

simples com o problema que você quer resolver. No caso, o problema para se resolver tem resposta que é igual a 1 mais a solução do problema com um passo mais simples.

3. Pense em qual seria o caso mais simples de todos a se

resolver, ou seja, procure entender qual seria o problema