Recurssividade

Recursividade

1. Programação Recursiva
Recursividade é uma função que invoca a si própria, ou invoca outra função, e na seqüência das diversas subfunções, uma das subfunções invoca a primeira função. Cada vez que é realizada a chamada recursiva um novo espaço de memória é alocado mesmo que a função já tenha sido chamada antes, o número de vezes que ela pode ser chamada é a mesma do tamanho da pilha, se o limite for ultrapassado é enviada uma mensagem de erro StackOverflow ou Stackfault .
Esse método deve ser utilizado somente quando for a forma mais simples e intuitiva de se ter uma solução para o problema.
Toda vez que houver uma chamada recursiva uma cópia dos seus parâmetros é alojada e guardada afim de não perder os valores das chamadas anteriores. A invocação de uma estrutura funciona da mesma forma que uma função não recursiva, sendo necessário guardar a estrutura de invocação até o fim da execução.

2. Tipos de Recursividade

Direta: a função contém uma chamada explícita a si própria

Indireta: a função F chama a função G que por sua vez chama F

Terminal: o valor de retorno da função é o valor de retorno da chamada recursiva (não existem operações pendentes)

Recursividade direta:

int factorial (int n){ if (n == 0)
// caso terminal / ponto paragem return(1); else
// caso geral / regra geral return(n * factorial(n - 1));
}

Recursividade terminal:

int factorial (int n, int r){ if (n == 0)
// caso terminal / ponto paragem return(r); else
// caso geral / regra geral return(factorial(n – 1, n * r));
}

3. Recursão versus Iteração
No exemplo do fatorial, a implementação iterativa tende a ser ligeiramente mais rápida na prática do que a implementação recursiva, uma vez que uma implementação recursiva precisa registrar o estado atual do processamento de maneira que ela possa continuar de onde parou após a conclusão de cada nova execução subordinada do procedimento recursivo. Esta ação consome tempo e memória.
Existem