1. Homepage
2. Programming
3. COMP2521 Data Structures and Algorithms Lab Exercise: Recursion

# COMP2521 Data Structures and Algorithms Lab Exercise: Recursion

AustraliaUNSWCOMP2521Data Structures and AlgorithmsRecursionC

# Week 02 Lab Exercise

### Objectives

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

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 $a$ and $b$ is the largest integer that divides both $a$ and $b$ with no remainder. For example, the GCD of $16$ and $28$ is $4$ because $16=4×4$ and $28=4×7$, 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 $r$ is the remainder when we divide $a$ by $b$, then the common divisors of $a$ and $b$ are precisely the same as the common divisors of $b$ and $r$, so the following identity holds:

$gcd\left(a,b\right)=gcd\left(b,r\right)$

If we start with any two positive integers, and apply this identity repeatedly, $r$ 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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
Note: We have provided hints for some of the tasks in this lab, which can be found in the appendix at the bottom of this page. Only look at them if you're stuck and have no ideas - if you have an idea but you're not sure if it will work, try it first!
##### 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.
Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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:

A linked list is either:
• 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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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) {
}


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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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.

Note: You must use recursion. A non-recursive solution will not receive any marks.
##### 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
...
./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.

## Get in Touch with Our Experts

QQ
WeChat
Whatsapp
Australia代写,UNSW代写,COMP2521代写,Data Structures and Algorithms代写,Recursion代写,C代写,Australia代编,UNSW代编,COMP2521代编,Data Structures and Algorithms代编,Recursion代编,C代编,Australia代考,UNSW代考,COMP2521代考,Data Structures and Algorithms代考,Recursion代考,C代考,Australiahelp,UNSWhelp,COMP2521help,Data Structures and Algorithmshelp,Recursionhelp,Chelp,Australia作业代写,UNSW作业代写,COMP2521作业代写,Data Structures and Algorithms作业代写,Recursion作业代写,C作业代写,Australia编程代写,UNSW编程代写,COMP2521编程代写,Data Structures and Algorithms编程代写,Recursion编程代写,C编程代写,Australiaprogramming help,UNSWprogramming help,COMP2521programming help,Data Structures and Algorithmsprogramming help,Recursionprogramming help,Cprogramming help,Australiaassignment help,UNSWassignment help,COMP2521assignment help,Data Structures and Algorithmsassignment help,Recursionassignment help,Cassignment help,Australiasolution,UNSWsolution,COMP2521solution,Data Structures and Algorithmssolution,Recursionsolution,Csolution,