Actualmente são muitas as linguagens de programação ao dispor dos programadores e curiosos pela “arte” de programar. O desenvolvimento de aplicações está hoje em dia direcionado para a Web e para os dispositivos móveis mas há ainda muito a fazer no que diz respeito à integração de sistemas. Depois de iniciarmos a nossa rubrica sobre a linguagem de programação Python, hoje iremos começar a explicar alguns elementos/sintaxe que fazem parte desta.
Na rubrica de hoje: Funções recursivas
. 
Em muitas línguas de programação existe a possibilidade de uma função na sua execução se chamar a ela mesma para alguma coisa. Este facto embora pareça circular, não o é e é muito útil nos mais diversos casos de programação.
Comecemos por pensar no seguinte problema, muito conhecido na introdução à recursividade:
“Defina uma função que calcule o factorial de um número n inteiro. O factorial de um número é o produto desse número por todos os números inteiro positivos inferiores.”
Ou seja 5! (lê-se 5 factorial) é igual a 5*4*3*2*1=120
Existe obviamente uma forma não recursiva de resolver este problema:
def fatorial(n):
"""Esta função calcula o fatorial de um número. n é um inteiro."""
count=n
result=1
while count>1:
result*=count
count-=1
return result
Mas pensando de outra forma, o factorial de um número n é sempre o produto de n por n-1 até que n seja 1.
Isto leva-nos a pensar na sintaxe básica da recursividade:
- Existe sempre um caso limite, onde a partir do qual não faz sentido ir mais “fundo” na recursividade.
- A função chama-se a ela própria enquanto não se atingir o caso limite.
Então a resposta recursiva (uma possível) para o nosso problema é:
def rec_fatorial(k):
"""Calcula o fatorial de um número k de forma recursiva"""
if k==0 or k==1: return 1 #Caso limite
else: return k * rec_fatorial(k-1) #A função chama-se a si própria!?
Como se pode ver, esta função tem uma sintaxe muito mais curta e tem menos operações do que a resolução anterior. Enquanto a resolução anterior obrigava a muitas variáveis intermédias, este método é mais “leve” (até certo ponto) para o computador.
Agora um problema mais complexo:
Escreva uma função flatten(a) que retorne uma lista simples com todos os valor existentes na lista imbricada a.
Exemplos:
>>>flatten([])
>>>flatten([[9, [7, 1, 13, 2], 8], [7, 6]])
>>>flatten([[’this’, [’a’, [’thing’], ’a’], ’is’], [’a’, ’easy’]])
Deverão retornar respectivamente:
[]
[9, 7, 1, 13, 2, 8, 7, 6]
[’this’, ’a’, ’thing’, ’a’, ’is’, ’a’, ’easy’]
Como se pode ver, estamos perante um problema muito mais complexo. A resposta pode ser encontrada no seguinte código.
def flatten(a):
"""Função que tranforma listas imbricadas numa lista simples"""
if a==[]: #Um caso limite: a lista vazia
return []
elif type(a) != list: #Mais um caso limite: o argumento já não é uma lista
return [a]
else:
c = flatten(a[0])
b = flatten(a[1:])
c.extend(b) #Método proprio de listas
return c
Este código, bastante mais complexo demonstra a capacidade das funções recursivas. Desta forma qualquer que seja a profundidade de imbricação das listas, o código funciona sempre.