Aula 4

jupyter do ic ainda nao esta funcionando
Vamos usar o site rextester userid mc346b password mc346b
Maior elemento de uma lista

(defun maior (l)
   (if (= (tamanho l) 1) (first l)
       (if (> (maior (rest l)) (first l))
           (maior (rest l))
           (first l)
       )))

Esse código é exponencial se a lista estiver na order crescente! O problema é que a mesma recursão é chamada 2 vezes.

É preciso uma variavel local para armazenar o resultado da computacao de (maior (rest l))
let - cria e atribui valor a uma ou mais variaveis local

(let ( 
       (variavel valor)
       (variavle valor)
       ...
      )
   expressao)

(defun maior (l)
     (if (= (tamanho l) 1) 
         (first l)
         (let ((maxx (maior (rest l))))
             (if (> maxx (first l))
                 (first l)
                 maxx))
         ))

eq, =, equal - testes de igualdade

1 Problemas com recursão

cuidado com o padrão (append (f (rest l)) (list (first l))) - isso torna o codigo quadratico porque o append copia o 1o argumento
absoluto cuidado com a mesma recursao sendo feita 2 vezes - o codigo vira exponencial

2 Arvores

a arvore vazia é ()
um nó com valor armazenado x é representado por (x lado-esquerdo lado-direito)
desenhe a arvore (5 () (8 (6 () (7 () ())) (9 () ())))

2.1 exercicios

retorne o número de nos de uma arvore
retorne a profundidade máxima de uma arvore
dado uma arvore, gere uma lista com todos nós na ordem infixa (lado-esquerdo no lado-direito)
gere uma lista dos nos na ordem prefixa (no esq dir)
dado uma lista retorne T se ela é uma arvore de busca binária
dado uma arvore de busca binaria e um item, verifique se o item esta na arvore
dado uma abb e um item, retorne a arvore com o item inserido
dado uma abb e um item, retorne a arvore sem o item

3 Uma versão de arvore pior

arvore vazia ()
uma arvore que so contem o elemento x -> x
(x lado-esquerdo lado-direito)
desenhe a arvore (5 () (8 (6 () 7 ) 9))
o seu codigo agora vai ter que testar o tipo do item na lista
listp -> T se o argumento for uma lista
numberp -> T se o argumento for um numero
refaca alguns exercicios de arvores usando essa nova representacao