31251 Lecture 4: dsa-recursion
30 Jun 2018
School
Department
Course
Professor
Recursion
• Recursion is conceptually a central component of D&C.
• You can in fact phrase everything in computer science in terms of recursion (not a great idea, but
possible).
• It often leads to “neat” code.
• It also often leads to inefficient and broken code.
• For a better understanding we will use Jeff Edmonds “Friends” metaphor for framing recursive
algorithm design (J. Edmonds, “How to Think About Algorithms”, Cambridge University Press, 2008.)
Designing a Recursive Algorithm with your “Friends”
• Carefully specify:
1 The Preconditions: what must be true about the input before you start the algorithm.
2 The Postconditions: what must be true about the output when you’re done.
• These conditions then apply at every step of the recursion.
• Work out how to measure the “size” of an instance.
Designing a Recursive Algorithm with your “Friends” – 2
• Consider a general instance of the problem.
1 Imagine you have friends who can magically solve any instance of the problem strictly
smaller than yours if it meets the preconditions.
2 From your instance, construct sub-instances that meet the preconditions.
3 Get your friends to solve them.
4 Recombine the sub-solutions.
Designing a Recursive Algorithm with your “Friends” – 3
• What if the subinstances don’t fit the preconditions?
• Then you have to rethink your preconditions (and maybe the postconditions).
• Keep the number of cases as small as possible.
• If the subinstance is small enough, just solve it using brute force.
• Analyse the algorithm using a recurrence.
1 | P a g e
find more resources at oneclass.com
find more resources at oneclass.com
Document Summary
Designing a recursive algorithm with your friends : carefully specify: 1 the preconditions: what must be true about the input before you start the algorithm. 2 the postconditions: what must be true about the output when you"re done: these conditions then apply at every step of the recursion, work out how to measure the size of an instance. Designing a recursive algorithm with your friends 2: consider a general instance of the problem. 1 imagine you have friends who can magically solve any instance of the problem strictly smaller than yours if it meets the preconditions. 2 from your instance, construct sub-instances that meet the preconditions.
