Hi,
Let's observe the following list: 1,2,3,4.
Our possible routes are: 1->2->3->4, 1->4, 1->2->4, 1->3->4. Thus we will compute in our naive recursion solution 3->4 twice, meaning we will initialize 2 recursive functions rather than just one.
From the lectures we may recall the following:
"For this reason, we will also introduce techniques to get rid of recursion…"
"This is highly wasteful and causes a huge overhead." (computing values over and over)
"The technique of storing values instead of re-computing them has different names in different contexts: It is known as memorization…"
Furthermore, from Wikipedia:
"n computing, memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again."