The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I
Lab #4
For labs meeting on Feb. 5, 2002

  1. Write a recursive function that takes two integers, y and x, and returns yx. The function should only use multiplication to calculate the result.

  2. Fibonacci number are defined as:
    f(1) = 1;
    f(2) = 1;
    and
    f(n) = f(n-2) and f(n-1), where n > 2
    Write a recursive function that calculates the Fibonacci numbers.

  3. Selection sort is a method for arranging items in some order where the< or > operator  is defined for the objects. The algorithm works by taking, an array of integers for instance, and progressively searching for the smallest (for ascending order, looking for the greatest will result in descending order) and swapping that integer with the first element in the array. Then looking for the second smallest integer and swapping that with the second smallest element in the array. The process is continued until the array is sorted (see page 507 in your data structures book for a detailed description). Write a recursive selection sort procedure for an array of integers.

  4. If you have time, try to come up with iterative definitions for each of the functions/procedures above. Think about which ones are simpler in their recursive form, versus their iterative form.