2. Recursão na Programação de Computadores

Durante esta aula, veremos que a recursão pode ser usada na implementação de diversas funções e procedimentos. Vamos ver como aplicamos esse conceito? Observe o seguinte programa:

No programa mostrado, temos a definição de uma função de nome funcaoX(). No corpo dessa funcaoX() temos uma chamada para a própria funcaoX() o que torna ela uma função recursiva. Porém, se percebe que essa função nunca irá retornar nada, pois sempre é chamada novamente antes do retorno. Temos então um caso de uma recursão infinita, como aquela do espelho. Entenda o que está acontecendo: quando a rotina main chama a funcaoX(), o corpo dessa função chama novamente a própria funcaoX(). Essa segunda execução da funcaoX() irá chamar uma terceira execução da funcaoX() e assim por diante.

Rodar um programa como o ProgramaRecursaoInfinita irá implicar no encerramento do seu programa por falta de memória. Isso porque toda vez que uma função ou procedimento é chamado, um espaço na memória é alocado para armazenar informações, como os valores das variáveis locais etc. Em uma recursão infinita você chama a própria função quantas vezes? Infinitas vezes, certo? Como a memória é finita, chegará um momento que não haverá mais memória para ser alocada e o programa será interrompido pelo sistema operacional do computador.

Muito bem, essa é a forma errada de se usar recursão em programação. O problema do ProgramaRecursaoInfinita é que a recursão implementada nele nunca para e toda função ou procedimento recursivo uma hora tem que parar. Para que isso aconteça, você geralmente vai precisar fazer um teste dentro da rotina recursiva.

Mas vejamos um exemplo prático de função que é melhor implementada através de recursão. O fatorial de um número natural n é uma função matemática representada pela notação n! e é calculado pelo produto de todos os números inteiros positivos menores ou iguais a n. Na notação matemática, temos o fatorial definido por:

Veja como esse valor é calculado no caso do fatorial de 5:

Um caso especial é o do número 0 (zero):

O fatorial não é calculado para números negativos, os quais não fazem parte dos números naturais. Sabendo disso, como você poderia implementar um programa para calcular o fatorial de um número? Veja uma possível implementação a seguir.

Na rotina main do ProgramaFatorialIterativo, é lido um número (variável numero) e é declarada e utilizada a função fatorial() para se calcular o fatorial desse número digitado. A função fatorial() é organizada através de um comando de seleção if. Isso porque existem três casos que precisam ser verificados. O primeiro é se o número passado como parâmetro é negativo (numero < 0). Se for o caso, a função está retornando o valor -1 para indicar o erro. Na disciplina de Programação Orientada a Objetos, você verá como tratar melhor esses casos de erro através do uso de exceções.

O segundo caso verificado é o do número digitado ser igual a 0 (numero == 0). Nessa situação, a função não precisa calcular nada, apenas retornar o valor 1, que por definição é o valor fatorial de zero. Já o último caso é aquele em que se calcula realmente o fatorial de acordo com a equação matemática mostrada para o fatorial. Veja que utilizamos o comando de iteração for para realizar a multiplicação do cálculo do fatorial:

Dado que o valor da variável fat é igual a 1 e que a variável i que indexa o laço é inicializada com o valor 2, está se fazendo um laço que, enquanto i não for maior que o número digitado, se atualiza o valor de fat multiplicando seu valor por i. Por exemplo, para o fatorial de 5, teremos o cálculo ilustrado no quadro a seguir, no qual temos a inicialização da variável fat com o valor 1, e depois uma sequência de laços multiplicando o valor da variável fat pelos números de 2 (valor inicial de i) a 5 (valor final de i).

Pois bem, essa forma de implementação do fatorial é válida, porém, não é a mais simples e natural possível. Para você entender isso, observe que o fatorial pode ser definido facilmente através das seguintes fórmulas:

Você notou alguma coisa especial nessa fórmula de cálculo para o fatorial de n? Ela possui uma definição recursiva! Observe que o fatorial de n é definido em termos do fatorial de n - 1. Baseado nessa nova definição, o fatorial pode ser calculado da forma mostrada a seguir. Note que para calcular o fatorial de 5, precisamos calcular o fatorial de (5 – 1), ou seja, o fatorial de 4, cujo valor depende do valor do fatorial de 3, e assim por diante, até chegarmos ao fatorial de 0, que já é definido como 1, como vimos na equação 3. Esse valor definido é o que faz a função fatorial ter um fim e é conhecido como caso base.

Quando a solução do problema a ser resolvido pode ser apresentada de forma recursiva, isso indica que sua implementação via recursão é mais simples e mais apropriada. Veja a seguir a implementação do mesmo programa, porém agora implementando a função fatorial através de recursão.

Note que o que muda é apenas o código da função fatorial. Nesse código, existe a mesma estrutura de if/else que existe na versão iterativa da solução (uso do for). Entretanto, o corpo do último else – onde se calcula o valor do fatorial de números maiores que zero – foi simplificado. Isso não só reduz a quantidade de linhas de código do programa, mas também facilita a leitura e o entendimento do código por outras pessoas.