TIL Avoiding Off-by-one errors and state using Recusion

POSTED ON: Jun 08, 2021

TAGS: math loops javascript

What is a off by one error? More details in this post
What is state? More details in this post

Recursion #

Recursion is a function that calls itself.

(Via Freecodecamp)[https://www.freecodecamp.org/news/what-is-recursion-in-javascript/]

Code Snippets #

Using these helpers:

// helpers
const first = xs => xs[0]
const rest = xs => xs.slice(1)

SUM:

Adding array values together

const sum = xs =>
  xs.length === 0
    ? 0
    : first(xs) + sum(rest(xs));

console.log( sum([1, 2, 3, 4, 5]) ); // 15

This is a different version using tail recursion.

It turns out we can abstract all of the details of traversing a list. The idea is simple. As we walk across a list, we store an accumulator, a value that stores some data that is important to us. For example, if we want to walk across a list of integers and sum them, we could store the current sum in the accumulator. We start with the accumulator set to 0. As we come across each new element, we add the element to the accumulator. When we reach the end, we return the value stored in the accumulator.

const tailSum = list => {
  const go = (acc, xs) =>
    xs.length === 0
      ? acc
      : go(acc + first(xs), rest(xs));
  return go(0, list)
}

console.log( tailSum([1, 2, 3, 4, 5]) ); // 15

A function that returns the value of its recursive call is said to be tail recursive. The advantage is that a tail recursive function can be compiled into a for loop. We will see exactly why later in the course, but for now just notice the following difference between the sum and sum' functions above. In the first sum function, after the recursive call returned its value, we add x to it. In the tail recursive sum', after the recursive call, we immediately return the value returned by the recursion. So in the second case, the compiler can change this recursive call into a simple goto statement. The result is that tail recursive functions tend to run faster than their standard counterparts.

This is via [cornell.edu's cs312 class](More info about Tail Recusion. The JS code is from the YDNL repo

REVERSE:

Flipping array values the other way

const reverse = xs =>
  xs.length === 0
    ? []
    : reverse(rest(xs)).concat(first(xs));

console.log( reverse([1, 2, 3, 4, 5]) ); // 5, 4, 3, 2, 1

Oddly enough, you can just do this with the built-in reverse method.🤷

console.log( [1, 2, 3, 4, 5].reverse() ); // 5, 4, 3, 2, 1

REDUCE:
Note: I couldn't get either reduce to work within the web environment.

Via the repo notes:
NOTE: Since tail call optimization is currently only supported by Safari, tail recursion may cause stack overflow in most other JavaScript environments. While others, such as the Chrome devs, appear to be discussing the subject on-and-off, you may wish to, in this case, use a loop here to compromise (and this is an example of balancing the triangle):

const reduce = (f, acc, xs) =>
  xs.length === 0
    ? acc
    : reduce(f, f(acc, first(xs)), rest(xs));


// tail recusion reduce
const tailReduce = function(reduceFn, accumulator, iterable){
  for (let i of iterable){
    accumulator = reduceFn(accumulator, i)
  }
  return accumulator
}

Via:
https://github.com/you-dont-need/You-Dont-Need-Loops#recursion

Related TILs

Tagged: math

• Next: TIL Higher Order functions to reduce loopsHigher Order Functions like Sum, Map, Filter, Reduce
• Previous: TIL Stateful and statelessAn expression in a programming language can be “stateful” or “stateless”.