CS 14 - Fluency Exercises

Programming Exercise: Lists & Recursion - Beginner

In this exercise we will play with STL lists and write some useful recursive functions.

STL Lists

Here is a very quick primer on the basic functionality for STL lists. (Note that the STL list type is a doubly-linked list, so insert and remove operations on both ends are efficient. A more space-efficient type, slist is also available, which has essentially the same interface.)

Note that STL lists, like STL vectors are templated types, and as such require a type to be specified when declaring an object of that type.

Gaining access to the STL list type
```
#include <list>
```
Declaring a list of ints:
```
list<int> myList;
```

Adding to the front or back of the list:

myList.push_back(10);
myList.push_front(1);

Getting the value from the front or back of the list:

int valFront = myList.front();
int valBack = myList.back();

Removing from the front or back of the list:
```
myList.pop_front();
myList.pop_back();
```

And most importantly, iterating through the list:

for (list<int>::iterator i = myList.begin(); i != myList.end(); ++i)
{
  cout << *i << endl;
}

For example, a recursive function to sum the elements of a list would be:

int listSum(list<int> l)
{
  int front = l.front();
  l.pop_front();
  
  if (l.size != 0) return front + listSum(l);

  return front;
}

These methods will let you perform most common operations on lists.

3 points

Declare a list in your main function and add 10 elements to it.
Write a recursive function to find the maximum element of the list. The signature should be int findMax(list<int> l). The base case should check if the list has a single element and return the value of that element. The recursive step should store the first element of the list, remove it, and compare it with the result of calling findMax on the rest of the list.
Write a recursive function to find the index of the first instance of a given value in a list: int firstIndex(list<int> l, int n).
Write a function that calls findMax and firstIndex to find the index of the maximum value in the list.
Write a function list<int;> squares(list<int;> l) that takes a list of integers and returns a new list consisting of each of those values, in the same order, squared. Thus calling squares on the list [1, 2, 3] would return [1, 4, 9].

Extra Credit Options

2 points: Rewrite all of these functions to pass their lists by reference and leave the lists intact after the recursive calls.
1 points: Rewrite all of these functions only using slists rather than lists. Are any of your operations made inefficient now? Which?
1 points: Rewrite all of these functions only using vector rather than list. Are any of your operations made inefficient now? Which?