Definição recursiva - Recursive definition

Quatro etapas na construção de um floco de neve Koch . Como acontece com muitos outros fractais , os estágios são obtidos por meio de uma definição recursiva.

Em matemática e ciência da computação , uma definição recursiva , ou definição indutiva , é usada para definir os elementos em um conjunto em termos de outros elementos no conjunto ( Aczel 1977: 740ss). Alguns exemplos de objetos definíveis recursivamente incluem fatoriais , números naturais , números de Fibonacci e o conjunto ternário Cantor .

Uma definição recursiva de uma função define os valores da função para algumas entradas em termos dos valores da mesma função para outras entradas (geralmente menores). Por exemplo, a função fatorial n ! é definido pelas regras

0! = 1.

( n + 1)! = ( n + 1) · n !.

Esta definição é válida para cada número natural n , porque a recursão eventualmente atinge o caso base de 0. A definição também pode ser pensada como dando um procedimento para calcular o valor da função n !, Começando de n = 0 e prosseguindo com n = 1, n = 2, n = 3 etc.

O teorema da recursão afirma que tal definição realmente define uma função que é única. A prova usa indução matemática .

Uma definição indutiva de um conjunto descreve os elementos de um conjunto em termos de outros elementos do conjunto. Por exemplo, uma definição do conjunto N de números naturais é:

1 é em N .
Se um elemento n é em N , então n + 1 é em N .
N é a interseção de todos os conjuntos que satisfazem (1) e (2).

Existem muitos conjuntos que satisfazem (1) e (2) - por exemplo, o conjunto {1, 1.649, 2, 2.649, 3, 3.649, ...} satisfaz a definição. No entanto, a condição (3) especifica o conjunto de números naturais removendo os conjuntos com membros estranhos. Observe que esta definição assume que N está contido em um conjunto maior (como o conjunto de números reais) - no qual a operação + é definida.

Propriedades de funções e conjuntos definidos recursivamente podem frequentemente ser provadas por um princípio de indução que segue a definição recursiva. Por exemplo, a definição dos números naturais apresentada aqui implica diretamente no princípio da indução matemática para números naturais: se uma propriedade é válida para o número natural 0 (ou 1), e a propriedade é válida para n +1 sempre que ela é válida para n , então a propriedade é válida para todos os números naturais (Aczel 1977: 742).

Forma de definições recursivas

A maioria das definições recursivas tem dois fundamentos: um caso base (base) e uma cláusula indutiva.

A diferença entre uma definição circular e uma definição recursiva é que uma definição recursiva deve sempre ter casos base , casos que satisfaçam a definição sem serem definidos em termos da própria definição, e que todas as outras instâncias nas cláusulas indutivas devem ser "menores" em algum sentido (ou seja, mais perto daqueles casos de base que encerram a recursão) - uma regra também conhecida como "recorrência apenas com um caso mais simples".

Em contraste, uma definição circular pode não ter nenhum caso base, e até mesmo pode definir o valor de uma função em termos daquele valor em si - ao invés de outros valores da função. Tal situação levaria a uma regressão infinita .

Que as definições recursivas são válidas - o que significa que uma definição recursiva identifica uma função única - é um teorema da teoria dos conjuntos conhecido como teorema da recursão , cuja prova não é trivial. Onde o domínio da função são os números naturais, condições suficientes para a definição ser válida são que o valor de $f (0)$ (ou seja, caso base) seja dado, e que para $n > 0$ , um algoritmo seja dado para determinar $f (n)$ em termos de $n, f (0), f (1), ..., f (n - 1)$ (isto é, cláusula indutiva).

De maneira mais geral, as definições recursivas de funções podem ser feitas sempre que o domínio for um conjunto bem ordenado , usando o princípio da recursão transfinita . Os critérios formais para o que constitui uma definição recursiva válida são mais complexos para o caso geral. Um esboço da prova geral e os critérios podem ser encontrados em James Munkres ' Topologia . No entanto, um caso específico (o domínio é restrito aos inteiros positivos em vez de qualquer conjunto bem ordenado) da definição recursiva geral será dado abaixo.

Princípio de definição recursiva

Deixe $A$ ser um conjunto e deixar $a 0$ ser um elemento de $A$ . Se $ρ$ é uma função que atribui a cada função $f$ mapeando uma seção não vazia dos inteiros positivos em $A$ , um elemento de $A$ , então existe uma função única tal que ${\ displaystyle h: \ mathbb {Z} _ {+} \ to A}$

{\ displaystyle h (1) = a_ {0}}

{\ displaystyle h (i) = \ rho (h | _ {\ {1,2, \ ldots, i-1 \}}) {\ text {for}} i> 1.}

Exemplos de definições recursivas

Funções elementares

A adição é definida recursivamente com base na contagem como

{\ displaystyle 0 + a = a,}

{\ displaystyle (1 + n) + a = 1 + (n + a).}

A multiplicação é definida recursivamente como

{\ displaystyle 0a = 0,}

{\ displaystyle (1 + n) a = a + na.}

A exponenciação é definida recursivamente como

{\ displaystyle a ^ {0} = 1,}

{\ displaystyle a ^ {1 + n} = aa ^ {n}.}

Coeficientes binomiais podem ser definidos recursivamente como

{\ displaystyle {\ binom {a} {0}} = 1,}

{\ displaystyle {\ binom {1 + a} {1 + n}} = {\ frac {(1 + a) {\ binom {a} {n}}} {1 + n}}.}

números primos

O conjunto de números primos pode ser definido como o conjunto único de inteiros positivos que satisfazem

1 não é um número primo,
qualquer outro inteiro positivo é um número primo se, e somente se, não for divisível por nenhum número primo menor que ele mesmo.

A primalidade do inteiro 1 é o caso base; verificar a primalidade de qualquer inteiro maior X por esta definição requer conhecer a primalidade de cada inteiro entre 1 e X , que é bem definido por esta definição. Esse último ponto pode ser provado por indução em X , para o qual é essencial que a segunda cláusula diga "se e somente se"; se tivesse dito apenas "se", a primalidade de, por exemplo, 4 não seria clara, e a aplicação posterior da segunda cláusula seria impossível.

Números pares não negativos

Os números pares podem ser definidos como consistindo em

0 está no conjunto E de eventos não negativos (cláusula base),
Para qualquer elemento x no conjunto E , x + 2 está em E (cláusula indutiva),
Nada está em E a menos que seja obtido das orações base e indutiva (cláusula extrema).

Fórmulas bem formadas

É principalmente na lógica ou na programação de computadores que as definições recursivas são encontradas. Por exemplo, uma fórmula bem formada (wff) pode ser definida como:

um símbolo que representa uma proposição - como p significa "Connor é um advogado".
O símbolo de negação, seguido por um wff - como Np significa "Não é verdade que Connor seja advogado."
Qualquer um dos quatro conectivos binários ( C , A , K ou E ) seguido por dois wffs. O símbolo K significa "ambos são verdadeiros", então Kpq pode significar "Connor é advogado e Mary gosta de música".

O valor de tal definição recursiva é que ela pode ser usada para determinar se qualquer sequência particular de símbolos é "bem formada".

Kpq é bem formado, porque é K seguido pelas wffs atômicas p e q .
NKpq é bem formado, porque é N seguido por Kpq , que por sua vez é um wff.
KNpNq é K seguido por Np e Nq ; e Np é um wff, etc.

Veja também

Notas

Referências

Halmos, Paul (1960). Teoria dos conjuntos ingênua . van Nostrand . OCLC 802530334 .
Aczel, Peter (1977). “Uma introdução às definições indutivas”. Em Barwise, J. (ed.). Handbook of Mathematical Logic . Estudos em Lógica e os Fundamentos da Matemática. 90 . Holanda do Norte . pp. 739–782. doi : 10.1016 / S0049-237X (08) 71120-0 . ISBN 0-444-86388-5 .
Hein, James L. (2010). Estruturas discretas, lógica e computabilidade . Jones e Bartlett . ISBN 978-0-7637-7206-2 . OCLC 636352297 .

Languages

In other projects