Assignment 4: Recursion¶

In this assignment, your task is to practice writing recursive functions. The questions are in the file a4.h, and each question asks you to write a recursive function according to a specification given in the source code itself.

The functions are specified using pre-conditions, post-conditions, and constraints. For example, here is the specification for a function that sums the integers from 1 to n:

// 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 functions finishes running correctly (assuming that the pre-condition held before it was called).

The constraints part of the specification lists any other things that must be true for the function. In this assignment, the major constraint is that no loops are allowed in any of the code you write.

Important: No loops are permitted in any of the code you write for this assignment (not even in the test functions).

Testing¶

For each function, you must also write a corresponding test function that automatically runs tests on the function to help ensure it is working correctly. Typically, this is a series of assert statements that call the function and compare its results to the known correct answer.

For example, the test function for sum from above could be written like this:

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";
}

Recall that assert is a standard C++ macro (use #include <cassert> to get it) that takes a bool expression as input. It crashes on purposes if the expression evaluates to false, and does nothing if it evaluates to true. Your test functions should only return normally if all the individual tests pass.

In some cases, you might prefer to use an if-statement rather than assert. For example, the test assert(sum(2) == 1 + 2) could be written like this:

if (sum(2) != 1 + 2) cmpt::error("test failed");

However you write the tests, the important thing is that you actually do the testing, and that those tests are run and 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 are exited, which can be helpful with recursive functions.

Implementation Constraints¶

Do not use any global variables, static local variables, or other such tricks when implementing these function. Just use function, arguments to those functions, and return values.

Important: No loops are permitted in any of the code you write for this assignment (not even in the test functions).

Submit Your Work¶

Please submit the file a4.cpp, and nothing else, on Canvas. A copy of of a4.h and cmpt_error.h will be put in the same folder as your program when it runs.

Do not submit cmpt_error.h, cmpt_trace.h, a4.h or any other unrequested files!

Basic Requirements¶

Before we give your program any marks, it must meet the following basic requirements:

It must compile on Ubuntu Linux using the standard course makefile:
```
$ make a4
g++  -std=c++14 -Wall -Wextra -Werror -Wfatal-errors -Wno-sign-compare -Wnon-virtual-dtor -g   a4.cpp   -o a4
```
If your program fails to compile, your mark for this assignment will be 0.

The standard course file cmpt_error.h will be in the same folder as a4.cpp when it’s compiled, so your program can use cmpt::error if necessary.

While your program can include any other standard C++ library files that it needs to run correctly, please stick to the basic C++ features discussed in lectures and the textbook.
It must have no memory leaks, according to valgrind, e.g.:
```
$ valgrind ./a4

// ... lots of output ...
```
A program is considered to have no memory leaks if:
1. In the LEAK SUMMARY, definitely lost, indirectly lost, and possibly lost must all be 0.
2. The ERROR SUMMARY must report 0 errors.
3. 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, it will not be marked.

/////////////////////////////////////////////////////////////////////////
//
// Student Info
// ------------
//
// Name : <put your full name here!>
// St.# : <put your full SFU student number here>
// Email: <put your SFU email address here>
//
//
// Statement of Originality
// ------------------------
//
// All the code and comments below are my own original work. For any non-
// original work, I have provided citations in the comments with enough
// detail so that someone can see the exact source and extent of the
// borrowed work.
//
// In addition, I have not shared this work with anyone else, and I have
// not seen solutions from other students, tutors, websites, books,
// etc.
//
/////////////////////////////////////////////////////////////////////////

If your program meets all these basic requirements, then it will graded using the marking scheme on Canvas.

a4.cpp¶

// a4.cpp

#include "a4.h"  // no other includes are allowed!

using namespace std;

//
// put your implementation of the 20 function headers from "a4.h" here
//


//
// You can use this main function (which calls all the test functions), or
// re-write it any way you like. The marker will be using their own main
// function to test your code.
//
int main () {
  sum_of_squares_test();
  sum_strange_test();
  all_same_test();
  all_digits_test();
  trim_test();
  sum_neg_test();
  min_vec_test();
  count_test();
  zip_test();
  join_test();
}

a4.h¶

// a4.h

///////////////////////////////////////////////////////////////////////////////
//
// Do not change this file in any way!
//
// Implement the 20 requested functions. Put all your code into a4.cpp.
//
///////////////////////////////////////////////////////////////////////////////

#include "cmpt_error.h"
#include <iostream>
#include <string>
#include <vector>
#include <cassert>

using namespace std;

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    n >= 0
// Post-condition:
//    Returns the sum of the first n squares, i.e.
//    1^2 + 2^2 + 3^2 + ... + n^2. 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 overflow sums that overflow int.
int sum_of_squares(int n);

void sum_of_squares_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    n > 0
// Post-condition:
//    Returns the count of the number of numbers from 1 to n (inclusive)
//    that are multiple of 3 but not multiples of 5.
//
//    For example, sum_strange(20) returns 5 because among the numbers 1 to
//    20, these are the multiples of 3: 3, 6, 9, 12, 15, 18. Since 15 is also
//    a multiple of 5, it's not counted.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
// Note:
//    You don't need to worry about overflow sums that overflow int.
int sum_strange(int n);

void sum_strange_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns true if all the characters in s are the same, and false otherwise.
//    If s is the empty string, true is returned.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
bool all_same(const string& s);

void all_same_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns true if s either empty, or contains only digit characters
//    '0' to '9'.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
// Note:
//    When testing functions that return bool, make sure to include some
//    test cases that return true, and some that return false.
bool all_digits(const string& s);

void all_digits_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns a copy of s, but with all leading and trailing spaces removes.
//    No other characters are changed. For example, trim("  ab c  d ") returns
//    "ab c  d". If s is the empty string, then "" is returned.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
string trim(const string& s);

void trim_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns the sum of just the negative numbers in v.
//    If v is empty, 0 is returned.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
int sum_neg(const vector<int>& v);

void sum_neg_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    a.size() == b.size(), and a.size() > 0
// Post-condition:
//    Returns a vector equal to {min(a[0],b[0]), min(a[1],b[1]),
//    min(a[2],b[2]), ..., min(a[n],b[n])}, where n == a.size().
//
//    For example, min_vec({3, 4, 1}, {2, 5, 2}) returns the new vector
//    {2, 4, 1}.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
vector<int> min_vec(const vector<int>& a, const vector<int>& b);

void min_vec_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns the number of strings in v that are equal to s.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
int count(const vector<string>& v, const string& s);

void count_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    s.size() == t.size()
// Post-condition:
//    Returns a vector<string> where the first string is the first character
//    of s followed by the first character of t, the second string is the
//    second character of s followed by the second character of t, and so on.
//    For example, zip("abc", "xyz") returns {"ax", "by", "cz"}.
//
//    If both s and t are empty, then an empty vector<string> is returned.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
vector<string> zip(const string& s, const string& t);

void zip_test();

///////////////////////////////////////////////////////////////////////////////
//
// Pre-condition:
//    none
// Post-condition:
//    Returns a string consisting of all the strings in v concatenated
//    together with sep after each string (except for the last).
//
//    For example, join({"cat", "dog", "house"}, ", ") returns the string
//    "cat, dog, house", and join({"he", "we", "see"}, "") returns the string
//    "hewesee".
//
//    If v is empty, the empty string is returned.
// Constraints:
//    Must be implemented using recursion (and no loops). You can write helper
//    functions if necessary.
string join(const vector<string>& v, const string& sep);

void join_test();

Table Of Contents

Previous topic

Next topic