A Little Recursion Refresher

Recursion is the bread and butter tool of every proper functional programmer. Here is a brief refresher about its major forms:

// body recursion

const mapRec = f => ([x, ...xs]) =>
  x === undefined
    ? []
    : [f(x), ...mapRec(f) (xs)];

// tail recursion

const mapTRec = f => ([x, ...xs], acc = []) =>
  x === undefined
    ? acc
    : mapTRec(f) (xs, acc.concat(f(x)));

// recursion in continuation passing style

const mapCPS = f => ([x, ...xs]) => k =>
  x === undefined
    ? k([])
    : mapCPS(f) (xs) (ys => k([f(x), ...ys]));

const sqr = x => x * x;
const id = x => x;

mapRec(sqr) ([1,2,3]); // [1,4,9]
mapTRec(sqr) ([1,2,3]); // [1,4,9]
mapCPS(sqr) ([1,2,3]) (id); // [1,4,9]

Actually there is still tail recursion modulo cons, mutual recursion, monad recurison, corecursion etc.

Learn more about recursion and trampolining at my course.