DEV Community 👩‍💻👨‍💻

Iven Marquardt
Iven Marquardt

Posted on

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.

Top comments (0)

Take Your Github Repository To The Next Level

Take Your Github Repository To The Next Level 🚀️: A step-by-step guide on creating the perfect Github repository.