It's fine, Simon Espigolé . I know life gets in the way sometimes, I just wanted to check if you wrote it somewhere else. I enjoyed this article by the way, some good content and insights here. Thank you for sharing that!

I actually won't go into details about Postgres FTS functions here, but I will add a link to another blog post (which I'm almost done writing) later. Not sure if you forgot to add the link or didn't write the other blog post. Would be nice though to leave the link if you did write that blog post.

The order of the old implementation is not O(n^3) it's O(3^n) as you branch 3 times for each call, and you have total n different cases, so it's 3 * 3 * 3 * 3 ... n times which is 3^n.

The complexity of the provided solution is exponential, because you branch 3 times in each recursive call, the complexity is about O(3^n) wich is very bad and will not scale at all for any large N. A very simple fix is using memoization. You can change the function a bit to accept the nber of remaining steps, in that case you can think about it as "what's the possible ways to solve x steps" that way you can save the solution to that x in a global map (would be a closure in a real world app) and when you enter the function you check if you already know the solution to x, you just return the value. Pretty much like memoizing the calculation of Fibonacci numbers.

You did some good work there, but I have a comment, in most of your code you place the curly braces opening "{" wrongly, they cannot be on a new line due to some compiler limitations, you need to place them on the same line as the declared function or struct. Most of the provided code as it is now won't even compile.