The input to the maximum and minimum problems is a sequence of numbers, a1... an, where n, the length of the sequence, is a positive integer. The function length(a1... an) returns n, the length of the sequence. If n > 1, you can also make new sequence a1... an-1, which is the original sequence a1... an, with the last number anomitted.

(a) Give a recursive algorithm which takes as input a sequence of numbers and returns the minimum (i.e., smallest) number in the sequence. Your algorithm should not use a loop.

(b) Use induction to prove that your algorithm to compute the minimum of a sequence outputs the correct value for every non-empty sequence of numbers.

(Hint: the minimum value of a sequence a1... anis the unique value x such that x = ajfor some 1 j n and x aifor every 1 i n.)