definição recursiva

Na lógica matemática e em ciência da computação, uma definição recursiva (ou definição indutiva) é usada para definir um objeto em termos de si próprio (Aczel 1977). Uma definição recursiva de uma função define valores das funções para algumas entradas em termos dos valores da mesma função para outras entradas. Por exemplo, a função fatorial n! é definida pelas regras 0! = 1.(n+1)! = (n+1)·n!. Esta definição é valida porque, para todo n, a recursão sempre vai alcançar o caso base de 0. Assim, a definição é bem-fundada. A definição pode também ser vista como um procedimento que descreve como construir a função n!, a partir de n = 0 e prosseguindo em diante com n = 1, n = 2, n = 3 etc.. Uma definição indutiva de um conjunto descreve os elementos de um conjunto em termos de outros elementos no conjunto. Por exemplo, uma definição do conjunto dos números naturais é: 1. * 0 pertence a . 2. * Se um elemento n pertence a então n+1 pertence a . 3. * é o menor conjunto que satisfaz (1) e (2). Há vários conjuntos que satisfazem (1) e (2) - por exemplo, o conjunto {0, 0.649, 1, 1.649, 2, 2.649, 3, 3.649, ...} satisfaz a definição. No entanto, a condição (3) especifica o conjunto dos números naturais, removendo os conjuntos com números externos. Propriedades de funções e conjuntos definidos recursivamente muitas vezes podem ser provadas por um princípio de indução que segue a definição recursiva. Por exemplo, a definição dos números naturais aqui apresentada implica o princípio da indução matemática para os números naturais: se o número natural 0 possui uma propriedade, e n+1 tem a propriedade sempre que n também a possui, então a propriedade é inerente a todos os números naturais (Aczel 1978:742).