Exemplos

Funções Recursivas

O seguinte código ALisP define uma pequena biblioteca de funções que ilustram cálculos recursivos.

(
    (set fib (fn (x) 
        (if (<= x 1) 
            1 
            (+ 
                (fib (- x 1))
                (fib (- x 2)) )
        )
    ))

    (set fact (fn (n)
        (if (<= n 1)
            1
            (*  
                n 
                (fact (- n 1))
            )
        )
    ))
)

Guarde este código em, por exemplo, recursivas.lisp e experimente:

  • alisp.py -l recursivas.lisp -e "(fact 100)" e deve obter imediatamente o resultado, que é um número com 246 dígitos ;)
  • alisp.py -l recursivas.lisp -e "(fib 20)" demora um tempo considerável (alguns segundos) e o resultado é 10946.
  • Exercício. A implementação de fib é muito pouco eficiente (porque o mesmo cálculo é feito duas vezes em cada passo!). Modifique-a (substituindo a recursão por um ciclo) de forma a ter um desempenho melhor. Deve conseguir calcular rapidamente (fib 10000), que tem 2090 dígitos. Já fib 100000) demora alguns segundos e é um número com 20899 dígitos :D

Adivinhar o Número

O jogo Adivinha o número é um problema simples que permite testar várias caraterísticas de uma linguagem de programação.

  1. O programa define um número secreto, entre 0 e 100 e o jogador tem de adivinhar esse segredo.
  2. O programa pede um palpite ao jogador.
  3. Se a resposta do jogador está certa, o jogo termina. O programa dá os parabéns e diz quantas tentativas foram necessárias.
  4. Caso contrário, o programa responde maior ou menor conforme o segredo é maior ou menor que o palpite e volta a pedir um palpite.

Uma implementação do Adivinha o Número em ALisP:

(seq
    (set greet (fn (name)
        (Hello name . Welcome to the Guess-the-Number game.)
    ))

    (set ord (fn (n)
        (if (== 1 n)
            first
            (if (== 2 n)
                second
                (if (== 3 n)
                    third
                    (n -th)
                )
            )
        )
    ))

    (set main (fn ()
        (write (What is your name?))
        (set name (read))
        (write (greet name))
        (set my-secret 42)
        (set answer 50)
        (set count 0)
        (while (!= answer my-secret) (
            (set count (+ count 1))
            (write (Guess the secret number [(ord count) tentative]))
            (set answer (read))
            (write
                (if (== answer my-secret)
                    (Very well name . You found that the secret is ** my-secret ** using only count guesses.)
                    (Not yet, name . The secret is **
                        (if (< my-secret answer)
                            smaller
                            greater
                        )
                        ** than answer . Try again.
                    )
                )
            )
        ))
    ))

    (main)
    BYE
)