Vamos começar a programar em Python? (Parte VII)

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:

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.