# Recursion Exercise

### Objective

To gain experience writing recursive functions.

### Task

Some data structures naturally lend themselves to recursion.
One of these is liked lists.
When we define the node of a linked list, we are already using a form of recursion:

```
struct Node {
type data;
Node* next;
};
```

Here a Node is defined as having data, and a pointer to another Node.
Because Nodes are mentioned in the definition of a Node, this is recursive.

We can use the fact that Nodes are defined recursively to write recursive
functions for dealing with linked lists. For this lab, you will write a
function to print a singly-linked list using recursion instead of iteration.
You will also write a function to print a singly-linked list **backwards**
using recursion. This is more difficult without recursion, but extremely
simple with it.

### Details

- Start by downloading list.cpp which is a basic linked list class with an add function.
- The class also has two functions "printForward" and "printBackward".
These functions take no parameters, and simply call printForwardHelper and printBackwardHelper with the head node.
- You will write the printForwardHelper and printBackwardHelper functions so they print out the nodes in the list starting at the node they take as a parameter.
- You can not use any kind of loop for the functions, you must use recursion.
- Start with the function to print the nodes forward, as it is likely easier to understand.
- Then write the function to print them backwards. It is a very minor change from the forward-printing function.

### Submitting

When you're done, email the code to ifinlay@umw.edu.
Copyright © 2018 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.