O objetivo deste exercício é que você compreenda porque definições recursivas que não atendem os critérios de totalidade e terminação não podem ser consideradas funções. Apresente exemplos de definições recursivas que: 1) não atendem o crítério de totalidade e 2) não atendem o critério de terminação. Por que essas definições não podem ser funções?
Passo 1
Beleza, vamos lá! O exercício pede para a gente entender por que definições recursivas que não garantem totalidade e terminação não podem ser consideradas funções. A gente vai precisar falar sobre o que é recursão, totalidade e terminação. Basicamente, vamos ver exemplos de definições que falham nesses critérios e por que isso impede que elas sejam funções de verdade.
Passo 2
Primeiro, vamos falar sobre totalidade. Uma definição recursiva é total quando ela está definida para todos os possíveis valores de entrada. Se faltar algum caso, a definição não é total. Por exemplo, imagine que queremos definir uma função recursiva para calcular o fatorial de um número:
Aqui, a função está bem definida para todos os números inteiros não negativos. Mas e se esquecêssemos o caso de $ n = 0 $? Aí a definição não seria total, porque para $ n = 0 $ a função não está definida.
Passo 3
Agora, vamos falar sobre terminação. Uma definição recursiva termina quando, ao aplicar a recursão, eventualmente chega a um caso base que para a chamada recursiva. Se a recursão nunca para, a definição não tem terminação. Por exemplo, pense na seguinte definição:
Aqui, para qualquer valor de $ n $, a função tenta calcular $ f(n+1) $, que por sua vez tenta calcular $ f(n+2) $, e assim por diante, sem nunca chegar a um ponto final. Isso significa que a definição não termina.
Passo 4
Agora, por que essas definições que faltam totalidade ou terminação não podem ser funções? Bem, uma função precisa estar bem definida para cada entrada esperada (totalidade) e, para cada entrada, deve dar um resultado finito (terminação). Se faltar totalidade, tem entrada para a qual a função não retorna nada. Se faltar terminação, a função nunca chega a um resultado. Portanto, essas definições quebram as regras básicas para serem consideradas funções válidas.
Resposta
Definições recursivas que não são totais ou que não terminam não podem ser consideradas funções porque não garantem um resultado definido e finito para todas as entradas. Sem totalidade, falta definição para alguns casos, e sem terminação, a computação nunca chega a um resultado, violando os requisitos fundamentais de uma função.