How to Code Recursion in Excel

In my posting "Earth falls toward a black hole and everyone dies", I said that the science-fiction generator it describes works by traversing a story flowchart, and that the natural way to program this is by recursion. I'm now going to explain. How did I code a recursive Excel spreadsheet?

Here's an example I've written to demonstrate. The spreadsheet is here. It has three columns. The first two, headed input and output, are one row each. Type a number into input, and its factorial will appear in output.

And here is the Excelsior program I generated this spreadsheet from:

  table input : -> general.

  table output : -> general.

  output[ ] = fac[ input[] ].


  type fac_range = 0:100.

  table fac : fac_range -> general.

  fac[ 0 ] = 1.

  fac[ n>0 ] = n * fac[ n-1 ].


  layout( 'Sheet 1'
        , rows( heading
              , row( input as null
                   , output as null
                   , fac as y
                   )  
              )
        ).

The key to understanding this is that Excelsior thinks of a spreadsheet as a collection of tables. The Excelsior keyword for these is table. When Excelsior generates a spreadsheet, it maps each table onto one or more cells, as dictated by the layout statement. In this program, that statement puts fac to the right of output to the right of input, and runs fac down the sheet. Since fac has one dimension — as indicated by the type statement for fac_range, and by the table declaration for fac — that makes it occupy a single column.

The key to understanding the recursion is to think of tables as functions. Indeed, my syntax for table declarations imitates the notation used by mathematicians to specify a function's argument and result types. The two equations for fac then become analogous to the usual recursive definition of factorial.

This, clearly, is recursion. But it's laid out — spread out, you might say — in space rather than in time.

So that generates the factorials. The remaining part of the program is that which gets the right factorial from the table and puts it into the output cell. Namely, the first three statements. The first two declare the input and output cells as tables that have no subscripts, and are therefore  one cell each. The third statement uses the input as a subscript to fac, and puts the result into the output.

And that's how to program recursion in Excel.