Nome: ? | Matrícula: ?

Programação funcional

Recursão profunda

Até agora temos trabalhado com listas de átomos, usando recursão para processar seu conteúdo. Definimos como lista profunda uma lista que contém outras listas. Listas profundas podem ser pensadas como árvores. Exemplo:

(a ((b c)) (d (e (f))) g)
       (a ((b c)) (d (e (f))) g)
                 |
----------------------------------------
|         |              |             |
a      ((b c))      (d (e (f)))        g
          |              |
          |          ----------
          |          |        |
        (b c)        d     (e (f))
          |                   |
       ------             --------
       |    |             |      |
       b    c             e     (f)
                                 |
                                 f

Para explorar a árvore completamente, é preciso usar recursão profunda. O função usa recursão profunda quando chama a si própria recursivamente no car e no cdr da lista.

Exemplo: membro-prof

Implemente a função (membro-prof x expr), que indica se x aparece na expressão expr, que pode ser um átomo ou uma lista (possivelmente profunda).

function(str, info) { return multiEval(str, info); }

OBS.: (consp x) indica se x é uma lista com pelo menos um elemento

Exemplo: conta-ocorrencias-prof

Modifique a função anterior para contar o número de ocorrências de x na expressão expr, usando recursão profunda

function(str, info) { return multiEval(str, info); }

Exemplo: subst

Crie uma função, (subst x y expr), que substitua as oorrências de x por y na expressão expr, usando recursão profunda.

function(str, info) { return multiEval(str, info); }

Exemplo: flatten

Crie uma função, (flatten lista), que “achata” a lista, isto é, retorna uma lista de átomos com a mesma sequência de átomos da lista profunda lista.

function(str, info) { return multiEval(str, info); }

Exemplo: flatten com recursão de cauda

Reimplemente a função anterior usando recursão de cauda.

function(str, info) { return multiEval(str, info); }