In Chapter 2, Getting Started with Functional Programming, in the section, Recursion, we cover recursion extensively (albeit there are recursion topics that are outside the scope of this book).

We used recursion to write classic algorithms such as Fibonacci (we're reusing tailrecFib from Chapter 2, Getting Started with Functional Programming):

fun tailrecFib(n: Long): Long {
   tailrec fun go(n: Long, prev: Long, cur: Long): Long {
      return if (n == 0L) {
         prev
      } else {
         go(n - 1, cur, prev + cur)
      }
   }

   return go(n, 0, 1)
}

And Factorial (same here, reusing tailrecFactorial from Chapter 2, Getting Started with Functional Programming):

fun tailrecFactorial(n: Long): Long {
   tailrec fun go(n: Long, acc: Long): Long {
      return if (n <= 0) {
         acc
      } else {
         go(n - 1, n * acc)
      }
   }

   return go(n, 1)
}

In both cases, we started with a number, and we reduced it to reach a base condition.

Another example that we looked at was FunList:

sealed class FunList<out T> {
   object Nil : FunList<Nothing>()

   data class Cons<out T>(val head: T, val tail: FunList<T>) : FunList<T>()

   fun forEach(f: (T) -> Unit) {
      tailrec fun go(list: FunList<T>, f: (T) -> Unit) {
         when (list) {
            is Cons -> {
               f(list.head)
               go(list.tail, f)
            }
            is Nil -> Unit//Do nothing
         }
      }

      go(this, f)
   }

   fun <R> fold(init: R, f: (R, T) -> R): R {
      tailrec fun go(list: FunList<T>, init: R, f: (R, T) -> R): R = when (list) {
         is Cons -> go(list.tail, f(init, list.head), f)
         is Nil -> init
      }

      return go(this, init, f)
   }

   fun reverse(): FunList<T> = fold(Nil as FunList<T>) { acc, i -> Cons(i, acc) }

   fun <R> foldRight(init: R, f: (R, T) -> R): R = this.reverse().fold(init, f)

   fun <R> map(f:(T) -> R): FunList<R> = foldRight(Nil as FunList<R>){ tail, head -> Cons(f(head), tail) }

}

The functions, forEach and fold, are recursive. Starting with the complete list, we reduce it until we reach the end (represented with a Nil), the base case. The other functions—reverse, foldRight, and map are just using fold with different variations.

So, on one hand, recursion takes a complex value and reduces it to the desired answer and on the other hand, corecursion takes a value and builds on top of it to produce a compound value (including potentially infinite data structures such as Sequence<T>).

As we use a fold function for recursive operations, we can use an unfold function:

fun <T, S> unfold(s: S, f: (S) -> Pair<T, S>?): Sequence<T> {
   val result = f(s)
   return if (result != null) {
      sequenceOf(result.first) + unfold(result.second, f)
   } else {
      sequenceOf()
   }
}

The unfold function takes two parameters, an initial S value that represents the starting or base step, and an f lambda that takes that S step and produces a Pair<T, S>? (a nullable Pair) of the T value to add to the sequence and the next S step. 

If the result of f(s) is null, we return an empty sequence, else we create a single value sequence and add the result of unfold with the new step.

Using unfold, we can create a function that repeats a single element many times:

fun <T> elements(element: T, numOfValues: Int): Sequence<T> {
   return unfold(1) { i ->
      if (numOfValues > i)
         element to i + 1
      else
         null
   }
}

fun main(args: Array<String>) {
   val strings = elements("Kotlin", 5)
   strings.forEach(::println)
}

The elements function takes the element to repeat any number of values. Internally, it uses unfold, passing 1 as the initial step and a lambda that takes the current step and compares it with numOfValues, returning Pair<T, Int> with the same element and the current step + 1 or null.

It is okay, but not very interesting. What about returning a Factorial sequence? We have you covered:

fun factorial(size: Int): Sequence<Long> {
   return sequenceOf(1L) + unfold(1L to 1) { (acc, n) ->
      if (size > n) {
         val x = n * acc
         (x) to (x to n + 1)
      } else
         null
   }
}

Same principle, the only difference is that our initial step is Pair<Long, Int> (the first element to carry the calculation and the second to evaluate against size) and therefore, our lambda should return Pair<Long, Pair<Long, Int>>.

Fibonacci will look similar:

fun fib(size: Int): Sequence<Long> {
   return sequenceOf(1L) + unfold(Triple(0L, 1L, 1)) { (cur, next</span>, n) ->
      if (size > n) {
         val x = cur + next
         (x) to Triple(next, x, n + 1)
      }
      else
         null
   }
}

Except that in this case, we use Triple<Long, Long, Int>.

The corecursive implementations to generate Factorial and Fibonacci sequences are a mirror of the recursive implementations to calculate a Factorial or a Fibonacci number, respectively—and some people can argue that is easier to understand.