Recursion is a powerful technique in computer science. If wecan express a solution to problem X in terms of solutionsto smaller instances of the same problem X—and wecan solve X directly for the “smallest”inputs—then we can solve X for all inputs. There aremany examples. We can sort an array A by sorting the lefthalf of A and the right half of A andmerging the results together; 1-element arrays are by definition alreadysorted. (That’s merge sort.)
Review the options below to login to check your access.
Log in with your Cambridge Higher Education account to check access.
If you believe you should have access to this content, please contact your institutional librarian or consult our FAQ page for further information about accessing our content.