Pointwise order of generalized Hofstadter functions G, H and beyond

Pierre Letouzey, Shuo Li, Wolfgang Steiner

Hofstadter's G function is recursively defined via $G(0)=0$ and then $G(n)=n-G(G(n-1))$. Following Hofstadter, we vary the number $k$ of nested recursive calls in this equation and…