recursion and corecursion

scala

Recursion consumes data whereas corecursion produces data. Corecursion can be used with laziness feature to implement infinite data structures.

Recursion starts from the original parameter, call itself until it reaches a base case. It’s from up to bottom.

Corecursion works the opposite. It starts from an initial state and transform the state to build next value and continues the transformation step by one step. It’s from bottom to up. Corecursion is more like we define math theory. e.g. for fibonacci number,

f(0) = 0 // initial state
f(1) = 1 // initial state
f(n) = f(n-1) + f(n-2) // induction

Recursion fib

def fib(n: Int): Int = n match {
	case _ if n <= 1 => n  // base case
	case _ => fib(n-1) + fib(n-2) // decrease n step by step
}

Corecursion fib

def fib(n: Int): Int = {
  def transform(state: (Int, Int), n: Int): (Int, Int) = {
    if (n < 1) state
    else transform((state._2, state._1 + state._2), n - 1)
  }
  transform((0, 1), n)._1
}

Above is not an evident corecursion implementation. If we have a lazy list Stream[+A] defined. We can write the implementation as below.

def cons(h: => A, t: => Stream[A]): Stream[A] = ???

// fib is corecursive, cons is a stream constructor with lazy parameter
def fib(a:Int, b: Int): Stream[Int] = cons(a, fib(b, a + b))

def fibnacci(n: Int): Int = fib(0, 1).take(n).toList.last
Support me