Recursividade

Recursão é o principio de que algo pode ser definido em termos de pedaços menores de si mesmo, na computação a recursividade é alcançada através do uso de funções recursivas, uma função recursiva realiza uma chamada de função para si mesma, aonde cada chamada trabalha de forma a refinar as sucessivas entradas  aproximando-o ao resultado final da solução.

Este estilo de desenvolvimento pode causar algum desconforto ao apresentar a resposta de um problema maior com uma rotina que chama a si própria, do que dividir o problema em vários pedaços e escrever as respectivas funções separadas, leva um tempo para acostumar-se a este estilo de programação.

Para começar, considere um problema simples como calcular o fatorial de um numero n, o fatorial de n, escrito n! é o produto de todos os números inteiros que precedem n até 1, por exemplo, 5! = 5 * 4 * 3 * 2 * 1, com a formula sendo:

n! = (n) (n – 1) (n – 2) ... (1)

Entretanto a expressão resultou de um processo iterativo,  aonde se subtrai um valor cada vez maior de n até alcançar 1. Buscar a resposta  de forma recursiva envolve encontrar o  padrão de recorrência, considere que os passos para n! aonde n será multiplicado pelo fatorial (n-1)!, com  n’ = n-1  resultando em  (n’)(n’-1)! e assim sucessivamente ao qual podemos definir formalmente como:

Descrevendo passo a passo o processo iterativo e recursivo temos:

ITERAÇÃO		RECURSÃO
5* (5-1)!		5* (5-1)!
5*4* (5-2)!		5*4* (4-1)!
5*4*3* (5-3)!		5*4*3* (3-1)!
5*4*3*2* (5-4)!		5*4*3*2* (2-1)!
5*4*3*2*1		5*4*3*2*1

Para ilustrar a computação de 5! usando a abordagem recursiva como descrita, visualiza-se o processo em duas partes, a primeira parte consiste em empilhar chamadas de rotinas sucessivamente até o ponto de encontrar a condição de termino, a condição de termino é o momento em que a rotina recursiva deixa de chamar a si mesma e retorna um valor, iniciando assim a segunda parte do processo ao desempilhar todas as chamadas de funções que retornam em ordem reversa, esta fase termina quando encontrar a chamada original, completando o processo recursivo.

F(5) =	5*F(4)
	F(4) =	4*F(3)
		F(3) =	3*F(2)
			F(2) =	2*F(1)
				F(1) =	1	CONDIÇÃO DE TERMINO
			F(2)=	2*1
		F(3) =	3*2
	F(4) =	4*6
F(5) =	5*24						1ª PARTE
120							2ª PARTE

Para montar a função C de fatorial, terá como entrada o numero positivo n para calcular o fatorial recursivamente, sendo a entrada menor ou igual a 1, isto é 0 e 1, retornamos 1, pois 0! e 1! são ambos definidos como 1, servindo assim como a condição de termino, do contrario a função retorna o resultado de n vezes o fatorial de n-1, como mostrado no detalhamento para o calculo de fatorial de 5.

#include <stdio.h> unsigned int fact(unsigned int n) {       if (n > 1) {             return( n * fact(n-1) );       }       else {             return 1;       } } void main(void) {       unsigned int i;       i = fact(5);       printf("5! = %u\n", i); }

Analisando a maneira que as funções são executadas em C, precisa compreender como um programa fica organizado na memória,  fundamentalmente um programa consiste em 4 áreas:

1)      Código: instruções de maquina que são executadas no programa

2)      Dados estáticos: informações que se mantém durante todo o programa, como variável global e estática.

3)      Heap: espaço para armazenamento dinâmico, como a memória reservada para rotinas como alloc.

4)      Pilha: armazena as informações das chamadas de funções. O bloco de armazenamento colocado na pilha é conhecido como registro de ativação (stack frame), composto por:

a.       Parâmetros de entrada

b.      Valor de retorno

c.       Armazenamento temporário

d.      Copia do estado (registradores)

e.      Parâmetros de saída

PROGRAMA		STACK
CODIGO		Parâmetro de entrada
DADOS ESTATICOS
		Valor de retorno
STACK		Armazenamento temporário
		Copia do estado
HEAP		Parâmetro de saída

Retornando ao exemplo de calcular 5!, a área da pilha da execução do programa em C a cada chamada fica:

n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5

n=5

?

?

?

?

?

?

?

?

120

n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4

n=4

?

?

?

?

?

?

24

n=3

n=3

n=3

n=3

n=3

n=3

n=3

?

?

?

?

6

n=2

n=2

n=2

n=2

n=2

?

?

2

n=1

n=1

n=1

1

A pilha é uma solução boa para armazenar informação paras as chamadas de função, graças ao seu comportamento ultimo a entrar, primeiro a sair (LIFO), entretanto seu uso possui fatores contra, manter informações de cada chamada executada pela rotina até seu retorno consome um espaço considerável, adicione também o tempo necessário para salvar e restaurar informações do registro de ativação (stack frame).

Tais preocupações devem ser levadas em conta, recursão é um principio elogiado nos meios acadêmicos como poderoso e elegante, o que não acontece em meios práticos, aonde elaborações profissionais tende a abominar esse tipo de resposta devido aos problemas que um código recursivo agrega.

No livro Code Complete escrito por Steve McConnel apesar de expressar que o uso seletivo da recursividade agrega benefícios, isso não o impede de afirmar que se um programador que trabalha para ele usar recursividade para calcular um fatorial, contrataria outra pessoa (forma elegante de dizer que demitiria).

Entre as opiniões reacionárias do escritor sobre o assunto, temos as seguintes regras para o bom uso da recursão:

1.       Certifique-se de que a recursividade pare.

2.       Use contadores de segurança para evitar a recursividade infinita.

3.       Restrinja a recursividade a uma única rotina (A chama B, que chama C, que chama A).

4.       Fique atento a pilha.

5.       Nunca calcule fatorial ou números de Fibonacci com recursão.

A ironia do texto deve servir como aviso para um trecho discutido anteriormente em ponteiros, código mal planejado resulta em erros catastróficos. Tanto o mau uso de ponteiros, como o uso incorreto da recursividade gera problemas difíceis de detectar, prefira sempre uma solução iterativa.

unsigned int ifact(unsigned int n) {       unsigned int i;       for (i = (n-1); i > 0; --i)             n *= i;       return n; }