algoritimos recurssivos

ALGORITMO RECURSIVO

Definição
O objetivo do algoritmo recursivo consiste em diminuir sucessivamente o problema em um problema menor ou mais simples, até que o tamanho o ou a simplicidade do problema reduzido permita resolvê-lo de forma direta, sem recorrer a si mesmo. Quando isso ocorre, diz-se que o algoritmo atingiu uma condição de parada, a qual deve estar presente em pelo menos um local dentro algoritmo. Sem esta condição o algoritmo não para de chamar a si mesmo, até estourar a capacidade da pilha, o que geralmente causa efeitos colaterais e até mesmo o término indesejável do programa.

Para todo algoritmo recursivo existe um outro correspondente interativo (não recursivo), que executa a mesma tarefa. Implementar um algoritmo recursivo, partindo de uma definição recursiva do problema, em uma linguagem de programação de alto nível com Pascal e C é simples e quase imediato,pois o seu código é praticamente transcrito para a sintaxe da linguagem.

RECURSIVIDADE E RELAÇÕES DE RECORRÊNCIA
Definição Recorrente

Uma definição onde item sendo definido aparece como parte da definição é chamada de definição recorrente ou definição por recorrência ou ainda definição por indução. A principio isso não parece fazer sentido, como podemos definir algo em termos de si mesmo? Isso funciona porque uma definição recorrente tem duais partes:

1.uma base, ou condição básica, onde alguns casos simples do item sendo definido são dados explicitamente.

2.um passo de indução ou recorrência, onde novos casos do item sendo definido são dados em função de casos anteriores.

SEQUÊNCIA DEFINIDA POR RECORRÊNCIA
EXEMPLO 1
A sequência S é definida por recorrência por

1.S(1) = 2
2. S(n) = 2S(N-1) para n >= 2

Pela proposição 1,S(1), o primeiro objeto em S, é 2.Depois pela proposição 2, o segundo objeto em S é S(@) = 2S(1) =2(2) = 4. Novamente pela proposição 2, S(3) = 2S(2) = 2 = 2(4) = 8, Continuando desse modo, vemos que a sequência S é.
2,4,8,16,32,...
Uma