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](https://stackoverflow.com/a/43195580/6445533) — , Nov 03 '17 at 08:40

Jaromanda X · Accepted Answer · 2017-11-02T22:30:08.973

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 02 '17 at 22:30

answered Nov 02 '17 at 22:25

Jaromanda X

53,868
5
73
87

A named function makes recursion possible. You are right about not using arrow functions needlessly. Thanks! – Uğurcan Şengit Nov 02 '17 at 22:29
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 – Jaromanda X Nov 02 '17 at 22:42
@UğurcanŞengit a named function is not required for recursion – Mulan Nov 03 '17 at 22:34

Mulan · Answer 2 · 2018-03-20T06:53:33.077

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))

How to curry a recursive function in ES6

2 Answers2