Write a recursive function definition for a function that has one parameter n of type int and that returns the nth Fibonacci number. See Programming Project 6 in Chapter 3 for the definition of Fibonacci numbers. Embed the function in a program and test it.

Programming Project 6 in Chapter 3

The text discusses the selection sort. We propose a different “sort” routine, the insertion sort. This routine is in a sense the opposite of the selection sort in that it picks up successive elements from the array and inserts each of these into the correct position in an already sorted subarray (at one end of the array we are sorting). The array to be sorted is divided into a sorted subarray and to-be-sorted subarray. Initially, the sorted subarray is empty. Each element of the to-be-sorted subarray is picked and inserted into its correct position in the sorted subarray. Write a function and a test program to implement the selection sort. Thoroughly test your program. Example and hints: The implementation involves an outside loop that selects successive elements in the to-be-sorted subarray and a nested loop that inserts each element in its proper position in the sorted subarray. Initially, the sorted subarray is empty, and the to-be-sorted subarray is all of the array:

Note that the sorted subarray has grown by one entry. Repeat the process for the first to-be-sorted subarray entry, a[2], finding a place where a[2] can be placed so that the subarray remains sorted. Since a[2] is already in place—that is, it is larger than the largest element in the sorted subarray—the inside loop has nothing to do. The result is as follows: