Função discreta recursiva
Na matemática, há um teorema que estabelece que toda definição indutiva pode ser simulada por uma função recursiva, construída a partir da base de indução e passo indutivo.
Importante
Vale lembrar que nem toda função recursiva vem de uma base indutiva.
A Teoria da Computação define uma função recursiva como sendo uma função que é computável, ou seja, em termos computacionais, significa que ela pode escrever um programa que simula tal função.
Para se construir uma função recursiva indutiva é guiada pelos passos da definição indutiva:
- Base de indução: definir todos os casos elementares de resultado da função
- Passo indutivo: determinar como calcula o valor da função através de casos anteriores.
Pegando o exemplo usado em Definições indutivas, a sua implementação de forma recursiva fica:
- Base de indução:
- Passo indutivo:
,
Observação
Observe que, no passo indutivo, é utilizado o nome da função dentro da sua própria definição. Isto é o que caracteriza, numa linguagem de programação, a possibilidade de uso de recursão em funções.