Classe das Funes Definidas Recursivamente

Semntica de uma Funo Definida Recursivamente

A definio das Recursivas de Bird pode ser vista atravs de alguns exemplos que mostram o seu potencial. Inicialmente, sabe-se que a Classe das funes com Definio Recursiva a mesma Classe das Funes Computveis.Considera-se a expresso:

Onde informalmente a expresso, se verdadeiro e caso contrrio.

EXEMPLO 1 FATORIALConsiderando a seguinte definio recursiva para uma funo fatorial:

Se considerarmos , teremos:

Pode-se observar que no tem valor definido, pois indefinido. Como , a funo tem valor definido e igual a 1.

EXEMPLO 2 ADIO, MULTIPLICAO E POTENCIALIZAOConsiderando a seguinte definio recursiva para uma funo de adio, multiplicao e potencializao:

Observa-se que: A adio definida atravs da funo sucessor A multiplicao definida em termos de adies de y A potencializao definida em termos de multiplicaes de x

EXEMPLO 3 DIVISO E MULTIPLICAOConsiderando a seguinte definio recursiva para uma funo de diviso e de multiplicao, como dada acima:

Para , tem-se: = 0, definido indefinido, pois indefinido.

EXEMPLO 4 MINIMIZAOSeja a funo h definida pela minimizao de obtem-se:

Para definir h preciso uma funo k:

Ento h pode ser definida como:

Para o valor x, h definida como o menor natural y tal que f(x,y) = 0.

CLASSE DAS FUNES DEFINIDAS RECURSIVAMENTEA seguir sero mostrados alguns tipos de Classes das Funes Definidas Recursivamente. E posteriormente, sero mostradas suas definies e expresses numricas.Tipo 1. Tipo de Definio RecursivaUm tipo de definio recursiva pode ser dada abaixo, sendo

B

As constantes e variveis dos tipos, assume-se: Tipo . As constantes so os nmeros: 0,1,2... As variveis so: x,y,z... Tipo B Denota-se apenas como verdadeiro ou falso Tipo A nica constante denotada por zero: Tipo Denotados por antecessor e sucessor Sucessor: Antecessor: Tipo ou . As variveis so denotadas por f,g,h...