3

There are many problems where a concise recursive algorithm is preferable over an iterative implementation. I have used recursion in Apps Script functions in the past, but would now like to find a way to use recursion in a plain vanilla Google Sheets formula.

I have tried defining a lambda() function in let(), and can call the function several times:

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

But that is reuse rather than recursion. How do I make a function in a Google Sheets formula call itself in a recursive manner?

doubleunary
  • 13,842
  • 3
  • 18
  • 51

1 Answers1

6

One easy way is to use a named function. Named functions can call themselves recursively. The documentation gives this example:

  • Function name: REVERSE_WORDS
  • Description: Reverses the word order in a string
  • Placeholders: str
  • Definition:
=if( 
  iserror(find(" ", str)), 
  str, 
  REVERSE_WORDS(right(str, len(str) - find(" ", str))) 
  & " " & 
  left(str, find(" ", str) - 1) 
)

Named functions are only available in spreadsheets where they have been added or imported. To create a stand-alone formula that does not break when you copy the formula or its tab from one spreadsheet file to another, use a lambda() instead.

The challenge is that a lambda function cannot directly refer to itself. So, to implement recursion, you need to call the lambda with itself as an argument, like this:

=let( 
  string, A2, 
  isOneWord_, lambda(s, not(regexmatch(s, " "))), 
  head_, lambda(s, regexextract(s, "^(.+?) ")), 
  tail_, lambda(s, regexextract(s, " (.*)$")), 

  reverseWords_, lambda(self, str, 
    if( 
      isOneWord_(str), 
      str, 
      self(self, tail_(str)) & " " & head_(str) 
    ) 
  ), 

  reverseWords_(reverseWords_, trim(string)) 
)

To test the formula, put a phrase like The quick brown fox jumped over the lazy dog in cell A2.

To give a couple additional often seen examples of recursion, here's a Tower of Hanoi implementation:

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

…and here's a Fibonacci implementation:

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

To get the tenth Hanoi or Fibonacci number, put 10 in cell A2.

Notes:

To ensure your recursion terminates, always put the recursive call in an if() of some sort. One of the branches must yield a value while the other calls self recursively.

Simple recursive formulas have pretty decent performance, with the hanoi_ function happily going one thousand rounds deep. The complexity of the formula affects the depth the formula can go to. The absolute depth limit of recursive functions appears to be 9999. See What factors determine the memory used in lambda functions?

More complex formulas that fork more than one copy grow exponentially. The fib_ function above will error out at 24 levels deep, for example. This appears to be caused by the ten million values limit that is also seen in mmult(). See What is the limit on array size in a google sheets formula?.

doubleunary
  • 13,842
  • 3
  • 18
  • 51
  • Impressive! The workspace available for recursion appears to be much more generous than in Excel https://techcommunity.microsoft.com/t5/excel/lambda-recursive-lists-and-understanding-recursion-limits-of/m-p/2199690 BTW I thought at first that 'self' was a keyword but (maybe obvious to others) it can be any legal name. – Tom Sharpe Mar 20 '23 at 11:17
  • Thanks. I chose `self` because it I think it is clearer than [`this`](https://en.wikipedia.org/wiki/This_(computer_programming)) when put into context. The Excel lambda article is interesting, but this question is about Google Sheets. The limits have shifted in the past and may shift in the future. – doubleunary Mar 20 '23 at 11:36
  • Nice thread. Very clear explanation. Learn something new from this post. – Harun24hr Mar 22 '23 at 02:18