Recursão

Nota: Isto é um tópico que se pode considerar relativamente avançado. Para a maioria das aplicações não precisas de saber nada a relativamente a recursão. Ocasionalmente no entanto pode te ser tão útil que se irá tornar indispensável. Por isso a apresento aqui em estudo. Mas não entres em pânico em caso que isto não faça sentido de imediato.

O que é?

Apesar que te tinha dito anteriormente, sobre os loops serem fundamentais na construção dos programas, a realidade é que se pode fazer um programa inteiro sem uma única construção de loop. Isto é tão verdade que algumas linguagens chegam mesmo a não ter statments de loops como of FOR, WHILE, linguagens como o Lisp. Em vez disso é utilizado uma técnica conhecida como recursão. Que é uma excelente técnica para resolver determinado tipos de problema. Então, vamos lá ver do que isto tudo se trata.

Recursão é uma técnica que consiste simplesmente em aplicar uma função como parte da definição dessa mesma função. Como exemplo dessa definição temos o nome GNU (a fonte de muito software livre), é dito que este nome é recursivo porque GNU, significa GNU Not Unix. tornando o GNU parte da definição do próprio GNU!

Mas a chave do funcionamento da recursão é que tem de existir uma condição que termine, por forma a que a função execute uma outra tarefa, não recursiva (o exemplo do GNU, já não satisfaz este parâmetro, porque cai num loop infinito).

Vamos olhar para um exemplo simples. A função factorial matemática, é definida como sendo o produto de todos os números até e incluindo um determinado argumento, ou seja o factorial de 1 é 1, continuando o mesmo raciocínio, vemos que uma outra forma de apresentar este raciocínio é dizendo que o factorial de N é igual à N vezes o factorial de (N-1).

Então:
1! = 1
2! = 1 x 2 = 2
3! = 1 x 2 x 3 = 2! x 3 = 6
N! = 1 x 2 x 3 x .... (N-2) x (N-1) x N = (N-1)! x N

Isto pode ser expresso no Python da seguinte maneira:

def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n-1)

Escrever este exercício aqui explicado exige um pouco mais de código. Irias precisar de criar uma lista de todos os números de 1 a N e depois multiplicar o total corrente pelo próximo item. Experimenta isso como um exercício e depois compara os resultados com a função descrita acima.

Recursão em listas

Uma outra área onde a recursão é muito útil e quando estamos a processar as listas. Desde que possamos testar se uma lista contém elementos ou não, e criar um código baseado na lista menos o sue primeiro elemento, aí podemos utilizar a recursão de uma maneira muito simples.

Considera este exemplo simples de imprimir todos os elementos de uma lista, para isso criamos uma função chamada printList:

def printList(L):
    if L:
        print L[0]
        # for [1:] - vai ver a documentação do Python como é que o 'slicing' funciona
        printList(L[1:])

Se L for verdadeiro - ou seja a lista não esta vazia - imprimimos o primeiro elemento da lista e depois processamos o resto.

Para uma lista tão simples como esta, é algo trivial usar um loop tão simples como este. Mas pensa no que acontece se a lista é algo mais complexo e contém outras listas dentro dela. Para isso podemos testa se existe algo dentro do da lista, depois podemos usar o printList() de uma forma recursiva. Em caso que isso não seja possível, nós então por e simplesmente imprimimos a lista. Visto a teoria, vamos testa-la, para ver se funciona:

def printList(L):
    # se a lista estiver vazia não acontece nada
    if not L: return
    # se não estiver vazia chama o printList para o primeiro elemento da lista
    if type(L[0]) == type([]):
        printList(L[0])
    else:  
        print L[0] 
    # agora processa o resto da L 
    printList(L[1:])

Agora caso tentes criar estes exemplos usando os loops convencionais, irás achar esta uma tarefa muito ingrata. A recursão torna uma tarefa relativamente complexa, em algo muito mais simples.

Mas existe um pequeno problema (é claro, não há bela sem senão). A recursão quando usada para processar grandes quantidades de dados tende a comer muita memória. Moral da história, em caso que estejas com pouca memória e tens muitos dados para processar, estarás melhor usando um código mais convencional.

OK, agora vamos dar um outro salto para o desconhecido, e começar a falar de programação orientada a objectos.