Interpreting nested recursions using sum trees
Finding visual interpretations of nested recursions that predict their behaviour and present patterns among their families has been a topic of interest for the last few decades. The most prevalent technique has been to associate a n’th term of nested recursion with the number of leaves preceding the n’th node in a specially-designed “up-infinite” binary tree. In this presentation, we will briefly note the strengths and a limitation of this approach and focus more on introducing another algorithm for constructing trees to interpret their behaviours that counter this limitation. We will demonstrate its effectiveness by applying it on a few well-known families of recursions, one family with a known “up-infinite” binary tree interpretation and one without, to find another tree-interpretation and to note some interesting results and consequences.