Qual é a diferença entre recursão e corecursão?

51

Qual é a diferença entre estes?

Na Wikipédia, há poucas informações e nenhum código claro que explique esses termos.

Quais são alguns exemplos muito simples que explicam esses termos?

Como a corecursão é o dual da recursão?

Existem algoritmos corecusivos clássicos?

    
por user167908 13.04.2012 / 11:54
fonte

4 respostas

20

Existem várias maneiras de ver isso. O mais fácil para mim é pensar sobre a relação entre "indutivo" e "definições co-indutivas"

Uma definição indutiva de um conjunto é assim.

O conjunto "Nat" é definido como o menor conjunto tal que "Zero" está em Nat, e se n está em Nat "Succ n" está em Nat.

Qual corresponde ao seguinte Ocaml

type nat = Zero | Succ of nat

Uma coisa a notar sobre essa definição é que um número

omega = Succ(omega)

não é um membro deste conjunto. Por quê? Suponha que era, agora considere o conjunto N que tem todos os mesmos elementos que Nat, exceto que ele não tem ômega. Claramente Zero está em N, e se y está em N, Succ (y) está em N, mas N é menor que Nat, o que é uma contradição. Então, o ômega não está em Nat.

Ou talvez mais útil para um cientista da computação:

Dado algum conjunto "a", o conjunto "Lista de um" é definido como o menor conjunto tal que "Nil" está em Lista de um, e que se xs está em Lista de a e x está em um "Cons x xs" está na lista de um.

Que corresponde a algo como

type 'a list = Nil | Cons of 'a * 'a list

A palavra operativa aqui é "menor". Se não disséssemos "menor", não teríamos como dizer se o conjunto Nat continha uma banana!

Mais uma vez,

zeros = Cons(Zero,zeros)

não é uma definição válida para uma lista de nats, assim como o omega não era um Nat válido

Definir dados indutivamente assim nos permite definir funções que funcionam com

let rec plus a b = match a with
                   | Zero    -> b
                   | Succ(c) -> let r = plus c b in Succ(r)

podemos então provar fatos sobre isso, como "mais um Zero = a" usando indução (especificamente, indução estrutural)

Nossa prova procede por indução estrutural em um. Para o caso base, deixe um zero. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r) , então sabemos plus Zero Zero = Zero . Deixe a ser um nat. Assuma a hipótese indutiva de que plus a Zero = a . Agora mostramos que plus (Succ(a)) Zero = Succ(a) é óbvio, pois plus (Succ(a)) Zero = match a with |Zero -> Zero | Succ(a) -> let r = plus a Zero in Succ(r) = let r = a in Succ(r) = Succ(a) Assim, por indução plus a Zero = a para todo a in nat

Podemos, claro, provar coisas mais interessantes, mas essa é a ideia geral.

Até agora, lidamos com dados definidos indutivamente , o que conseguimos com o conjunto "menor". Então, agora queremos trabalhar com codata coindutivamente definida, o que conseguimos ao permitir que seja o maior conjunto.

Então

Deixe um ser um conjunto. O conjunto "Fluxo de um" é definido como o maior conjunto tal que para cada x no fluxo de a, x consiste no par ordenado (cabeça, cauda) tal que a cabeça está em um e cauda está em Fluxo de um

Em Haskell, nós expressamos isso como

data Stream a = Stream a (Stream a) --"data" not "newtype"

Na verdade, em Haskell usamos normalmente as listas internas, que podem ser um par ordenado ou uma lista vazia.

data [a] = [] | a:[a]

Banana também não é membro desse tipo, pois não é um par ordenado ou uma lista vazia. Mas agora podemos dizer

ones = 1:ones

e esta é uma definição perfeitamente válida. Além do mais, podemos realizar co-recursão nesses co-dados. Na verdade, é possível que uma função seja co-recursiva e recursiva. Embora a recursão tenha sido definida pela função que possui um domínio que consiste em dados, a co-recursão significa apenas que possui um co-domínio (também chamado de intervalo) que é co-dados . A recursão primitiva significava sempre "chamar a si mesmo" em dados menores até alcançar alguns dados menores. Co-recursão primitiva sempre "chama a si mesma" em dados maiores ou iguais ao que você tinha antes.

ones = 1:ones

é primitivamente co-recursivo. Enquanto a função map (como "foreach" em linguagens imperativas) é primitivamente recursiva (tipo de) e primitivamente co-recursiva.

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = (f x):map f xs

O mesmo vale para a função zipWith , que pega uma função e um par de listas e as combina usando essa função.

zipWith :: (a -> b -> c) -> [a] -> [b] -> [c]
zipWith f (a:as) (b:bs) = (f a b):zipWith f as bs
zipWith _ _ _           = [] --base case

o exemplo clássico de linguagens funcionais é a seqüência de Fibonacci

fib 0 = 0
fib 1 = 1
fib n = (fib (n-1)) + (fib (n-2))

que é primitivamente recursivo, mas pode ser expresso de forma mais elegante como uma lista infinita

fibs = 0:1:zipWith (+) fibs (tail fibs)
fib' n = fibs !! n --the !! is haskell syntax for index at

um exemplo interessante de indução / co-indução está provando que essas duas definições computam a mesma coisa. Isso é deixado como um exercício para o leitor.

    
por 14.04.2012 / 06:27
fonte
7

Basicamente, a corecursão é recursão estilo acumulador , construindo seu resultado no caminho a seguir a partir do caso inicial, enquanto a recursão regular constrói seu resultado no caminho de volta a partir do caso base.

(falando Haskell agora). É por isso que foldr (com uma função de combinação estrita) expressa recursão, e foldl' (com combos restritos. F.) / scanl / until / iterate / unfoldr / etc. express corecursion. A corecursão está em toda parte. foldr com pente não estrito. f. expressa contras modulo de recursão da cauda .

A recursão protegida de Haskell é como módulos de recursão da cauda .

Isso é recursivo:

fib n | n==0 = 0
      | n==1 = 1
      | n>1  = fib (n-1) + fib (n-2)

fib n = snd $ g n
  where
    g n | n==0 = (1,0)
        | n>0  = let { (b,a) = g (n-1) } in (b+a,b)

fib n = snd $ foldr (\_ (b,a) -> (b+a,b)) (1,0) [n,n-1..1]

(leia $ como "de"). Esta é a corecursão:

fib n = g (0,1) 0 n where
  g n (a,b) i | i==n      = a 
              | otherwise = g n (b,a+b) (i+1)

fib n = fst.snd $ until ((==n).fst) (\(i,(a,b)) -> (i+1,(b,a+b))) (0,(0,1))
      = fst $ foldl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst $ last $ scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..n]
      = fst (fibs!!n)  where  fibs = scanl (\(a,b) _ -> (b,a+b)) (0,1) [1..]
      = fst (fibs!!n)  where  fibs = iterate (\(a,b) -> (b,a+b)) (0,1)
      = (fibs!!n)  where  fibs = unfoldr (\(a,b) -> Just (a, (b,a+b))) (0,1)
      = (fibs!!n)  where  fibs = 0:1:map (\(a,b)->a+b) (zip fibs $ tail fibs)
      = (fibs!!n)  where  fibs = 0:1:zipWith (+) fibs (tail fibs)
      = (fibs!!n)  where  fibs = 0:scanl (+) 1 fibs
      = .....

Dobras: link

    
por 02.05.2013 / 13:44
fonte
3

Verifique isso em blog de Vitomir Kovanovic . Eu achei isso no ponto:

Lazy evaluation in one very nice feature found in programming languages with functional programming capabilities such as lisp, haskell, python etc. It mans that evaluation of variable value is delayed to the actual usage of that variable.

It means that for example if you wanted to create a list of million elements with something like this (defn x (range 1000000)) it is not actually created, but it is just specified and when you really use that variable for the first time, for instance when you want 10th element of that list interpreter creates only first 10 elements of that list. So the first run of (take 10 x) actually creates these elements and all subsequent calls to the same function are working with already existing elements.

This is very useful because you can create infinite lists without out of memory errors.The list will be large just how much you requested. Of course, if your program is working with large data collections it can hit memory limit in the usage of these infinite lists.

On the other hand corecursion is dual to recursion. What this means? Well just like the recursive functions, which are expressed in the terms of themselves, corecursive variables are expressed in the terms of themselves.

This is best expressed on the example.

Let’s say we want list of all prime numbers...

    
por 13.04.2012 / 13:24
fonte
2

Aqui está uma série de slides que dão uma resposta bastante clara.

De acordo com essas notas, uma definição corecursiva é semelhante a uma definição recursiva, exceto que ela não possui um caso base.

    
por 13.04.2012 / 13:48
fonte