What's Recursion? Recursion is the process of dividing the problem into one or more subproblems,which are identical in structure to the original problem and then combining the solutions to these subproblems to obtain the solution to the original problem
What’s Recursion? ◼ Recursion is the process of dividing the problem into one or more subproblems, which are identical in structure to the original problem and then combining the solutions to these subproblems to obtain the solution to the original problem
What's Recursion? There are three special cases of the recursion technique: Induction:the idea of induction in mathematical proofs is carried over to the design of efficient algorithms 。 Nonoverlapping subproblems:divide and conquer Overlapping subproblems:dynamic programming,trading space for time
What’s Recursion? ◼ There are three special cases of the recursion technique: ⚫ Induction: the idea of induction in mathematical proofs is carried over to the design of efficient algorithms ⚫ Nonoverlapping subproblems: divide and conquer ⚫ Overlapping subproblems: dynamic programming, trading space for time
Induction Given a problem with parameter n,designing an algorithm by induction is based on the fact that if we know how to solve the problem when presented with a parameter less than n,called the induction hypothesis, then our task reduces to extending that solution to include those instances with parameter n
Induction Given a problem with parameter n, designing an algorithm by induction is based on the fact that if we know how to solve the problem when presented with a parameter less than n, called the induction hypothesis, then our task reduces to extending that solution to include those instances with parameter n
Radix Sort Let L=ta,a,...an be a list of n numbers each consisting of exactly k digits.That is,each number is of the form dd1...d,where each d,is a digit between 0 and 9. In this problem,instead of applying induction onn, the number of objects,we use induction on k,the size of each integer
Radix Sort ◼ Let L={a1 , a2 , …, an} be a list of n numbers each consisting of exactly k digits. That is, each number is of the form dkdk-1…d1 , where each di is a digit between 0 and 9. ◼ In this problem, instead of applying induction on n, the number of objects, we use induction on k, the size of each integer
Radix Sort ■ If the numbers are first distributed into the lists by their least significant digit,then a very efficient algorithm results. Suppose that the numbers are sorted lexicographically according to their least k-1 digits, i.e.,digits de de2r....a. After sorting them on their kth digits,they will eventually be sorted
Radix Sort ◼ If the numbers are first distributed into the lists by their least significant digit, then a very efficient algorithm results. ◼ Suppose that the numbers are sorted lexicographically according to their least k-1 digits, i.e., digits dk-1 , dk-2 , …, d1 . ◼ After sorting them on their kth digits, they will eventually be sorted