Algoritmo - Recursividade

A recursividade permite modelar algoritmos de modo a alcançar a solução através da definição do problema em termos de si mesmo. Em outras palavras, podemos construir um algoritmo, tendo em vista que sua resolução é composta de chamadas a suas instruções até que uma condição de parada seja atendida; de natureza recursiva, a fim de facilitar a confecção do mesmo, pois se torna fácil pensar na solução do problema dessa maneira. A idéia chave por trás dos algoritmos recursivos, consiste em dividir o problema em partes menores até que uma de suas partes seja resolvida diretamente, sem uma chamada ao próprio código, sendo esta ultima execução direta denominada condição de parada.

Para identificarmos um algoritmo que pode ser escrito recursivamente, basta atentar-se ao comportamento que o problema descreve. Por exemplo, o comportamento de um fatorial é recursivo, porque a completa solução do calculo é definida em termos de si mesma:

Veja o exemplo:
fatorial de 3!

fatorial(3) = 3 x fatorial(2)
3 x 2
fatorial(2) = 2 x fatorial(1)
2 x 1
fatorial(1) = 1 x fatorial(0)
1 x 1
fatorial(0) = 1

Assim, para encontrar o valor de 3! o algoritmo acima descreveu os seguintes passos: a execução se inicia por 3!, prosseguindo pelas etapas intermediarias 3 x 2!, 2 x 1!, 1 x 0! até que a condição de parada 0! = 1 seja atingida. É importante frisar que a definição do problema de um fatorial envolve um caso de parada, o qual consiste em que 0! = 1, assim sendo, nosso algoritmo chama a si mesmo ate encontrar o tempo certo de interromper sua execução e obter a solução desejada.

Para ilustrar melhor como um algoritmo recursivo trabalha, segue o pseudocodigo para o calculo de um fatorial:

procedimento fatorial(n: inteiro)
Inicio

se ( n=0 ) entao
retorne 1; { por definicao fatorial de 0! = 1 }

senao
retorne n*fatorial(n-1);

Fim
fim-procedimento

fatorial(3); { chamada externa ao procedimento, realiza os passos descritos anteriormente }

O procedimento recebe como argumento um numero inteiro para o calculo do fatorial. A primeira execução entra no senão da estrutura condicional, e segue assim até que a condição de parada n = 0 seja atingida. Para auferir o resultado, os computadores usam uma pilha de execução, a qual armazena os valores previamente calculados, e ao fim da execução ( condição de parada ), desempilha os valores e retorna o resultado à função chamadora.

Vale salientar que qualquer algoritmo escrito recursivamente pode ser escrito iterativamente, isto é, usando as estruturas de repetição enquanto e para, mas a elaboração do algoritmo pode se tornar mais complexa.