COMP2521 Data Structures and Algorithms Lab Exercise: Recursion
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 28 The GCD of 16 and 28 is 4 ./gcd 25 15 The GCD of 25 and 15 is 5 ./gcd 12 72 The GCD of 12 and 72 is 12 ./gcd 64 25 The GCD of 64 and 25 is 1 ./gcd 0 42 The 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 0 Number of rabbits after 0 month(s): 2 ./rabbits 1 Number of rabbits after 1 month(s): 2 ./rabbits 2 Number of rabbits after 2 month(s): 4 ./rabbits 12 Number 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 ... ./listTail Enter list size: 7 Enter list values: 6 8 9 2 5 1 3 List: [6, 8, 9, 2, 5, 1, 3] The last element is: 3 ./listTail Enter list size: 4 Enter list values: 2 5 2 1 List: [2, 5, 2, 1] The last element is: 1 ./listTail Enter list size: 1 Enter list values: 42 List: [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 ... ./listMax Enter list size: 5 Enter list values: 7 2 6 8 0 List: [7, 2, 6, 8, 0] The maximum element is: 8 ./listMax Enter list size: 5 Enter list values: 9 6 1 8 8 List: [9, 6, 1, 8, 8] The maximum element is: 9 ./listMax Enter list size: 4 Enter list values: 2 5 2 1 List: [2, 5, 2, 1] The maximum element is: 5 ./listMax Enter list size: 1 Enter list values: 42 List: [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 ... ./listSum Enter list size: 9 Enter list values: 8 1 5 9 6 4 9 5 1 List: [8, 1, 5, 9, 6, 4, 9, 5, 1] The sum of the values in the list is: 48 ./listSum Enter list size: 6 Enter list values: 2 4 3 7 0 4 List: [2, 4, 3, 7, 0, 4] The sum of the values in the list is: 20 ./listSum Enter list size: 5 Enter list values: 3 5 2 4 1 List: [3, 5, 2, 4, 1] The sum of the values in the list is: 15 ./listSum Enter list size: 2 Enter list values: 42 -4 List: [42, -4] The sum of the values in the list is: 38 ./listSum Enter list size: 0 List: [] 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 ... ./listInsertOrdered Enter list size: 3 Enter list values (must be in ascending order): 2 5 7 List: [2, 5, 7] Enter value to insert: 1 List after inserting 1: [1, 2, 5, 7] ./listInsertOrdered Enter list size: 3 Enter list values (must be in ascending order): 2 5 7 List: [2, 5, 7] Enter value to insert: 3 List after inserting 3: [2, 3, 5, 7] ./listInsertOrdered Enter list size: 3 Enter list values (must be in ascending order): 2 5 7 List: [2, 5, 7] Enter value to insert: 5 List after inserting 5: [2, 5, 5, 7] ./listInsertOrdered Enter list size: 3 Enter list values (must be in ascending order): 2 5 7 List: [2, 5, 7] Enter value to insert: 6 List after inserting 6: [2, 5, 6, 7] ./listInsertOrdered Enter list size: 3 Enter list values (must be in ascending order): 2 5 7 List: [2, 5, 7] Enter value to insert: 8 List after inserting 8: [2, 5, 7, 8] ./listInsertOrdered Enter list size: 0 List: [] Enter value to insert: 42 List 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
andvalue
- Calls
listInsertNth
- Displays the updated list
Here are some examples of its usage:
make ... ./listInsertNth Enter list size: 3 Enter list values: 16 7 8 List: [16, 7, 8] Enter position and value to insert: 0 12 List after inserting 12 at position 0: [12, 16, 7, 8] ./listInsertNth Enter list size: 3 Enter list values: 16 7 8 List: [16, 7, 8] Enter position and value to insert: 1 12 List after inserting 12 at position 1: [16, 12, 7, 8] ./listInsertNth Enter list size: 3 Enter list values: 16 7 8 List: [16, 7, 8] Enter position and value to insert: 2 12 List after inserting 12 at position 2: [16, 7, 12, 8] ./listInsertNth Enter list size: 3 Enter list values: 16 7 8 List: [16, 7, 8] Enter position and value to insert: 3 12 List after inserting 12 at position 3: [16, 7, 8, 12] ./listInsertNth Enter list size: 3 Enter list values: 16 7 8 List: [16, 7, 8] Enter position and value to insert: 4 12 List after inserting 12 at position 4: [16, 7, 8, 12] ./listInsertNth Enter list size: 1 Enter list values: 42 List: [42] Enter position and value to insert: 0 16 List after inserting 16 at position 0: [16, 42] ./listInsertNth Enter list size: 0 List: [] Enter position and value to insert: 0 2 List after inserting 2 at position 0: [2] ./listInsertNth Enter list size: 0 List: [] Enter position and value to insert: 10 2 List 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.