Lecture 16: Recursion on Non-numerics

[@ifedayoosifuye8798]

boolean inListOfLists(List L, int e) { // Base case: if the list is empty, return false if (L.size() == 0) return false; // Get the first sublist List sublist = L.get(0); // Check if the element exists in the current sublist for (int num : sublist) { if (num == e) return true; } // Recursive case: check the rest of the list of lists return inListOfLists(L.subList(1, L.size()), e); }

[@MrRosamunda]

I wanted to revisit recursion and found lecture 15 and 16. Such an epic professor! I was doing the exercise about basketball and got stuck for a while because her function's docstring said: "order doesn't matter", but it does (e.g. 2+1 and 1+2 are counted as 2 different options)! Pointing it out in case it helps someone :)

[@WIllz2GOTA]

late reply but for others: whether or not order matters are two completely different problems so Ana is not wrong in any way - when she defined the base case for n = 3 she counted the three ways (1+1+1, 2+1, 3) of adding up to 3 with the numbers 1,2,3 without reordering, whereas with ordering you'd also have the example 1+2 which you've given

[@ondrbak]

@@WIllz2GOTA The example in the lecture still doesn't work correctly. The base case assumes the order doesn't matter, but the recursive step doesn't account for that and counts differently ordered combinations as distinct possibilities. You can see this even when trying to calculate the number of ways to get to 4. If we do it "by hand" by carefully counting all combinations, we will get 4 different ways (again, the order doesn't matter): 3+1, 2+2, 2+1+1, 1+1+1+1 But if we call the function score_count(4) = score_count(3) + score_count(2) + score_count(1) = 3 + 2 + 1 = 6 To fix the example in the direction of "order does matter" is trivial, just replace base case if x==3 return 3 with if x== 3 return 4. Then score_count(4) = 4 + 2 + 1 = 7, and indeed there are 7 different ways to get to 4 if order matters: 3+1, 2+2, 2+1+1, 1+3, 1+2+1, 1+1+2, 1+1+1+1 I don't see an equally easy fix for the "order doesn't matter" variant.

[@JAVERDO_69]

I watched this two times. The second time I didn't understand it. 🤣 She is a great teacher. Excellent explanations.

[@dominikwilczek5655]

Correct me if im wrong but if order in this basketball score recursion example doesnt matter, then there are 4 ways to score 4 points: (1,1,1,1), (1,1,2), (1,3) and (2,2). Yet the recursive function of 4 returns 6. If order of scoring would matter then there are 7 ways for getting to 4 points: (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2), (1,3) and (3,1), and they dont sum up to returned 6 ways.

[@jordanstins3521]

I tried to modify the code to count duplicates and print 7, but I have no idea how to prevent counting duplicates and print 4 instead. def score_count(x): if x == 0: return 1 if x < 0: return 0 return score_count(x - 1) + score_count(x - 2) + score_count(x - 3) print(score_count(4))

[@suphanichk]

@@jordanstins3521 If the order matter, my version would be (Just add one more possibility on x==3 that we may have the case of 2,1 and 1,2) if x == 1: return 1 # 1 elif x == 2: return 2 # 2 or 1+1 elif x == 3: return 4 # 3 or 2+1 or 1+2 or 1+1+1

[@紫晶-w5s]

是的, 當你同意並接受 x==3時 return 3, score_count(4)就註定是6

[@festusabonuhi791]

Change the base case, 4 ways to score 3 (1,1,1), (1,2), (2,1) and 3.. maybe that's should resolve the issue

[@সমুদ্রসন্তান]

This also works for fib example, if for any reason it helps def fib(n, d = {1:1, 2:1}): if n in d: return d[n] else: result = fib(n-1) + fib (n-2) d[n] = result return result

[@mayaahmed]

This is simpler code: def deep_reverse_recur(L): if len(L) == 1: if type(L[0]) != list: return L else: return [deep_reverse_recur(L[0])] else: return deep_reverse_recur(L[1:]) + deep_reverse_recur([L[0]])

[@voitikfamily2679]

Thank you.

[@ManishKumar-pp3li]

Think you mam

[@luisp1375]

This one reversed my brain

[@mawkuri5496]

those are big chalks😮

[@tunahanada6116]

🔥