|
|
|
|
|
|
|
Move circle 3 from 1 to 3
From second: 2 2 1 3
From first: 1 2 3 1
From first: 0 2 1 3
Move circle 1 from 2 to 1
From second: 0 3 2 1
Move circle 2 from 2 to 3
From second: 1 1 2 3
From first: 0 1 3 2
Move circle 1 from 1 to 3
From second: 0 2 1 3 |
|
|
|
|
|
|
|
|
Recursive Algorithms with Structured Variables |
|
|
|
|
|
|
|
|
In our definition of a recursive algorithm, we said there were two cases: the recursive or general case, and the base case for which an answer can be expressed nonrecursively. In the general case for all our algorithms so far, a parameter was expressed in terms of a smaller value each time. When structured variables are used, the recursive case is often in terms of a smaller structure rather than a smaller value; the base case occurs when there are no values left to process in the structure. |
|
|
|
|
|
|
|
|
We examine a recursive algorithm for printing the contents of a onedimensional array of n elements to show what we mean. |
|
|
|
|
|
|
|
|
IF more elements
Print the value of the first element
Print Array of n - 1 elements |
|
|
|
|
|
|
|
|
|
The recursive case is to print the values in an array that is one element smaller; that is, the length of the array decreases by 1 with each recursive call. The base case is when the length of the array becomes 0that is, when there are no more elements to print. |
|
|
|
|
|
|
|
|
Our parameters must include the index of the first element (the one to be printed). How do we know when there are no more elements to print (that is, when the length of the array to be printed is 0)? We know we have printed the last element in the array when the index of the next element to be printed is beyond the index of the last element in the array. Therefore, the index of the last array element must be passed as a parameter. We call the indices first and last. When first is greater than last, we are finished. The name of the array is list. |
|
|
|
|
|