###### tags: `one-offs` `trees`

# Recursive Algorithms and Trees

**Overview**: In this note, I describe how many sequential algorithms can readily be adapted to operate on tree-structured systems, and describe some speculative generalisations and applications.

## Chains Are Just The Simplest Trees

At various stages, I have been prompted to think about the abstract nature of recursive algorithms, since they eventually show up in so many computational disciplines. One very nice point which has stuck with me is that even though lots of recursive algorithms are primarily used for sequential tasks, they can typically be extended to tree-based problems without much difficulty.

Some familiar examples of this are the Kalman filter and the Forward-Backward algorithm, which are both formulated for different kinds of state-space models, but each make sense for general tree graphs, once you rewrite them as an instance of belief propagation. A slightly more esoteric / surprising instance of this is the work on ['Divide-and-Conquer SMC'](https://arxiv.org/abs/1406.4993), which highlights quite nicely that the essence of SMC is about recursion, rather than sequential structure.

Inspired by this, one challenge is then to identify other sequential algorithms which are fundamentally recursive, and understand what it might mean to extend them to tree-structured problems (and whether it might make sense to apply them to general graph structures anyways, c.f. loopy BP).

One challenge which I am yet to crack is whether this procedure is relevant to the study of Quasi-Newton optimisation methods. My thinking is that it doesn't quite make sense for the path itself - the $x$s are updated iteratively, rather than recursively - but it may be reasonable for understanding the Hessian estimates, which are essentially treated recursively.

One current barrier (among many) is that I'm unsure of how one should 'optimally' enact the update

\begin{align}
\left\{ \widehat{\mathrm{Hessian}}\left(x_{s}\right):s<t\right\} \mapsto\widehat{\mathrm{Hessian}}\left(x_{t}\right),
\end{align}

in the abstract setting. I'm not sure whether this will ever work out neatly (though I would certainly like it to!), but I do think that it's a fun idea. It's all very speculative, but I would like to resolve it one day, in some form or another.