Wikipedia describes an algorithm for the subset sum problem which runs in time $O(2^{\frac{n}{2}})$. It works by dividing the set in half once, computing all the sums in each half (cleverly presorted), negating each element in the set of sums for one of the halves, and then checking if the intersection exists, in which case there is a subset summing to $0$.
I wonder if there is a recursive version of this algorithm? The running time suggests that there could be some way of recursing on two subsets of $n - 2$ elements and performing some constant-time computation. Are there any interesting ways this algorithm can be restated recursively or otherwise?
There has been a recent series of papers improving the exponential subset algorithms (at least in the average case).
The first two paper work on a classical computer with complexity close to $2^{n/3}$, the third one on a quantum computer with complexity close to $2^{n/4}.$
Apparently the key idea is to decompose the subset sum in two halves in a less constrained way. These algorithms also use a limited form of recursivity (only a few levels).