How to curry a recursive function in ES6

Question

I was doing some functional programming practice with javascript lambda expressions and came up with the following code. The code aims to return a function that calculates given number's power of given base value. My code as follows;

const findUpper = base => (num, i = 0) => {
  if (num < base) {
    return i;
  } else {
    i++;
    return findUpper(Math.round(num / base), i);
  }
}

const findUpper2 = findUpper(2)
console.log(findUpper2(8)) //expected to have 3

The problem here is, recursion becomes broken after first findUpper call, because it returns a function.

How can I make this snippet work?

Just to show you the expressiveness of functions, take a look at the U/Y combinator — user6445533
– user6445533, Commented Nov 3, 2017 at 8:40

Jaromanda X · Accepted Answer · 2017-11-02 22:30:08Z

3

One way is like this

    var findUpper = base => {
        let fn = (num, i = 0) => {
            if (num < base) {
                return i;
            } else {
                i++;
                return fn(Math.round(num / base), i);
            }
        };
        return fn;
    }
    var findUpper2 = findUpper(2)
    console.log(findUpper2(8))

Declare the recursive function with a name inside fundUpper ... recursively call fn rather than findUpper

it's slightly "tidier" without using arrow functions needlessly

var findUpper = base => {
    return function fn(num, i = 0) {
        if (num < base) {
            return i;
        } else {
            i++;
            return fn(Math.round(num / base), i);
        }
    };
}
var findUpper2 = findUpper(2)
console.log(findUpper2(8))

Although, using => the code can be as simple as

const findUpper = base => {
    let fn = (num, i = 0) => (num < base) ? i : fn(Math.round(num / base), i + 1);
    return fn;
}

edited Nov 2, 2017 at 22:30

answered Nov 2, 2017 at 22:25

Jaromanda X

57.1k6 gold badges82 silver badges96 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Uğurcan Şengit Over a year ago

A named function makes recursion possible. You are right about not using arrow functions needlessly. Thanks!

Jaromanda X Over a year ago

by the way, I'd be more inclined, in the first and last example, to return num => fn(num); - ensuring the "validity" of i :p

Mulan Over a year ago

@UğurcanŞengit a named function is not required for recursion

Mulan · Accepted Answer · 2018-03-20 06:53:33Z

Here's your mistake

i++
return findUpper(Math.round(num / base), i);

You intended:

// don't forget, findUpper is a curried function
return findUpper(Math.round(num/base))(i + 1);

Here's another way to write your program as a pure expression

const findUpper = (base = 1) => (num = 0, exp = 0) =>
  num < base
    ? exp
    : findUpper (base) (num / base, exp + 1)
    
console.log (findUpper (2) (8))

Using generic loop/recur procedures, we keep findUpper's parameters clean, increase loop performance, and maintain the curried interface you want

const recur = (...values) =>
  ({ recur, values })
  
const loop = f =>
{
  let acc = f ()
  while (acc && acc.recur === recur)
    acc = f (...acc.values)
  return acc
}

const findUpper = (base = 1) => (num = 0) =>
  loop ((n = num, exp = 0) =>
    n < base
      ? exp
      : recur (n / base, exp + 1))

console.log (findUpper (2) (8))

Collectives™ on Stack Overflow

How to curry a recursive function in ES6

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related