• Revista PROGRAMAR: Já está disponível a edição #53 da revista programar. Faz já o download aqui!

Baderous

Padrões de recursividade

10 mensagens neste tópico

Tenho uma função que expressa o padrão de definição de funções usando recursividade primitiva:

primrec c g 0 = c
primrec c g (n+1) = g n (primrec c g n)

Agora tenho de definir a função factorial usando esta. O que eu tenho é isto:

factorial n = primrec 1 (*) n

Sei que isto vai dar 0 em todos os casos, até porque já fiz as reduções à mão para ver, mas não consigo achar a solução.

Depois tenho também outro desafio que consiste em escrever a 1ª função, mas agora expressando o padrão de definição de funções recursivas usando acumuladores. Tenho isto:

primrec' c g 0 = c
primrec' c g (n+1) = primrec' (g n) g n

Como é que sei que isto está certo. A mim parece-me que está, mas como testo?

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Hmm a primeira função foi te dada, ou foste tu que fizeste. Porque como tens está errada.

Presumo que deveria ser:

primrec c g 0 = c
primrec c g (n+1) = g (n+1) (primrec c g n)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não podes usar essa definição de multiplicação...

Usa a seguinte função: mult x y = (x+1) * y

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

LOL por acaso foi dada pelo livro do JBB (já detectei alguns erros na edição que tenho, este escapou-me). Pois agora que dizes, já faz mais sentido e já funciona a minha factorial.

Agora a outra é que continua mal, pois quando testo, dá-me o "No instance for (Num (t -> t))". Penso que tem a ver com a forma como o acumulador está a ser actualizado.

primrec' c g 0 = c
primrec' c g (n+1) = primrec' (g n) g (n+1)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Pensa como é que farias a função reverse com o uso de acumuladores.

A tua função primrec' tem de usar o mesmo padrão :thumbsup:

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Não é erro nenhum. Isso deriva da definição matemática da operação de recursão primitiva: http://en.wikipedia.org/wiki/Primitive_recursive_function

EDIT:

Sejam

f : N0k -> N0

g : N0k+2 -> N0

Seja

h : N0k+1 -> N0

definida por

h(x1, ..., xk, 0) = f(x1, ..., xk)

h(x1, ..., xk, y+1) = g(x1, ..., xk, y, h(x1, ..., xk, y))

h diz-se um função definida recursivamente por f e g.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Custou mais foi:

primrec' c g 0 = c
primrec' c g (n+1) = primrec' (g c (n+1)) g n

Thanks dudes!

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Custou mais foi:

primrec' c g 0 = c
primrec' c g (n+1) = primrec' (g c (n+1)) g n

Thanks dudes!

Estás a fazer batota... Isso não é equivalente à função que te foi dada. Não é o operador de recursividade primitiva.

Parece que estás a assumir que a função que te foi dada tinha um erro, quando isso não acontecia. Aquilo que tinhas mal era estares a usar a função de multiplicação directamente.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Estás a fazer batota... Isso não é equivalente à função que te foi dada. Não é o operador de recursividade primitiva.

Eu não consegui fazer de outra forma, pensando em acumuladores. :/

Parece que estás a assumir que a função que te foi dada tinha um erro, quando isso não acontecia. Aquilo que tinhas mal era estares a usar a função de multiplicação directamente.

Já percebi esta parte. Só acho um pouco estranho o facto de ter de definir uma função de multiplicação diferente só para este caso.

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Rui Carlos, já consegui fazer correctamente, acho eu:

primrec' c g 0 = c
primrec' c g (n+1) = primrec' (g c n) g n

Tenho é de, mais uma vez, definir uma função de multiplicação diferente que se adapte a este caso, para funcionar na função factorial:

factorial n = primrec' 1 (multr) n
where multr x y = x*(y+1)

0

Partilhar esta mensagem


Link para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!


Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.


Entrar Agora