Defina uma função max:
por
(a) Use essa função para escrever uma função recursiva
que retorne o maior valor em
, em que
é uma lista de números.
(b) Demonstre que a sua função LMax funciona. Em outras palavras, demonstre que LMax
retorna o maior valor na lista
.
(b) Demonstre que a sua função LMax funciona. Em outras palavras, demonstre que LMax
Passo 1
O enunciado define a função
e pede (a) uma definição recursiva de
que retorne o maior elemento de uma lista
de números, e (b) uma demonstração de que essa função de fato devolve o máximo de
. Vamos usar indução sobre o comprimento de
.
Passo 2
Definimos o caso base, em que a lista tem exatamente um elemento. Se
então não há outra escolha senão
Passo 3
Definimos o caso recursivo. Se a lista
tem pelo menos dois elementos, escrevemos
onde
é o primeiro elemento e
é o restante da lista. Então definimos
Passo 4
Para provar que
realmente retorna o maior elemento de
, enunciamos a propriedade
:
“Para toda lista de comprimento
,
é o maior elemento de
.”
“Para toda lista
Passo 5
Verificação de
(base da indução). Se
, então por definição
, e
é claramente o maior (único) elemento de
. Logo
vale.
Passo 6
Passo indutivo: suponha
Por definição de e todos os elementos de
, ou seja, o maior de
. Assim
vale, completando a indução.
Resposta
(a) Para qualquer lista não vazia
,
(b) A prova por indução sobre o comprimento de
mostra que esse algoritmo devolve sempre o maior elemento da lista.