# Week 02 Lab Exercise

### Recursion

### Objectives

- To practice recursion
- To practice using linked lists
- To practice defining recursive helper functions

### Admin

- Marks
- 5 (see the Assessment section for more details)
- Demo
- no demo required
- Submit
- see the Submission section
- Deadline to submit to give
- 5pm Monday of Week 3
- Late penalty
- 0.2% per hour or part thereof, submissions later than 5 days not accepted

### Setting Up

Create a directory for this lab, change into it, and run the following command:

unzip /web/cs2521/23T2/labs/week02/downloads/files.zip

If you're working at home, download `files.zip`

by clicking on the above link and then unzip the downloaded file.

If you've done the above correctly, you should now have a Makefile and several main programs for the tasks below.

### Task 1 - GCD

The greatest common divisor, or GCD, of two integers and is the largest integer that divides both and with no remainder. For example, the GCD of and is because and , and there is no larger integer than divides both.

One way to calculate the GCD would be to totally factor both numbers and find common factors, but there is a much faster and easier way to do it.

If is the remainder when we divide by , then the common divisors of and are precisely the same as the common divisors of and , so the following identity holds:

If we start with any two positive integers, and apply this identity repeatedly, will eventually become zero, and the other number in the pair is the greatest common divisor.

This is an amazing method known as Euclid's algorithm, and is probably the oldest known non-trivial algorithm; it was first described in Euclid's *Elements* in around 300 BC.

Your task is to implement the following function in `gcd.c`

:

```
int gcd(int a, int b);
```

This function should find the GCD of two integers using Euclid's algorithm as described above. You can assume that `a`

and `b`

are non-negative, and that at most one of them is 0.

##### Testing

`gcd.c`

contains a main function which allows you to test your `gcd`

function. The main function takes two command-line arguments which are the two integers. Here are some examples of its usage:

make..../gcd 16 28The GCD of 16 and 28 is 4./gcd 25 15The GCD of 25 and 15 is 5./gcd 12 72The GCD of 12 and 72 is 12./gcd 64 25The GCD of 64 and 25 is 1./gcd 0 42The GCD of 0 and 42 is 42

### Task 2 - A Plague of Rabbits

I have a terrible rabbit problem.

I used to have a pair of baby rabbits; they were extremely cute and fluffy, so of course I got them. But the shopkeeper I got them from - a guy named Leonardo, of Pisa Pets - didn't tell me they would mature very fast, and breed even faster.

After a month, I had a mature pair of rabbits... and, of course, they bred. Damn.

So, a month later, I had a pair of adults and a pair of baby rabbits.

And a month later, I had two pairs of adults, and another pair of baby rabbits.

And a month later, I had three pairs of adults, and two pairs of baby rabbits.

And a month later, I had five pairs of adults, and three pairs of baby rabbits.

HELP! I HAVE SO MANY RABBITS, I'M GOING HOPPING MAD!

Can you help me figure out how many rabbits I'll have? Given that I started with one pair of baby rabbits, implement the following function in `rabbits.c`

that tells me how many rabbits I'll have after a given number of months.

```
long long rabbits(int months);
```

You can assume I won't ask about any time longer than 60 months - surely the rabbits will have taken over the world by then...

`long long`

is like an `int`

, but is 8 bytes in size, so it can store larger values than can be stored in an `int`

.##### Testing

`rabbits.c`

contains a main function which allows you to test your `rabbits`

function. The main function accepts one command-line argument which is the number of months. Here are some examples of its usage:

make..../rabbits 0Number of rabbits after 0 month(s): 2./rabbits 1Number of rabbits after 1 month(s): 2./rabbits 2Number of rabbits after 2 month(s): 4./rabbits 12Number of rabbits after 12 month(s): 466./rabbits 42... after a long pause ...Number of rabbits after 42 month(s): 866988874./rabbits 60... after several hours ...Number of rabbits after 60 month(s): 5009461563922

### Task 3 - Find the Last Element of a Linked List

Recursion works really well with linked lists, because a linked list can be defined recursively as follows:

- Empty, or
- A node containing a value followed by a (smaller) linked list

This means we usually have a base case where the node pointer is `NULL`

, and a recursive case where we do something with the current value and recursively call the function on the rest of the list. Depending on the problem, there may be more base cases or recursive cases.

Your task is to implement this function in `listTail.c`

:

```
int listTail(struct node *list);
```

This function should use recursion to find the last value in the given list. You can assume that the list is not empty.

##### Testing

`listTail.c`

contains a main function which allows you to test your `listTail`

function. The main function:

- Reads the size of the list
- Reads the values of the list
- Displays the list
- Calls
`listTail`

- Displays the result

Here are some examples of its usage:

make..../listTailEnter list size:7Enter list values:6 8 9 2 5 1 3List: [6, 8, 9, 2, 5, 1, 3] The last element is: 3./listTailEnter list size:4Enter list values:2 5 2 1List: [2, 5, 2, 1] The last element is: 1./listTailEnter list size:1Enter list values:42List: [42] The last element is: 42

### Task 4 - Find the Largest Element of a Linked List

Your task is to implement this function in `listMax.c`

:

```
int listMax(struct node *list);
```

This function should use recursion to find the largest value in the given list. You can assume that the list is not empty.

##### Testing

`listMax.c`

contains a main function which allows you to test your `listMax`

function. The main function:

- Reads the size of the list
- Reads the values of the list
- Displays the list
- Calls
`listMax`

- Displays the result

Here are some examples of its usage:

make..../listMaxEnter list size:5Enter list values:7 2 6 8 0List: [7, 2, 6, 8, 0] The maximum element is: 8./listMaxEnter list size:5Enter list values:9 6 1 8 8List: [9, 6, 1, 8, 8] The maximum element is: 9./listMaxEnter list size:4Enter list values:2 5 2 1List: [2, 5, 2, 1] The maximum element is: 5./listMaxEnter list size:1Enter list values:42List: [42] The maximum element is: 42

### Task 5 - Using Recursive Helper Functions

Often in this course, a list will be represented by two structures, one for the usual list node, and one which contains a pointer to the head of the list (along with other data about the list such as its size), usually called a wrapper or container struct. In this case, since we want to recurse on the nodes, not the wrapper struct, we need to implement a helper function which takes in a node pointer and then call it from the original function. For example:

```
int listFunc(struct list *list) {
return listFuncHelper(list->head);
}
```

Your task is to implement this function in `listSum.c`

:

```
int listSum(struct list *list);
```

This function should use a recursive helper function that takes in a node pointer to find the sum of a linked list.

##### Testing

`listSum.c`

contains a main function which allows you to test your `listSum`

function. The main function:

- Reads the size of the list
- Reads the values of the list
- Displays the list
- Calls
`listSum`

- Displays the result

Here are some examples of its usage:

make..../listSumEnter list size:9Enter list values:8 1 5 9 6 4 9 5 1List: [8, 1, 5, 9, 6, 4, 9, 5, 1] The sum of the values in the list is: 48./listSumEnter list size:6Enter list values:2 4 3 7 0 4List: [2, 4, 3, 7, 0, 4] The sum of the values in the list is: 20./listSumEnter list size:5Enter list values:3 5 2 4 1List: [3, 5, 2, 4, 1] The sum of the values in the list is: 15./listSumEnter list size:2Enter list values:42 -4List: [42, -4] The sum of the values in the list is: 38./listSumEnter list size:0List: [] The sum of the values in the list is: 0

### Task 6 - Insert into an Ordered Linked List

Your task is to implement this function in `listInsertOrdered.c`

:

```
void listInsertOrdered(struct list *list, int value);
```

This function should use recursion to insert the given value into an ordered linked list. The list should remain ordered after inserting the value. The function should be able to insert duplicates.

The given file contains a `newNode`

function. You can use this in your solution.

##### Testing

`listInsertOrdered.c`

contains a main function which allows you to test your `listInsertOrdered`

function. The main function:

- Reads the size of the list
- Reads the values of the list
- Displays the list
- Reads the value to insert
- Calls
`listInsertOrdered`

- Displays the updated list

Here are some examples of its usage:

make..../listInsertOrderedEnter list size:3Enter list values (must be in ascending order):2 5 7List: [2, 5, 7] Enter value to insert:1List after inserting 1: [1, 2, 5, 7]./listInsertOrderedEnter list size:3Enter list values (must be in ascending order):2 5 7List: [2, 5, 7] Enter value to insert:3List after inserting 3: [2, 3, 5, 7]./listInsertOrderedEnter list size:3Enter list values (must be in ascending order):2 5 7List: [2, 5, 7] Enter value to insert:5List after inserting 5: [2, 5, 5, 7]./listInsertOrderedEnter list size:3Enter list values (must be in ascending order):2 5 7List: [2, 5, 7] Enter value to insert:6List after inserting 6: [2, 5, 6, 7]./listInsertOrderedEnter list size:3Enter list values (must be in ascending order):2 5 7List: [2, 5, 7] Enter value to insert:8List after inserting 8: [2, 5, 7, 8]./listInsertOrderedEnter list size:0List: [] Enter value to insert:42List after inserting 42: [42]

### Task 7 - Insert into the n'th Position in a Linked List

Your task is to implement this function in `listInsertNth.c`

:

```
void listInsertNth(struct list *list, int n, int value);
```

This function should use recursion to insert the given value before position `n`

of the linked list. The list elements are numbered in the same manner as array elements, so the first element in the list is considered to be at position 0, the second element is considered to be at position 1, and so on. If there are less than `n`

elements in the list, the new value should be inserted at the end of the list. You can assume that `n`

is non-negative.

The given file contains a `newNode`

function. You can use this in your solution.

##### Testing

`listInsertNth.c`

contains a main function which allows you to test your `listInsertNth`

function. The main function:

- Reads the size of the list
- Reads the values of the list
- Displays the list
- Reads the values of
`n`

and`value`

- Calls
`listInsertNth`

- Displays the updated list

Here are some examples of its usage:

make..../listInsertNthEnter list size:3Enter list values:16 7 8List: [16, 7, 8] Enter position and value to insert:0 12List after inserting 12 at position 0: [12, 16, 7, 8]./listInsertNthEnter list size:3Enter list values:16 7 8List: [16, 7, 8] Enter position and value to insert:1 12List after inserting 12 at position 1: [16, 12, 7, 8]./listInsertNthEnter list size:3Enter list values:16 7 8List: [16, 7, 8] Enter position and value to insert:2 12List after inserting 12 at position 2: [16, 7, 12, 8]./listInsertNthEnter list size:3Enter list values:16 7 8List: [16, 7, 8] Enter position and value to insert:3 12List after inserting 12 at position 3: [16, 7, 8, 12]./listInsertNthEnter list size:3Enter list values:16 7 8List: [16, 7, 8] Enter position and value to insert:4 12List after inserting 12 at position 4: [16, 7, 8, 12]./listInsertNthEnter list size:1Enter list values:42List: [42] Enter position and value to insert:0 16List after inserting 16 at position 0: [16, 42]./listInsertNthEnter list size:0List: [] Enter position and value to insert:0 2List after inserting 2 at position 0: [2]./listInsertNthEnter list size:0List: [] Enter position and value to insert:10 2List after inserting 2 at position 10: [2]

### Submission

Submit via the command line using the `give`

command:

give cs2521 lab02 gcd.c rabbits.c listTail.c listMax.c listSum.c listInsertOrdered.c listInsertNth.c

You can also submit via give's web interface. You can submit multiple times. Only your last submission will be marked. You can check the files you have submitted here.