Longest Common Subsequence using Memoization

longest-common-subsequence-memoization.swift

/// start from m * n. Use RECURSION. End at 0 * 0
    /// out of bounds could be the top and left edges. 
    func lcs(_ t1: [Character], _ t2: [Character]) -> Int {
        var cache: [Stage: Int] = [:]
        
        func helper(_ s: Stage) -> Int {
            if let cached = cache[s] {
                return cached
            }
            
            guard s.s1 >= 0 && s.s2 >= 0 else {
                cache[s] = 0
                return 0
            }
            
            if t1[s.s1] == t2[s.s2] {
                cache[s] = helper(Stage(s.s1 - 1, s.s2 - 1)) + 1 
                return cache[s]!
            } else {
                cache[s] = max(helper(Stage(s.s1 - 1, s.s2)), helper(Stage(s.s1, s.s2 - 1)))
                return cache[s]!
            }
        }
        return helper(Stage(t1.count - 1, t2.count - 1))
    }

/* Interesting notes from Stanford PDF: 
https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1126/lectures/06/Slides06.pdf 

Recursion solves a problem by continuously simplifying the problem until it becomes simple enough to be solved directly.
The recursive decomposition makes the problem slightly simpler at each step.
The base case is what ultimately makes the problem solvable – it guarantees that when the problem is sufficiently simple, we can just solve it directly.

You will need to learn to trust that your recursive calls – which are to the function that you are currently writing! - will indeed work correctly.
Eric Roberts calls this the “Recursive Leap of Faith.”

What is different is that in recursion, the recursive function calls get interrupted part way through by another recursive function call. 
Every time that happens, the function call gets paused, and a new function call starts. 
Each recursive call generates new parameters to feed into the next recursive call, until the parameters generated match to the base case and the last recursive call ends. 
Usually the last recursive call returns a value at that point. See here for more: https://www.reddit.com/r/learnprogramming/comments/xdtpbc/how_to_conceptually_understand_recursion_and/



*/