My generic advice here is that if you want recursion to be fast (in any language), you should ideally enlarge the base case (“coarsen” the recursion) — see this comment.
(That being said, maybe with memo-ization here you won’t call the trivial base cases enough to matter?)