Funções Recursivas

Ciência da Computação

Teoria da Computação
(ENG10395)

Profa. Juliana Pinheiro Campos
E-mail: [e-mail]

TEORIA DA COMPUTAÇÃO

Funções recursivas
 Os formalismos usados para especificar algoritmos podem ser classificados nos seguintes tipos:
• Operacional: define-se uma máquina abstrata baseada em estados, em instruções primitivas e na especificação de como cada instrução modifica cada estado. Ex: MT.
• Axiomático: Associam-se regras às componentes da linguagem. As regras permitem afirmar o que será verdadeiro após a ocorrência de cada cláusula, considerando-se o que era verdadeiro antes da ocorrência. Ex: gramática.

TEORIA DA COMPUTAÇÃO

Funções recursivas
• Denotacional ou funcional: Trata-se de uma função construída a partir de funções elementares de forma composicional, no sentido em que o algoritmo denotado pela função pode ser determinado em termos de suas funções componentes. Ex: funções recursivas parciais (de
Stephen C. Kleene) e cálculo lambda (de Alonzo
Church)

TEORIA DA COMPUTAÇÃO

Funções recursivas de Kleene (ou funções recursivas parciais)
 São funções construídas sobre 3 funções naturais básicas
(funções recursivas primitivas):
• natural zero visto como uma função
• sucessor (de um número natural)
• projeção (na realidade, uma família de funções, pois depende do n° de componentes, bem como de qual componente deseja-se projetar) juntamente com as seguintes operações:
• substituição composicional (generaliza o conceito usual de composição de funções)

TEORIA DA COMPUTAÇÃO

Funções recursivas de Kleene (ou funções recursivas parciais)
• recursão (definição de uma função em termos dela mesma)
• minimização (busca, em um tempo finito, o menor valor para o qual uma certa condição ocorre) constituindo uma forma compacta e natural para definir muitas funções e suficientemente poderosa para descrever toda função intuitivamente computável.

TEORIA DA COMPUTAÇÃO

