从非递归函数生成递归函数

六月 12, 2020

递归在现代的语言中是一个很常见的特性，它可以把问题分解成规模更小的相似问题逐步解决。尤其是在函数式编程语言中，没有循环语句，所有的迭代操作都会由递归来完成。但是如果有一天被大卡车撞了，穿越到了递归函数不存在的世界，应该要怎么样实现相同的效果呢？

Y Combinator

function factorial(n) {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

年轻人的第一个递归，阶乘函数。下面把它改写成箭头函数。

n => {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * /* ??? */;
}

很快就遇到了问题，因为我们没有给这个箭头函数绑定变量，所以在递归调用的地方不知道应该写什么了。这就是接下来的任务：把不能递归的函数变得可以递归。既然在这个地方找不到 factorial 函数了，那就创造一个。在箭头函数中，唯一可能得到这个函数的地方就是参数了，因此先加上一个参数，每次调用的时候把 factorial 传递进来就可以了

const recursive = fn => (...args) => fn(fn, ...args);

recursive((fn, n) => {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * fn(fn, n - 1);
});

因为函数的参数变为了两个，第 7 行变为了 fn(fn, n - 1)。这可太丑了，在写函数的时候每次都要把自己作为第一个参数写进来，正经的人是不会写出这样的代码的。理想情况中，这里仍应保持 fn(n - 1) 的形式。所以 recursive 函数还应该继续改进。

const recursive = fn => (...args) => fn(fn, ...args);
//                                      ~~

这个位置的参数显然不应该是 fn 了，它应该是一个 (...args) => ReturnValue 类型的函数 X。但是目前的作用域中只有 fn, args，显然它们以及它们的直接组合都不是 X 合适的候选项。因此设 X 为 x(?) 的形式。这里需要继续引入新的变量，考虑和前面引入递归函数时相同，把 x 放在函数的参数里面。为了不改变返回值的类型，写为 IIFE 的形式。

const recursive = fn =>
  (x => (...args) => fn(x(?), ...args)
//                        ~
  )(x_);
//  ~~

这样又引入了两个未知的变量，调用 x 的参数 ?，以及传递给 x 的值 x_。首先来找 x_ 的取值。根据上面的叙述，x 应该是一个返回 (...args) => fn(x(?), ...args) 的函数，所以需要找到一个 ?? => (...args) => fn(x(?), ...args) 形式的函数。而神奇的是，第 2 行不就恰好是这样一个函数吗？令 x_ = x => (...args) => fn(x(?), ...args 得到

const recursive = fn =>
  (x => (...args) => fn(x(?), ...args))
  (x => (...args) => fn(x(?), ...args));

然后就只剩下 x 的参数 ? 了。综合上面的结果可以得到 x 的形式是 x => (...args) => fn(x(?), ...args)。而 x(?) 是 (...args) => fn(x(?), ...args)。那么显然 ? 就是 x 本身。所以

const recursive = fn =>
  (x => (...args) => fn(x(x), ...args))
  (x => (...args) => fn(x(x), ...args));

简化成 $ \lambda $ 表达式的形式就是（通过 $ \eta $ 转换去掉 args）

$$ \lambda f.(\lambda x.f(x ~ x))(\lambda x.f(x ~ x)) $$

这就是 Y Combinator。为了看起来更加「函数式」，把 Y 函数进行柯里化，并且限定 args 只接受一个参数。

const Y = fn =>
  (x => arg => fn(x(x))(arg))
  (x => arg => fn(x(x))(arg))

回到最初的函数，使用 Y Combinator 构造递归函数

const factorial = Y(fn => n => {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * fn(n - 1);
});

$ console.log(factorial(5))
> 120

上面的 $ \lambda $ 表达式通过 $ \eta $ 转换去掉了 args，如果在 JavaScript 代码中也执行相同的操作会？

const Y = fn =>
  (x => fn(x(x)))
  (x => fn(x(x)))

const factorial = Y(fn => n => {
  if (n === 0 || n === 1) {
    return 1;
  }
  return n * fn(n - 1);
});

> Uncaught RangeError: Maximum call stack size exceeded

在调用 Y 生成递归函数的时候直接爆栈了。模拟运行一下调用 Y 的过程。根据 JavaScript 的运行逻辑，传入参数 fn 以后，首先执行 IIFE，将 x => fn(x(x)) 传入 x => fn(x(x))，计算 fn 中的参数 x(x)。代换以后得到 (x => fn(x(x)))(x => fn(x(x)))。很好，又整回去了 ╮(╯▽╰)╭。这个过程会无限地重复下去，最后爆栈。

Thunk

再来看一个递归函数的例子，求一个数是否为偶数。

const isEven = Y(fn => n => {
  if (n === 0) {
    return true;
  }
  return !isEven(n - 1);
});

然后来尝试一下

$ isEven(114514)
> RangeError: Maximum call stack size exceeded

又爆栈了，因为栈深度是 $ O(n) $ 的，数字比较大的时候就会直接爆栈。这里就想到了尾递归优化，当递归调用的语句是函数中的最后一个语句时，编译器将栈深度优化为 $ O(1) $。在这个例子中，计算完 isEven(n - 1) 后还需要对结果取反，所以实际上递归调用是倒数第二条语句，因此改进代码。

const isEven = Y(fn => n => {
  if (n === 0) {
    return true;
  }
  if (n === 1) {
    return false;
  }
  return isEven(n - 2);
});

但是等一下，一个连递归函数都没有的异世界怎么会有尾递归优化的编译器呢？（什么？现实世界的 JavaScript 引擎也不支持？那没事了）很快就能想到，我们可以像前面给 Y Combinator 添加 args 参数一样，推迟函数调用的时机，这样就不会爆栈了。

const Thunk = fn => ({ get: () => fn() });

const trampoline = fn => {
  let value = fn();

  while (typeof value.get === 'function') {
    value = value.get();
  }

  return value;
};

const isEven = trampoline(
  Y(fn => n => {
    if (n === 0) {
      return true;
    }
    if (n === 1) {
      return false;
    }
    return Thunk(() => fn(n - 2));
  })
);

$ isEven(114514)
> true

这里又有了一个同样的问题，isEven 的函数里面写了 Thunk，这个优化对于函数本身是不透明的，正经人是不会写这种代码的。所以要尝试吧 Thunk 从函数里面取出来。这就意味着，当我们调用 fn(n - 2) 的时候，返回的值不是 isEven(n - 2)，而是 Thunk^m(isEven(n - 2))。再回到 Y 函数

const Y = fn =>
  (x => arg => fn(x(x))(arg))
  (x => arg => fn(x(x))(arg))

也就是说我们需要修改 x(x)。我们知道 x(x) 是一个函数，所以可以转换成 brg => x(x)(brg)。把返回值变为 Thunk，得到 brg => Thunk(() => x(x)(brg))

const recursive = fn =>
  (x => arg => fn(brg => Thunk(() => x(x)(brg)))(arg))
  (x => arg => fn(brg => Thunk(() => x(x)(brg)))(arg))

因为函数和参数相同，简化得到

const recursive = fn =>
  (m => m(m))
  (x => arg => fn(brg => Thunk(() => x(x)(brg)))(arg))

最后再将计算的结果从 Thunk 中取出即可

const recursive = fn => fnArg => {
  let value = (m => m(m))
    (x => arg => fn(brg => Thunk(() => x(x)(brg)))(arg))
    (fnArg);
  while (typeof value.get === 'function') {
    value = value.get();
  }
  return value;
}

再来试一下

const isEven = recursive(
  fn => n => {
    if (n === 0) {
      return true;
    }
    if (n === 1) {
      return false;
    }
    return fn(n - 2);
  }
);

$ isEven(114514)
> true

很好，现在就可以在递归函数里面使用尾递归优化了。可是既然有循环语句了，为什么还要用递归呢？(￣ε(#￣)☆╰╮o(￣皿￣///)

参考文献

Paulson, L. C., Foundations of functional programming, University of Cambridge, 1995.
R. Braithwaite, “Why Y? Deriving the Y Combinator in JavaScript
“, Raganwald, 2018.

查看评论