4 ms·
The biggest issue I have encountered with educating CS college students is that some groups will be hostile to recursion. This is unfortunate, because recursiv
by voxl 4y ago
The biggest issue I have encountered with educating CS college students is that some groups will be hostile to recursion.
This is unfortunate, because recursive solutions neatly transform into dynamic programming solutions. An entire category of so-called "leetcode mediums", tons of interview questions, can almost always be boiled down to a recursive solution and inverting the execution order.
The problems compounds when you also try to teach induction, because it requires many of the same muscles as recursion and it is by far the easiest method to make sure your algorithm is actually correct.
- zuzuleinen 4y agoCan you give me a solution involving inverting the execution order? It's the first time I read about it.
- puffoflogic 4y agoConsider the trace of a naive recursive Fibonacci function: fib(5), fib(4), fib(3), fib(2), fib(1), fib(0), fib(1), fib(2), fib(1), fib(0), .... A memoized solution would merely eliminate the duplicates, but a DP solution should instead have this trace: fib(0), fib(1), fib(2), fib(3), fib(4), fib(5). With the DP solution we know a priori which terms will be needed, so we visit them in an order so that every term needed any step is already computed.