[HN Gopher] Show HN: Python Recursion: A Trampoline from the Mut...
       ___________________________________________________________________
        
       Show HN: Python Recursion: A Trampoline from the Mutual Head to
       the...
        
       Author : skielcast
       Score  : 18 points
       Date   : 2023-05-26 19:45 UTC (3 hours ago)
        
 (HTM) web link (elc.github.io)
 (TXT) w3m dump (elc.github.io)
        
       | skielcast wrote:
       | Last week I published this article about recursion in Python and
       | wanted to share to gather feedback
        
       | tokyolights2 wrote:
       | My biggest insight about recursion came in my graduate algorithms
       | course. I had a great professor who was talking about dynamic
       | programming. I think that most people can agree that DP is one of
       | the hairier subjects. When I'm griding Leetcode I mostly used to
       | skip these problems and then just hope in an interview I'm never
       | asked about it.
       | 
       | My prof cleared everything up though. He said that DP is what
       | naturally happens whenever you take a recursive algorithm and
       | refactor it to put all the recursive calls into their own data
       | structure. When you are doing recursive fibonacci, you are really
       | just using the call stack as a linked list. So instead of making
       | the recursive call, figure out how value N in the list relies on
       | the previous values and then compute that directly.
       | 
       | For more complicated algorithms where the recursive call has N
       | arguments, that means you need a N-dimensional array (worst case)
       | to store your calls in.
       | 
       | After that lecture I was never scared of dynamic programming
       | because I had a meta-algorithm to produce the DP solution.
       | 
       | 1. Write a recursive algo (probably exponentially inefficent)
       | 
       | 2. Figure out how to store recursive call data in a data
       | structure
       | 
       | 3. Figure out how to populate field (a,b) of the data structure,
       | normally by combining/minimizing/maximizing (a,b-1), (a-1,b)
       | 
       | 4. Figure out how to get the answer out of the data structure
       | once you have filled it in
        
         | adammarples wrote:
         | This is a very helpful rule of thumb
        
         | analog31 wrote:
         | A similar "data structure," that made recursion easy for me, is
         | a set that's populated by an inductive proof in math. I think
         | it's pretty much what you're talking about.
        
       ___________________________________________________________________
       (page generated 2023-05-26 23:00 UTC)