Funções Recursivas

[pic 1]

Janderson Lucas de Jesus Freire

Funções Recursivas

Brasília
Novembro/2014

[pic 2]

Janderson Lucas de Jesus Freire

RA: B928492

Funções Recursivas

[pic 3]

Brasília
Novembro/2014

Sumário

Introdução        

Definição Recursiva        

Sequência recursiva        

Conjuntos recursivos        

Algoritmos recursivos        

Algoritmo Iterativo        

Conclusão        

Referências        

Introdução

Definição Recursiva

È uma definição na qual o item que está sendo definido aparece como parte da definição. Esse procedimento funciona porque as definições recursivas são formadas por duas partes: uma base, que determina explicitamente alguns casos simples do item que está sendo definido. Um passo indutivo ou recursivo, onde outros casos do item que está sendo definido são determinados em termos dos casos anteriores a recursão pode ser usada para definir seqüência de objetos, operações sobre objetos, conjuntos e algoritmos.

Sequência recursiva

Uma sequência é uma lista de objetos, enumerados segundo uma ordem.

S(k) denota o k­ésimo elemento da sequência.        

Uma sequência recursiva explicita seu primeiro valor (ou primeiros valores) e define outros valores na sequência em termos  dos valores iniciais.

EXEMPLOS:

Sequência definida  recursivamente

1. S(1) = 2

2. S(n)  = 2S(n­1) para  n ≥ 2

O primeiro valor da sequência é explicitamente dado, S(1) = 2, os valores seguintes são sucessivamente calculados com base na definição recursiva:

■   S(2) = 2S(1)  = 2*2 = 4

■   S(3) = 2S(2)  = 2*4 = 8

■   S(4) = 2S(3)  = 2*8 = 16

Escreva os primeiros 5 valores da Sequência T definida  por:

1. T(1) = 1

2. T(n) = T(n­1)+3 para  n ≥ 2

■   T(1) = 1

■   T(2) = T(1) + 3 = 1 + 3 = 4

■   T(3) = T(2) + 3 = 4 + 3 = 7

■   T(4) = T(3) + 3 = 7 + 3 = 10

■   T(5) = T(4) + 3 = 10 + 3 = 13

=

        

Conjuntos recursivos

Enquanto objetos de uma sequência são ordenados, um conjunto é uma coleção de objetos na qual nenhuma regra de ordenação é imposta. Certos conjuntos podem ser definidos recursivamente:

Definição recursiva para o conjunto dos ancestrais de um ser vive:

•    Os pais de um ser vivo são seus ancestrais.

•     Todo pai de um ancestral também é um ancestral.

Seja S o conjunto dos inteiros  positivos divisíveis por 3, definido  recursivamente por:

1. 3 ∊ S

2. (x + y) ∊ S se (x ∊ S) e (y ∊ S)

Prova

Seja A o conjunto de todos os  inteiros  positivos divisíveis por 3. Para mostrar que A = S, é necessário que A ⊆ S e S ⊆ A

Parte I: Prove que A ⊆ S (usando indução matemática)

 Seja P(n) a afirmativa “3n pertence a S”.