Question

Recursion is one way of implementing recursion in programs to solve complex problems. 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

Answer)

Process - Sorting using Recursion by passing array and size of array as parameter:

> To implement Sorting of an array in recursive manner, in the first step it is required to check if the size is 1, then return.

> Iterate each element in the array by checking, if the element in the current index is greater than the element in the next index. If it is, then swap the position. This way, the largest element in the array got its fixed desired index.

> Call the entire process again for (n - 1) elements, passing the same array - Recursive (calling itself)

This way, every time the process is calling itself by passing n-1 elements and setting one large value at its end. This way, ascending sort is implemented, by shifting the larger values at the end.