New answers tagged recursion
2
There's actually two questions here!
The transformation you ask about is called the tupling transformation. Basically, if your recursive calls follow a fixed pattern of overlap, a memo-table can be turned into some extra arguments (as in the fibonacci function)
For references, see
Zhenjiang Hu, Hideya Iwasaki, Masato Takeichi, Cheap Tupling Transformation
...
Top 50 recent answers are included