Dê uma definição recursiva para a função nsubtermos : E N que, dada uma expressão aritmética, representada como um termo de E, 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.

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 um plus que soma duas constantes: const(suc zero) e const(zero).
  • E também temos outra const(zero).
No total, são 5 subtermos:
  1. times (...) (...)
  2. plus (...) (...)
  3. const(suc zero)
  4. const(zero) dentro do plus
  5. const(zero) fora do plus

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 ou times, 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:
nsubtermos(const x) = 1
nsubtermos(plus e1 e2) = 1 + nsubtermos(e1) + nsubtermos(e2)
nsubtermos(times e1 e2) = 1 + nsubtermos(e1) + nsubtermos(e2)

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 é:
nsubtermos(const x) = 1
nsubtermos(plus e1 e2) = 1 + nsubtermos(e1) + nsubtermos(e2)
nsubtermos(times e1 e2) = 1 + nsubtermos(e1) + nsubtermos(e2)
Essa definição satisfaz os critérios de totalidade e terminação, comprovando que nsubtermos é realmente uma função válida.

Exercícios relacionados