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 umplusque 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 doplusconst(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
plusoutimes, 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.