Dê uma definição recursiva para a função nsubtermos :
que, dada uma expressão aritmética, representada como um termo de
, retorna o número de subtermos dessa expressão. Por exemplo,
nsubtermos (const zero) retorna 1
nsubtermos (times (plus (const(suc zero)) (const(zero))) (const zero)) retorna 5
Justifique que sua definição é uma função, mostrando que ela satisfaz os critérios de totalidade e terminação.
nsubtermos (const zero) retorna 1
nsubtermos (times (plus (const(suc zero)) (const(zero))) (const zero)) retorna 5
Justifique que sua definição é uma função, mostrando que ela satisfaz os critérios de totalidade e terminação.
Passo 1
Beleza, vamos lá! O que a gente precisa resolver aqui é definir de forma recursiva uma função chamada
nsubtermos
que, dada uma expressão aritmética, conta quantos subtermos ela possui. A matéria envolvida aqui é recursão em estruturas de dados, que é fundamental na programação e em lógica matemática. Para resolver isso, vamos precisar entender como as expressões aritméticas são construídas e como aplicar a recursão para navegar por cada parte dessa expressão.Passo 2
Primeiro, vamos entender o que é uma expressão aritmética. No nosso caso, uma expressão pode ser uma constante, como
zero
, ou uma operação como plus
(adição) ou times
(multiplicação), que combina outras expressões.Passo 3
A função
nsubtermos
precisa contar cada parte da expressão. Por exemplo, na expressão const zero
, temos apenas um subtermo: const zero
mesmo.Passo 4
Agora, vejamos uma expressão mais complexa:
times (plus (const(suc zero)) (const(zero))) (const zero)
. Aqui, temos várias partes:times
é uma operação que multiplica duas expressões.- Dentro do
times
, temos umplus
que soma duas constantes:const(suc zero)
econst(zero)
. - E também temos outra
const(zero)
.
No total, são 5 subtermos:
times (...) (...)
plus (...) (...)
const(suc zero)
const(zero)
dentro doplus
const(zero)
fora doplus
Passo 5
Para definir a função recursiva, precisamos considerar os diferentes casos de uma expressão:
- Caso Base: Se a expressão for uma constante (
const x
), então o número de subtermos é 1. - Caso Recursivo: Se a expressão for uma operação como
plus
outimes
, então o número de subtermos é 1 (para a própria operação) mais a soma dos subtermos das expressões que ela combina.
Passo 6
Agora, vamos escrever a definição recursiva usando notação matemática:
Passo 7
Vamos justificar que
nsubtermos
realmente é uma função. Precisamos mostrar que ela é total e que termina (não fica em loop infinito).-
Totalidade: A função está definida para todos os possíveis termos de
$\mathcal{E}$
. Ou seja, para qualquer expressão que a gente tiver como entrada, a função sabe como computar o número de subtermos. -
Terminação: A definição é recursiva, mas sempre trabalha com subtermos menores. Isso significa que a cada passo, a função processa uma parte menor da expressão, garantindo que eventualmente vai chegar ao caso base (
const x
) e parar.
Resposta
Então, a definição recursiva para a função
nsubtermos
é:Essa definição satisfaz os critérios de totalidade e terminação, comprovando que
nsubtermos
é realmente uma função válida.