Recursion¶
Part 5 of the course, volume 5 of the lecture notes. Recursion: classical recursive algorithms, recurrence relations, the Master Theorem, recursive algorithms (array sum, merge sort, binary search, maximum subarray) and the comparison between recursive and iterative versions.
-
14. Recursion
Recursive algorithms · Tree of recursive calls and call stack · Correctness of recursive algorithms · Factorial · …
-
15. Recurrences
Recurrences · The expansion method · The substitution method · The recursion-tree method · …
-
16. The Master Theorem
Recurrences in standard form · The Master Theorem · Applying the Master Theorem · When the Master Theorem does not apply · …
-
17. Recursive algorithms
The sum of the elements of an array · Merge Sort · Recursive Binary Search · The maximum subarray problem · …
-
18. Recursive versus iterative algorithms
Recursion and iteration · Comparison at a glance · Divide and conquer is what gives the gain, not recursion itself · When subproblems overlap · …