Question

Select one of the following three common computer science problems and describe how recursion can be used to solve this problem more efficiently (sorting, minimum cost spanning tree, knapsack problem). You must generally describe the algorithm that would be used to solve the problem and detail how recursion makes the algorithm more asymptotically efficient.

Answer 1

Solution:

We are taking sorting as a problem to solve here.

So let's have a look at what recursion is and how it is helpful to us programmers.

Recursion:

Recursion is basically a concept when a function calls itself in order to solve a problem, so the concept here is to find a pattern in the problem which is repeating and place it in recursive calls to solve it.

So recursive methods always have a base case or we'd like to call it terminating condition which is the basic condition of the function where the algorithm terminates.

Recursion is basically divided and conquer approach which issued to solve the problem, so in case of sorting as well recursively, we can break the array into subarray of numbers which is given to us in unsorted order and then merge it in sorted order and then getting to the final sorted array.

In general sorting algorithms take around O(n^2) time to solve where we compare each element with one another to sort the array.

But here divide and conquer using recursion will solve this problem in O(n log n) time (Merge sort to heap sort) which is efficient.

But mostly recursion is used to make the life of the programmer easy where the programmer will be writing very less line of codes to solve the problem.

Hit the thumbs up if you liked the answer. :)