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)
How to submit
see the Submission section
Deadline to submit
12pm Monday of Week 3
Submission late penalty
0.2% per hour or part thereof deducted from the attained mark, submissions later than 5 days not accepted
When to get handmarked
in your Week 2, 3 or 4 lab session (after you have submitted)
Note: You must get your work handmarked to receive marks for the lab. If you do not get your work handmarked, you will receive 0 marks for the entire lab exercise, regardless of your automarking result.

Click here to request handmarking

Note that you must be physically present in the lab to get handmarked, and you must be prepared to explain your work. During handmarking, if you take too long to explain your work or recall what you did, you may be moved to the end of the queue.

Setting Up

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

unzip /web/cs2521/26T3/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 - Exponentiation 2️⃣️2️⃣️

We have seen in lectures that some mathematical operations can be defined, and hence implemented, recursively.

For example, factorial can be defined recursively as:

$$ n! = \begin{cases} 1 & \text{if } n = 0 \\ n \times (n - 1)! & \text{if } n > 0 \end{cases} $$

Another mathematical operation that can be defined recursively is exponentiation, written as \(a^n\), where a number \(a\) (called the base) is multiplied by itself \(n\) times (called the exponent).

For example:

  • \(a^1 = a\)
  • \(a^2 = a \times a\)
  • \(a^3 = a \times a \times a\)
  • \(a^4 = a \times a \times a \times a\)
Note that \(a^0\), which is \(a\) multiplied by itself zero times, is also defined and is equal to \(1\), the empty product.

Observe that the definition of \(a^1\) appears in the definition of \(a^2\), the definition of \(a^2\) appears in the definition of \(a^3\), and so on. This means in general, we can write each power of \(a\) in terms of a smaller power of \(a\)! For example:

$$ \begin{align} a^4 &= a \times a \times a \times a\\ &= a \times (a \times a \times a)\,\,\ \\ &= a \times a^3 \end{align} $$

And in general:

$$ \begin{align} a^n &= \underbrace{a \times a \times \cdots \times a}_{n\ \text{times}} \\ &= a \times (\underbrace{a \times \cdots \times a}_{n - 1\ \text{times}}) \\ &= a \times a^{n - 1} \end{align} $$

Your task is to implement the following function in power.c:

long long power(int a, int n);

This function should calculate an recursively as described above. You can assume that n is non-negative and that a and n are not both 0.

A 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 not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
Testing

power.c contains a main function which allows you to test your power function. The main function takes two command-line arguments which are \(a\) and \(n\) respectively. Here are some examples of its usage:

make
...
./power 2 32
2^32 = 4294967296
./power 3 13
3^13 = 1594323
./power 5 21
5^21 = 476837158203125
./power 12 2
12^2 = 144

Task 2 - Faster Exponentiation ⚡️

It turns out there is a much more efficient way to perform exponentiation!

Suppose we want to find \(a^{32}\). We can do this by simply multiplying \(a\) by itself thirty-two times, but this is slow.

One way we can speed it up is that once we have multiplied \(a\) by itself sixteen times to get \(a^{16}\), we can simply square it to get \(a^{32}\) instead of multiplying it by \(a\) sixteen more times. This cuts the time taken by roughly half.

Using the same idea, we can also find \(a^{16}\) more efficiently: after we have found \(a^8\), we can simply square it to get \(a^{16}\), which cuts the time taken by half again.

Similarly, to find \(a^8\), we can simply find \(a^4\) first and then square it. And so on.

This method of calculating \(a^n\) is called fast exponentiation.

If \(n\) is even, then we first find \(a^{n/2}\), and then square it to get \(a^n\).

But what if \(n\) is odd, for example, \(a^{13}\)? We can still find it efficiently - first, we find \(a^{12}\) (by squaring \(a^6\)), and then multiply it by \(a\) to get \(a^{13}\).

So if \(n\) is odd, then we first find \(a^{\lfloor n/2 \rfloor}\), then square it, and then multiply the result by \(a\).

We can use the above method to calculate any integer power of \(a\). For example, suppose we want to find \(a^{21}\). We would calculate it as follows:

$$ \begin{align} a^{21} &= a^{10} \times a^{10} \times a \\ a^{10} &= a^5 \times a^5 \\ a^5 &= a^2 \times a^2 \times a \\ a^2 &= a^1 \times a^1 \\ a^1 &= a^0 \times a^0 \times a \\ a^0 &= 1 \end{align} $$

Fast exponentiation is \(O(\log n)\), where \(n\) is the exponent. This is because the number of powers of \(a\) we explicitly calculate is about \(\log_2{n}\), and for each power, we perform up to two multiplications.

Your task is to implement the following function in fastPower.c:

long long fastPower(int a, int n);

This function should calculate an in \(O(\log n)\) time using fast exponentiation, as described above. You can assume that n is non-negative and that a and n are not both 0.

Note: Your function should run in \(O(\log n)\) time. Slower solutions will not receive any marks.

Hint: To ensure that your function runs in \(O(\log n)\) time, make sure that each function call recurses only once! Don't recurse twice on the same exponent, or your function might end up being \(O(n)\).

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
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

fastPower.c contains a main function which allows you to test your fastPower function. The main function takes two command-line arguments which are \(a\) and \(n\) respectively. Here are some examples of its usage:

make
...
./fastPower 2 32
2^32 = 4294967296
./fastPower 3 13
3^13 = 1594323
./fastPower 5 21
5^21 = 476837158203125
./fastPower 12 2
12^2 = 144

Task 3 - Find the Last Element of a Linked List

Recursion works very 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. The function must not modify the list.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
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 Funniness of a Linked List

Henry loves the 67 meme. The more he sees it, the funnier it is, and the more he laughs. Now, Henry needs your help to determine how funny a linked list is.

Your task is to implement this function in listFunniness.c:

int listFunniness(struct node *list);

This function should use recursion to find the funniness of a linked list. The funniness of a linked list is the number of occurrences of any of the following:

  • The value 67
  • The value 6 immediately followed by the value 7

Note that the function must not modify the list.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
Testing

listFunniness.c contains a main function which allows you to test your listFunniness function. The main function:

  • Reads the size of the list
  • Reads the values of the list
  • Displays the list
  • Calls listFunniness
  • Displays the result

Here are some examples of its usage:

make
...
./listFunniness
Enter list size: 7
Enter list values: 3 6 7 9 2 67 1
List: [3, 6, 7, 9, 2, 67, 1]
The funniness of the list is: 2
./listFunniness
Enter list size: 8
Enter list values: 6 7 67 6 6 6 7 67
List: [6, 7, 67, 6, 6, 6, 7, 67]
The funniness of the list is: 4
./listFunniness
Enter list size: 6
Enter list values: 4 7 6 8 76 5
List: [4, 7, 6, 8, 76, 5]
The funniness of the list is: 0

Task 5 - 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. The function must not modify the list.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
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 6 - Insert into an Ordered Linked List

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

struct node *listInsertOrdered(struct node *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.

A newNode function is provided in list.h. You can use this in your solution.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: You must not use helper functions in this task. Solutions that use helper functions will receive at most half the marks for this task. (Why? If you feel the need to use a helper function, this suggests that you might not fully understand recursion, so please ask your tutor for feedback!)
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 - Using Recursive Helper Functions

In this course, a list will often 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. The function must not modify the list.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these will not receive any marks.
Note: Helper functions are allowed in this task and the following tasks. However, note that the intended solutions of these tasks use only one helper function each, so if you are considering using more, you may want to ask your tutor for feedback.
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 8 - 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.

A newNode function is provided in list.h. You can use this in your solution.

Note: You must not use while loops, for loops, do loops or goto statements. Solutions that use any of these 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]

Optional Challenge Task - Shifting a Linked List Recursively!

Note: This task is optional. It is not worth any marks.

Your task is to implement this function in listShift.c:

struct node *listShift(struct node *list);

This function should use recursion to shift the given list to the right once and return a pointer to the start of the updated list. When a linked list is shifted to the right, the node at the end of the list is moved to the start. The function should not create any new nodes or delete any nodes - it should simply modify pointers in the existing nodes.

Note: You must not use while loops, for loops, do loops or goto statements.
Note: You must not use helper functions in this task.
Note: As stated above, your solution should not create new nodes or delete nodes - this means you must not call malloc or free, either directly or indirectly.
Testing

listShift.c contains a main function which allows you to test your listShift function. The main function:

  • Reads the size of the list
  • Reads the values of the list
  • Displays the list
  • Calls listShift
  • Displays the updated list

Here are some examples of its usage:

make
...
./listShift
Enter list size: 3
Enter list values: 16 5 2
List: [16, 5, 2]
List after shifting: [2, 16, 5]
./listShift
Enter list size: 5
Enter list values: 9 6 1 8 8
List: [9, 6, 1, 8, 8]
List after shifting: [8, 9, 6, 1, 8]

Submission

Submit via the command line using the give command:

give cs2521 lab02

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.

Assessment

The marking criteria are as follows:

Aspect Marks Criteria
Code correctness 4 Your code for each task will be automarked. Automarking will be run after submissions have closed. After automarking is run you will be able to view your results here.
Code understanding 1 Your tutor will ask you to explain your implementation of one of the tasks to check your understanding of recursion and ask you one or two additional questions about your code. Please see the marking rubrics below to understand how you will be marked.

Code understanding marking rubrics

Explanation
Mark Description
0 No attempt at an explanation, only reading the code
0.2 Some attempt at an explanation, but explanation was poor or predominantly consisted of reading the code
0.3 Reasonable explanation of the logic of most branches in the code
0.4 Explanation is good but describes the code as if it uses iteration (loops) rather than recursion.
For example, "In listAppend, we keep going until the end of the list" suggests an iterative approach.
0.5 Explanation is good and shows an understanding that recursion involves solving a problem via one or more subproblems (smaller version(s) of the same problem).
For example, "In listAppend, if the list is not empty, we recurse to append the value to the rest of the list" shows a good understanding of recursion because "append ... to the rest of the list" communicates what the subproblem is.
Question(s) from tutor
Mark Description
0 Could not answer questions and was not able to understand answers given by tutor
0.2 Could not answer questions but was able to understand answers given by tutor
0.3 Able to answer questions with some prompting from tutor, but shows some lack of understanding
0.4 Able to answer questions with some prompting from tutor and shows a good understanding
0.5 Able to answer questions without prompting and shows a good understanding

Appendix

Hints

You should give each task at least 10 minutes of thought and working out before looking at these hints.

Hints for fastPower

To summarise:

$$ a^n = \begin{cases} a^{n/2} \times a^{n/2} & \text{if } n \text{ is even} \\ a^{\lfloor n/2 \rfloor} \times a^{\lfloor n/2 \rfloor} \times a & \text{if } n \text{ is odd} \end{cases} $$

Don't forget the base case! See the example in the question for a hint.

Be careful not to calculate the same power of \(a\) twice! For example, if you are trying to find \(a^{20}\), don't calculate \(a^{10}\) twice - calculate it once and then square it. Otherwise, your function will not be \(O(\log n)\).

Hints for listTail

If there is one element in the list, what would the last element be?

Hints for listMax

If there is one element in the list, what would the maximum element be?

Suppose you found the maximum element in the rest of the list. In what case would this element be the maximum element of the entire list? In what case would it not be?

Hints for listInsertOrdered

Where should the value be inserted if the list is empty?

In what situations should the value be inserted at the beginning of the list? Be careful - you need to make sure the new node is connected to the rest of the list.

Recall from lectures that when we implemented listAppend, we needed to do the following:

list->next = listAppend(list->next, value);

This ensures that if the head of the rest of the list changes, the current node's next pointer is updated to point to the new head. Make sure you do something similar!