The best way to understand recursion is to practice writing recursive functions. In the comments of a4.h are a series of questions, each of which asks you to write two functions: an answer function that answers the question, and a test function that tests your answer function. For each question, write both functions.
Put your answer and test functions in a4.cpp, and use a4_main.cpp to call the test functions. When you're done, you'll submit only a4.cpp.
You will need to compile a4.cpp and a4_main.cpp
separately, and then link their .o files into executable for running the
tests. A special-purpose makefile is provided to simplify the
compiling and linking. Read the comments at the top of makefile to
see how it can be used.
The functions are specified using pre-conditions, post-conditions, and constraints. For example:
// Pre-condition:
// n >= 0
// Post-condition:
// Returns the sum of the first n integers, i.e. 1 + 2 + 3 + ... + n.
// If n is 0, then 0 is returned.
// Constraints:
// Must be implemented using recursion (and no loops). You can write
// helper functions if necessary.
// Note:
// You don't need to worry about sums that overflow int.
int sum(int n);The pre-condition states what must be true before the function is called, and the post-condition states what must be true after the function returns correctly (assuming that the pre-condition was true before the function was called).
Constraints lists anything else that is required for the function to be considered correct.
If a function's pre-condition is false when the function is called, then that means it's being called with bad input, and so you probably have a bug somewhere earlier in your code.
Hint A good way to check pre-conditions bugs is to call
assertat the start of a function to check if the pre-condition is true.
For each question, also write a corresponding test function that
automatically runs tests on the answer function. For example, the test
function for sum could be this:
#include <cassert>
// ...
void sum_test() {
cout << "Testing sum ... ";
assert(sum(0) == 0);
assert(sum(1) == 1);
assert(sum(2) == 1 + 2);
assert(sum(3) == 1 + 2 + 3);
assert(sum(4) == 1 + 2 + 3 + 4);
cout << "all sum tests passed!\n";
}In some cases, you might prefer to use an if-statement rather than assert.
The test assert(sum(2) == 1 + 2) could be written like this:
if (sum(2) != 1 + 2) cmpt::error("test failed");However you write your tests, make sure they all run successfully and are checked automatically.
You may also want to use cmpt_trace.h to help debug your functions. It prints messages when functions are called and when they exit, which can be helpful for understanding and debugging recursive functions. See the comments in cmpt_trace.h for an example of how to use it.
-
No loops are permitted in any of the code you write for this assignment (not even in the test functions or helper functions). If your code for a question uses a loop then you will get 0 for that question.
-
You can use helper functions if you like, as long as you write them yourself and they don't use loops. Don't use code from the web or other people.
-
Do not use any global variables, static local variables, or other such tricks when implementing your functions. Just use functions, parameters, and return values in the style shown in the notes and in lectures.
-
Use exactly the function names and parameters given in a4.h. Don't change them in any way.
-
Do not #include any files other than those that are already in a4.h.
On Canvas, please submit just the filea4.cpp with your answers in it. Don't submit anything else.
The marker will use the assignment makefile to compile your
a4.cpp and link it with their own main() function. A copy of
a4.h, cmpt_error.h, cmpt_trace.h, and
cmpt_trace.cpp will be in the same folder as your program when
it runs.
Before we give your program any marks, it must meet the following basic requirements:
-
It must compile on Ubuntu Linux using the makefile in this assignment. Just type
make:$ make g++ -std=c++17 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g -c -o a4.o a4.cpp g++ -std=c++17 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g -c -o a4_main.o a4_main.cpp g++ -std=c++17 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g -c -o cmpt_trace.o cmpt_trace.cpp g++ -o a4_main_test a4.o a4_main.o cmpt_trace.o $ ./a4_main_test ...
makefile is customized for this assignment: it's not the usual course makefile. Notice also that the name of the executable it builds is
a4_main_test. See the comments at the top of makefile for how to use it.If your program fails to compile using this makefile, your mark for this assignment will be 0.
-
It must have no memory leaks or memory errors, according to
valgrind, e.g.:$ valgrind ./a4_main_test // ... lots of output ...A program is considered to have no memory error if:
-
In the
LEAK SUMMARY,definitely lost,indirectly lost, andpossibly lostmust all be 0. -
The
ERROR SUMMARYreports 0 errors. -
It is usually okay if still reachable reports a non- zero number of bytes.
-
-
You must include the large comment section with student info and the statement of originality. If your submitted file does not have this, then we will assume your work is not original and it will not be marked.
If your program meets all these basic requirements, then it will be graded using the marking scheme.
- All code is sensibly and consistently indented, and all lines are 100 characters in length, or less.
- Whitespace is used to group related pieces of a code to make it easier for humans to read. All whitespace has a purpose.
- Variable and function names are self-descriptive.
- Appropriate features of C++ are used, as discussed in class and in the notes. Note If you use a feature that we haven't discussed in class, you must explain it in a comment, even if you think it's obvious.
- Comments are used when needed to explain chunks of code whose purpose is not obvious from the code itself. There should be no commented-out code from previous versions.
- 1 mark for correctly and efficiently implementing each solver function.
- 1 mark for thoroughly testing each requested recursive function with its own test function.
- -1 mark (at least) if your file does not have the correct name, or you submit it in the incorrect format, submit the wrong file, etc.
- up to -3 marks if you do not include your full name, email, and SFU ID in the header of your file.
- a score of 0 if you don't include the "statement of originality in the header of your file.
- a score of 0 if you accidentally submit a "wrong" non-working file, and then after the due date submit the "right" file. If you can provide evidence that you finished the assignment on time, then it may be marked (and probably with a late penalty).