## Sunday, 26 January 2014

### 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'
, 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.