Volume 3

Exercise	Focus
0. Alternating Factorial	Recursion and defining one recursive function using another.
1. Recursively Processing Arrays	Recursive initialization, transformation, aggregation, minimum, and maximum.
2. Grey Codes	Recursion and two-dimensional arrays through grey-code generation.

Getting Started

• Don’t know how to get started with a Volume? Refer to the instructions in Tutorial 0
• To understand how the volumes are graded, refer to How Are Volumes Graded
• To read our expectations for code in this course (which we will teach you over time), read C Standards

Warning: You can't use loops for this Volume, sorry :(

In this volume, we’re going to disallow loops. The code you write in student.c should solve every exercise recursively. You may implement additional helper functions in student.c for every exercise.

Why? Typically, we’re very happy to let you use any parts of C you might know before CS1010, and we hate banning things. In this Volume’s case though, we want you to develop specific recursion skills that will help you later. Working with constraints also helps develop your problem solving mental muscles. Please bear with us for now and trust that limiting this approach right now is in your best interest.

0. Alternating Factorial

Focus

Recursion, alternate factorials, and defining one recursive function using another.

Introduction

Have you heard of an alternating factorial? No? Well, neither have we! Nonetheless, we’ll see how to implement it as basic recursion practise.

You are already familiar with the factorial function:

$n!=n\times (n-1)\times \dots \times 2\times 1.$

In this exercise, you will implement a variation called the alternate factorial, defined recursively as follows:

$$\begin{array}{rl}alt\_factorial(1)& =1,\\ alt\_factorial(n)& =n!-alt\_factorial(n-1),\\ & n>1.\end{array}$$

Hint

Pay attention to what our base case is here, as opposed to the original factorial function.

For example:

$$\begin{array}{rl}alt\_factorial(2)& =2!-alt\_factorial(1)\\ & =2-1=1,\end{array}$$ $$\begin{array}{rl}alt\_factorial(3)& =3!-alt\_factorial(2)\\ & =6-1=5,\end{array}$$ $$\begin{array}{rl}alt\_factorial(4)& =4!-alt\_factorial(3)\\ & =24-5=19.\end{array}$$

Your Task

• Write your solution in the function:

long alt_factorial(int n)

Expected Behaviour

Your function should implement alternate factorial recursively. The input satisfies $1\le n\le 20$. Compute the result recursively from the input; pre-computing the solutions and storing them in a lookup table or hard-coding them is not allowed.

Running and Testing

• To compile: run make
• To run: run ./alt_factorial
• To test: run make test
• Input: The program reads a single integer $n$ from standard input and outputs the value of alt_factorial(n)

Examples

Input	Output
1	1
2	1
3	5
4	19
5	101

Notes

• Implement alt_factorial and any helper functions you need
• Do not change the provided input-reading code or main

---

1. Recursively Processing Arrays

Focus

Recursion over arrays by repeatedly solving a smaller prefix.

Your Task

Open student.c, and you should see the following functions that you need to fill out.

#include <stddef.h>
#include <stdio.h>
 
void initialize_increasing(int values[], size_t length) {
  // TODO
}
 
void double_if_even(int values[], size_t length) {
  // TODO
}
 
bool are_all_odd_indices_positive(int values[], size_t length) {
  // TODO
}
 
int sum_elements(int values[], size_t length) {
  // TODO
}
 
size_t find_min_index(int values[], size_t length) {
  // TODO
}
 
int find_max(int values[], size_t length) {
  // TODO
}
 
double digits_to_double(int values[], size_t length) {
  // TODO
}
 
void swap_adjacent_pairs(int values[], size_t length) {
  // TODO
}
 
bool is_palindrome(int values[], size_t length) {
  // TODO
}

Note

You may implement additional functions as helpers if you wish.

Expected Behaviour

• initialize_increasing should initialise the given array with values from $1$ up to $length$

• double_if_even should double each even-valued element in the given array, leaving odd-valued elements unchanged

• are_all_odd_indices_positive should return true if every element at an odd index ($1$, $3$, $5$, and so on) is strictly positive, and false otherwise. Return true if there are no odd indices. Do not modify the array

• sum_elements should return the sum of all the elements

• find_min_index should return the zero-based index of the smallest element. If the minimum occurs more than once, return its first index

• find_max should return the largest element

• digits_to_double should treat every element as a decimal digit and return the digits after a decimal point. For example, {1, 2, 3, 4} should produce $0.1234$. Every element will be between $0$ and $9$

• swap_adjacent_pairs should recursively swap the first and second elements, the third and fourth elements, and so on. If the array has an odd number of elements, leave the last element unchanged. For example, {1, 2, 3, 4, 5, 6} should become {2, 1, 4, 3, 6, 5}, and {1, 2, 3, 4, 5} should become {2, 1, 4, 3, 5}. Empty arrays and arrays with one element should remain unchanged

• is_palindrome should return true if the array is palindromic, meaning its elements read the same forwards and backwards, and false otherwise. For example, {1, 2, 3, 2, 1} is palindromic, but {1, 2, 3} is not. Empty arrays and arrays with one element are palindromic. Do not modify the array

Constraints

• length is the number of elements to process, at most $100$
• find_min_index and find_max always receive a nonempty array
• Every doubled value in double_if_even fits in an int
• Every intermediate and final sum in sum_elements fits in an int
• Elements outside the specified length must remain unchanged

For an empty array (length == 0):

Function	Behaviour
initialize_increasing, double_if_even, swap_adjacent_pairs	Leave the array unchanged
sum_elements	Return 0
digits_to_double	Return 0.0
are_all_odd_indices_positive, is_palindrome	Return true

Running and Testing

• To compile: run make
• To run: run ./recursive-arrays
• To test: run make test

Run ./recursive-arrays, then type an operation, the number of elements, and that many elements. You may separate these with spaces or newlines. The operations are initialize, double, odd-positive, sum, min, max, to-double, swap-pairs, and palindrome. Input reading and printing has been handled for you.

For example, to test digits_to_double:

to-double
4
1 2 3 4

And in this case, the program should print:

0.1234

Press Enter after the final element to see the result. For an empty array, press Enter after the zero length; no elements are needed.

To run the tests for just one function, use its C function name, as in Volume 1’s Pong exercise:

make test FUNCTION=is_palindrome

Replace is_palindrome with any of the function names above to work on one function at a time. Run make test without FUNCTION to run all the cases. All functions must still compile, but only the selected function’s cases will run.

Examples

Type each example’s input into ./recursive-arrays. Boolean results are printed as true or false.

Function	Input	Output
initialize_increasing	initialize 5 0 0 0 0 0	1 2 3 4 5
double_if_even	double 5 3 -2 0 7 10	3 -4 0 7 20
are_all_odd_indices_positive	odd-positive 5 10 20 30 40 50	true
sum_elements	sum 5 4 7 2 -3 5	15
find_min_index	min 5 4 7 2 -3 5	3
find_max	max 5 4 7 2 -3 5	7
digits_to_double	to-double 4 1 2 3 4	0.1234
swap_adjacent_pairs	swap-pairs 5 1 2 3 4 5	2 1 4 3 5
is_palindrome	palindrome 5 1 2 3 2 1	true

---

2. Grey Codes

Focus

Recursion and two-dimensional arrays through grey-code generation.

Background

We’re going to get you to generate something called a grey code. You can read all about them here: https://en.wikipedia.org/wiki/Gray_code, they’re very cool, and some computer engineers we know have had to make these in their programs in the past. (We lied, we know a few electrical engineers who had to do it, but they worked at Intel, so we guess that counts!)

They’re used in quite a few engineering and mathematical contexts, but here’s what we basically want from you: Given an input $n>=1$, we need you to generate an array of arrays each with $n$ elements each being either only 0 or 1, such that:

• All $2^n$ possible sequences of 0 and 1 are listed, each possibility on its own line
• Any adjacent sequence differs only exactly by 1 character
• The first sequence and last sequence also differ only exactly by 1 character

Example 1

Here’s an example for $n=2$:

00
01
11
10

Explanation: There are $2^n=2^2=4$ possible sequences we need to output, notice here that each line differs from the next line in exactly 1 character only. Furthermore, the first line and the last line differ in exactly 1 character.

Example 2

Here’s an example for $n=3$:

000
001
011
010
110
111
101
100

Explanation: There are $2^n=2^3=8$ possible sequences we need to output, notice here that each line differs from the next line in exactly 1 character only. Furthermore, the first line and the last line differ in exactly 1 character.

Note

The ordering of the sequences matter here! This is not the same as just printing out all $2^n$ possible sequences. Adjacent lines of output must differ by exactly 1 character.

Step 1.1: Identify the simple case

Think about what is a valid grey code for $n=1$. That should be your base case.

Step 1.2: Use the solution to the simpler case to solve the current problem

Let’s say we could solve grey-code for $n-1$. You might want to think about how that sequence helps you solve the $n$ case.

Step 2: Break the problem up into logical steps

Identify the high level idea without writing the code first. What kind of operations do you need? Can you make each of these steps their own functions? What should their prototypes be?

Step 3: Start Writing the Code

Hop to it!

Code

In student.c, complete the following function:

void grey_code(unsigned int n, GreyCode sequence[]) {
  // TODO
}

The GreyCode type

GreyCode sequence[] is an array of GreyCode. You are promised that sequence[] is an array that can hold at least $2^n$ elements. Use only the first $2^n$ rows. You are also promised that each element is an array that will fit at least n elements. I.e. GreyCode is an array.

I.e. you could choose to think of sequence as a 2D array, with $2^n$ rows and $n$ columns.

Indexing

If for example, you wish to set the $i^{t}h$ character of the $j^{th}$ sequence to be 1, you’d write: sequence[j][i] = '1'.

Your Task

Complete grey_code recursively. Do not use loops. Fill the first $2^n$ rows of sequence, each with exactly $n$ characters, either '0' or '1' (subject to the requirement).

Any ordering satisfying all the stated grey-code properties is accepted; it need not match the examples exactly.

The input satisfies $1\le n\le 10$ (anything larger and the output is gonna be really long anyway). Generate the sequences recursively from the input; pre-computing the solutions and storing them in lookup tables or hard-coding them is not allowed.

Running and Testing

• To compile: run make
• To run: run ./grey-code
• To test: run make test
• Input: Input a single integer $n$ from $1$ to $10$, inclusive

Note

If we’re being honest, we don’t know how to solve this problem without recursion. So that’s probably a sign that if anything, knowing how to recurse is going to make your life a lot easier.

Suggestions / Hints

Hint

Look at the examples for $n=2$ and $n=3$ again. Can you somehow see how you might spot the $n=2$ sequence from within the $n=3$ sequence?

Hint

A function called copy_grey_code(...) is given to you. It will copy the sequence[from] into sequence[to] for you. You can use it for free! But we would recommend thinking about the other important logical steps you need, and the kind of functions they can become.

Hint

You learned how to mirror an array of integers in the lab. Perhaps mirroring something else (not integers nor chars) might be helpful here.

Hint

You might need to figure out how to “append” a character at the end of the sequence as well. The value n should help you with this somehow.