Uma função recursiva é uma função que se refere a si própria. A ideia consiste em utilizar a própria função que estamos a definir na sua definição.
Em todas as funções recursivas existe:
Se analisarmos a função factorial, o caso básico é o teste de igualdade a zero (zerop n), o resultado imediato é 1, e o passo recursivo é (* n (fact (- n 1))).
Geralmente, uma função recursiva só funciona se tiver uma expressão condicional, mas não é obrigatório que assim seja. A execução de uma função recursiva consiste em ir resolvendo subproblemas sucessivamente mais simples até se atingir o caso mais simples de todos, cujo resultado é imediato. Desta forma, o padrão mais comum para escrever uma função recursiva é:
No caso de erro em função recursivas, o mais usual é a recursão nunca parar. O número de chamadas recursivas cresce indefinidamente até esgotar a memória (stack), e o programa gera um erro. Em certas linguagens (Scheme) e implementações do Common Lisp, isto não é assim, e pode nunca ser gerado um erro. A recursão infinita é o equivalente das funções recursivas aos ciclos infinitos dos métodos iterativos do tipo while-do e repeat-until.
Repare-se que uma função recursiva que
funciona perfeitamente para os casos para que foi prevista pode
estar completamente errada para outros casos. A função
fact é um exemplo. Quando o argumento é negativo, o problema
torna-se cada vez mais complexo, cada vez mais longe do caso
simples. (fact -1) => (fact -2) => (fact -3) =>
Exercício 9
Considere uma versão extremamente primitiva da linguagem Lisp, em que as únicas funções numéricas existentes são zerop e duas funções que incrementam e decrementam o seu argumento em uma unidade, respectivamente, 1+ e 1-. Isto implica que as operações >, <, = e similares não podem ser utilizadas. Nesta linguagem, que passaremos a designar por nanoLisp, abreviadamente nanoLisp , defina o predicado menor, que recebe dois número inteiros positivos e determina se o primeiro argumento é numericamente inferior ao segundo.
Exercício 10
Defina a operação igual? que testa igualdade numérica de inteiros positivos na linguagem nanoLisp .
Exercício 11
Até ao momento, a linguagem nanoLisp apenas trabalha com números inteiros positivos. Admitindo que as operações 1+, 1- e zerop também funcionam com números negativos, defina a função negativo que recebe um número inteiro positivo e retorna o seu simétrico. Assim, pretendemos obter: (negativo 3) => -3.
Exercício 12
Agora que a linguagem nanoLisp pode também trabalhar com números inteiros negativos, defina o predicado positivo?, que recebe um número e indica se ele é positivo ou não.
Exercício 13
Defina o teste de igualdade de dois números na linguagem nanoLisp contemplando a possibilidade de trabalhar também com números inteiros negativos.
Exercício 14
Defina a função simétrico de um número qualquer na linguagem nanoLisp .
Exercício 15
É possível definir a soma de dois números inteiros positivos em nanoLisp , i.e., apenas recorrendo às funções 1+ e 1- que somam e subtraem uma unidade, respectivamente. Defina a operação soma.
Exercício 16
Generalize a função de soma de modo a poder receber números inteiros positivos e negativos.
Exercício 17
Do mesmo modo que a soma pode ser definida exclusivamente em termos de sucessor 1+ e predecessor 1-, a multiplicação pode ser definida exclusivamente em termos da soma. Defina a função mult que recebe dois número e os multiplica usando a função soma.