# Caching 7.2starred Recursive Solution

 0 I did the recursive solution to edit distance first, but chickened out when I saw how slow it was for inputs above len(10). I tried using a cache to speed things up, and I saw in the answer video that he mentions that caching can help. I must have done something wrong, because I put some print statements in my code to see when the cache was being used, and it never was getting used. For some reason I can't find my recursive/cache solution (must have trashed it). I was hoping someone who used recursion AND caching in an effective manner would post their code here. I want to see where I went wrong. I'll copy my straight recursive function below. There's a middle part that truncates the strings in all the places where they match, but I suspect this doesn't speed things up, as the real cost is all the recursive calls themselves, not what they are doing: def edit_distance(s,t): if not s: return len(t) elif not t: return len(s) if s == t: return 0 if len(s) > len(t): s, t = t, s shortString = '' longString = '' for i in range(len(s)): if s[i] != t[i]: shortString = shortString + s[i] longString = longString + t[i] if len(t) > len(s): longString = longString + t[len(s):] substitution = 1 + edit_distance(shortString[1:], longString[1:]) deletion = 1 + edit_distance(shortString[1:], longString) insertion = 1 + edit_distance(shortString, longString[1:]) return min(substitution, deletion, insertion)  asked 09 Apr '12, 23:37 bubbled-1 86●3●6●12 accept rate: 0%

 0 This is the one I posted: http://www.udacity-forums.com/cs101/questions/61679/a-cached-version-of-peters-72-starred-solution answered 10 Apr '12, 01:16 Charles Lin 9.2k●42●94●135
 0 This is my solution. Basically, you just provide cache for your function (as a global var or input parameter) and 1) check whether string pair is cached before doing more expensive computation and 2) if it isn't cached yet, add pair to cache before returning the answer. I'd suggest to put cache check before or after the 's==t' base case (I'm still not certain whether it's useful to cache identical strings). answered 10 Apr '12, 02:08 Stepas Tolia... 501●4●22
Question text:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

×15,249
×637
×4