如何在 Google Sheets 公式中实现递归？

Question

在许多问题中，简洁的递归算法优于迭代实现。我过去曾在 Apps 脚本函数中使用过递归，但现在想找到一种在普通 Google Sheets 公式中使用递归的方法。

我尝试lambda()在 中定义一个函数let()，并且可以多次调用该函数：

=let( 
  fn_, lambda(v, v + 42), 
  x, fn_(1), 
  y, fn_(2), 
  z, fn_(3), 
  { x, y, z } 
)

但这是重用而不是递归。如何使 Google 表格公式中的函数以递归方式调用自身？

Answer 1

一种简单的方法是使用命名函数。命名函数可以递归地调用自身。文档给出了这个例子：

\n

\n
• 函数名称： REVERSE_WORDS
\n
• 描述： Reverses the word order in a string
\n
• 占位符： str
\n
• 定义：
\n

\n

=if( \n  iserror(find(" ", str)), \n  str, \n  REVERSE_WORDS(right(str, len(str) - find(" ", str))) \n  & " " & \n  left(str, find(" ", str) - 1) \n)\n

\n

命名函数仅在已添加或导入的电子表格中可用。要创建一个在将公式或其选项卡从一个电子表格文件复制到另一个电子表格文件时不会中断的独立公式，请改用lambda()。

\n

挑战在于 lambda 函数不能直接引用自身。因此，要实现递归，您需要使用 lambda 本身作为参数来调用，如下所示：

\n

=let( \n  string, A2, \n  isOneWord_, lambda(s, not(regexmatch(s, " "))), \n  head_, lambda(s, regexextract(s, "^(.+?) ")), \n  tail_, lambda(s, regexextract(s, " (.*)$")), \n\n  reverseWords_, lambda(self, str, \n    if( \n      isOneWord_(str), \n      str, \n      self(self, tail_(str)) & " " & head_(str) \n    ) \n  ), \n\n  reverseWords_(reverseWords_, trim(string)) \n)\n

\n

要测试公式，请输入类似The quick brown fox jumped over the lazy dogin cell 的短语A2。

\n

举几个常见的递归示例，这里是汉诺塔的实现：

\n

=let( \n  towerHeight, A2, \n  hanoi_, lambda( \n    self, n, \n    if(n < 2, n, 2 * self(self, n - 1) + 1) \n  ), \n  hanoi_(hanoi_, towerHeight) \n)\n

\n

\xe2\x80\xa6 这里是斐波那契实现：

\n

=let( \n  ordinal, A2, \n  fib_, lambda( \n    self, n, \n    if(n < 2, n, self(self, n - 1) + self(self, n - 2)) \n  ), \n  fib_(fib_, ordinal) \n)\n

\n

要获得第十个河内数或斐波那契数，请将其放入10单元格中A2。

\n

笔记：

\n

为了确保递归终止，请始终将递归调用置于if()某种类型中。其中一个分支必须产生一个值，而另一个分支则self递归调用。

\n

简单的递归公式具有相当不错的性能，该hanoi_函数可以愉快地进行一千轮深度。公式的复杂程度影响公式可以达到的深度。递归函数的绝对深度限制似乎是 9999。请参阅哪些因素决定 lambda 函数中使用的内存？

\n

分叉多个副本的更复杂的公式呈指数级增长。fib_例如，上面的函数将在 24 层深度处出错。这似乎是由 1000 万值限制引起的，该限制也出现在 中mmult()。请参阅谷歌表格公式中数组大小的限制是什么？。

\n