Recursion Discussion Notes● Midterm Surveys!Reminders:● Midterm project progress reports are due Sun 10/20 11:55pm.● Beyond Block 1st Session Thurs 10/24 79pm, 306 Soda.○ Bring your own computers!● Midterm Review Sun 10/27 123PM, 2050 VLSB.1. Factorial (could skip to gcd)● Breakdown fact(5) into its recursive calls:fact(5) = 5 x fact(4) = 5 x 24 = 120fact(4) = 4 x fact(3) = 4 x 6 = 24fact(3) = 3 x fact(2) = 3 x 2 = 6fact(2) = 2 x fact(1) = 2 x 1 = 2fact(1) = 1 x fact(0) = 1 x 1 = 1fact(0) = 12. Greatest common divisorgcd(27, 9) = gcd(9, 27 % 9)= gcd(9, 0)= 9gcd(259, 111) = gcd(111, 259 % 111) 259 222 = 37 = gcd(111, 37) 111 = 37 * 3 = gcd(37, 0) = 37gcd(10, 3) = gcd(10, 10 % 3) = gcd(10, 1) = gcd(1, 10 % 1) = gcd(1, 0) = 13. Fibonacci sequencefib(n) = 0 if n = 01 if n = 1fib(n 1) + fib(n2) if n > 12 ^ 2 = 42 ^ 3 = 82 ^ 4 = 162 ^ 5 = 32● Runtime6. Memoization: How can we make Fibonacci linear + recursive?● Take a look at the tree, is there any repetition?● How can we avoid recalculating things we’ve already calculated?● Memoization AKA tabling● How can we add this to our current fibonacci code?7. Practice Problem Palooza● Define length of list without using list● Define multiply without using multiply● Define mod without using mod● Define palindrome
View Full Document
Unlocking...