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

Qual a diferença entre estes?

• Recursão
• Corecursão

Na Wikipedia, há pouca informação e nenhum código claro explicando 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?

Existem várias maneiras boas de ver isso. O mais fácil para mim é pensar na relação entre "definições indutivas" e "definições coindutivas"

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

O conjunto "Nat" é definido como o menor conjunto, de modo que "Zero" esteja em Nat e, se n estiver em Nat, "Succ n" estará em Nat.

Que 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 sim, agora considere o conjunto N que possui todos os mesmos elementos que Nat, exceto que ele não possui ô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á no Nat.

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

Dado um conjunto "a", o conjunto "Lista de a" é definido como o menor conjunto, de forma que "Nil" esteja na Lista de a, e que se xs estiver na Lista de aex esteja em "Contras x xs" está na lista de a.

O 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 saber se o conjunto Nat continha uma banana!

Novamente,

zeros = Cons(Zero,zeros)

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

Definir dados indutivamente como este nos permite definir funções que funcionam com recursão

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

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

Nossa prova procede por indução estrutural em a.
Para o caso base, seja zero. plus Zero Zero = match Zero with |Zero -> Zero | Succ(c) -> let r = plus c b in Succ(r)então nós sabemos plus Zero Zero = Zero. Seja aum nat. Assuma a hipótese indutiva de que plus a Zero = a. Vamos agora mostrar que plus (Succ(a)) Zero = Succ(a)isso é óbvio desde 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 = apara todos aem nat

É claro que podemos provar coisas mais interessantes, mas essa é a ideia geral.

Até agora, lidamos com dados definidos indutivamente , obtendo-os por ser o conjunto "menor". Então, agora queremos trabalhar com coinductivly definidos CODATA qual obtemos por deixá-lo ser o maior conjunto.

assim

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

Em Haskell, expressaríamos 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 é um membro desse tipo, pois não é um par ordenado ou a lista vazia. Mas agora podemos dizer

ones = 1:ones

e esta é uma definição perfeitamente válida. Além disso, 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 ele possui um co-domínio (também chamado de intervalo) que é co-dados. Recursão primitiva significava sempre "chamar a si mesmo" em dados menores até alcançar alguns dados menores. A co-recursão primitiva sempre "se chama" em dados maiores ou iguais aos que você possuía antes.

ones = 1:ones

é primitivamente co-recursivo. Enquanto a função map(como "foreach" em linguagens imperativas) é primitivamente recursiva (mais ou menos) 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 zipWithque pega uma função e um par de listas e os 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 sequê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 maneira 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 / coindução está provando que essas duas definições calculam a mesma coisa. Isso é deixado como um exercício para o leitor.

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

(falando Haskell agora). É por isso que foldr(com uma função de combinação estrita) expressa recursão e (com uma combinação foldl'estrita de f.) / scanl/ until/ iterate/ unfoldr/ Etc. expressa corecursão. Corecursão está em toda parte. foldrcom pente não estrito. f. expressa recursão da cauda módulo contras .

E a recursão guardada de Haskell é como contras de módulo de recursão da cauda .

Isso é recursão:

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"). Isso é 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: http://en.wikipedia.org/wiki/Fold_(higher-order_function)

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

Avaliação preguiçosa em um recurso muito interessante encontrado em linguagens de programação com recursos de programação funcional, como lisp, haskell, python etc. Ele considera que a avaliação do valor da variável é adiada para o uso real dessa variável.

Isso significa que, por exemplo, se você deseja criar uma lista de milhões de elementos com algo assim, (defn x (range 1000000))ele não é realmente criado, mas é apenas especificado e quando você realmente usa essa variável pela primeira vez, por exemplo, quando deseja o 10º elemento de esse intérprete de lista cria apenas os 10 primeiros elementos dessa lista. Portanto, a primeira execução de (leva 10 x) realmente cria esses elementos e todas as chamadas subsequentes para a mesma função estão trabalhando com elementos já existentes.

Isso é muito útil porque você pode criar listas infinitas sem erros de falta de memória. A lista será grande quanto você solicitou. Obviamente, se o seu programa estiver trabalhando com grandes coleções de dados, poderá atingir o limite de memória no uso dessas listas infinitas.

Por outro lado, a corecursão é dual à recursão. O que isto significa? Bem, assim como as funções recursivas, que são expressas em termos de si mesmas, as variáveis ​​corecursivas são expressas em termos de si mesmas.

Isso é melhor expresso no exemplo.

Digamos que queremos uma lista de todos os números primos ...