Sample Solutions to Recursion Practice Questions¶

Implement the following using recursion (and no loops, or special STL functions). For some questions, you may want to create a helper function with extra parameters.

The product of the integers from 1 to \(n\), i.e. the factorial function \(n! = 1 \cdot 2 \cdot \ldots \cdot n\), for \(n \geq 0\). Note that \(0! = 1\).

Sample solution:

int factorial_rec(int n) {
    if (n == 0) {
        return 1;
    } else {
        return n * factorial_rec(n - 1);
    }
}

void factorial_rec_test() {
    cout << "Testing factorial_rec ... ";
    assert(factorial_rec(0) == 1);
    assert(factorial_rec(1) == 1);
    assert(factorial_rec(2) == 2);
    assert(factorial_rec(3) == 6);
    assert(factorial_rec(4) == 24);
    cout << "all tests passed\n";
}

The sum of the first n squares, i.e. \(1^2 + 2^2 + \ldots + n^2\), for \(n \geq 0\).

Sample solution:

int square_rec(int n) {
    if (n == 0) {
        return 0;
    } else {
        return n * n + square_rec(n - 1);
    }
}

void square_rec_test() {
    cout << "Testing square_rec ... ";
    assert(square_rec(0) == 0);
    assert(square_rec(1) == 1);
    assert(square_rec(2) == 5);
    assert(square_rec(3) == 14);
    assert(square_rec(4) == 30);
    cout << "all tests passed\n";
}

Print the numbers from n down to 1 on cout, one number per line. Assume \(n \geq 1\).

Sample solution:

void print_down_from(int n) {
    if (n == 1) {
        cout << 1 << "\n";
    } else {
        cout << n << "\n";
        print_down_from(n-1);
    }
}

void print_down_from_test() {
    cout << "Testing print_down_from ...\n";
    print_down_from(5);
    cout << "all tests passed\n";
}

Print the numbers from 1 up to n on cout, one number per line. Assume \(n \geq 1\). Hint: Write a recursive function that takes two inputs, n, and also another int representing the current value to be printed.

Sample solution:

void print_up_to(int start, int n) {
    if (start == n) {
        cout << start << "\n";
    } else {
        cout << start << "\n";
        print_up_to(start + 1, n);
    }
}

void print_up_to_test() {
    cout << "Testing print_up_to ...\n";
    print_up_to(1, 5);
    cout << "all tests passed\n";
}

The sum of just the positive numbers in a vector. For example, the sum of the positive numbers in {1, -3, -2, 6} is 7.

Sample solution:

int sum_pos(const vector<int>& v, int begin, int end) {
    if (begin >= end) {
        return 0;
    } else if (v[begin] > 0) {
        return v[begin] + sum_pos(v, begin + 1, end);
    } else {
        return sum_pos(v, begin + 1, end);
    }
}

int sum_pos(const vector<int>& v) {
    return sum_pos(v, 0, v.size());
}

void sum_pos_test() {
    cout << "Testing sum_pos ... ";
    vector<int> a = {2};
    vector<int> b = {-2, 1, 4, 0, -10};
    vector<int> c = {1, 2, 3};
    vector<int> d = {-1, -2, -3};
    assert(sum_pos(a) == 2);
    assert(sum_pos(b) == 5);
    assert(sum_pos(c) == 6);
    assert(sum_pos(d) == 0);
    cout << "all tests passed\n";
}

The number of times x occurs in a vector. For example, in {5, 2, 1, 5, 5}, 5 occurs three times.

Sample solution:

int count_rec(const vector<int>& v, int x, int begin, int end) {
    if (begin >= end) {
        return 0;
    } else if (v[begin] == x) {
        return 1 + count_rec(v, x, begin + 1, end);
    } else {
        return count_rec(v, x, begin + 1, end);
    }
}

int count_rec(const vector<int>& v, int x) {
    return count_rec(v, x, 0, v.size());
}

void count_rec_test() {
    cout << "Testing count_rec ... ";
    vector<int> v = {2, 6, 6, 1, 6, 8, 2, 1};
    assert(count_rec(v, 5) == 0);
    assert(count_rec(v, 2) == 2);
    assert(count_rec(v, 6) == 3);
    assert(count_rec(v, 1) == 2);
    assert(count_rec(v, 8) == 1);
    cout << "all tests passed\n";
}

Print the elements of a vector<int>, one number per line.

Sample solution:

void print_vec(const vector<int>& v, int begin, int end) {
    if (begin >= end) {
        // do nothing
    } else {
        cout << v[begin] << "\n";
        print_vec(v, begin + 1, end);
    }
}

void print_vec(const vector<int>& v) {
    print_vec(v, 0, v.size());
}

void print_vec_test() {
    cout << "Testing print_vec ...\n";
    vector<int> v = {1, 2, 3, 4};
    print_vec(v);
    cout << "all tests passed\n";
}

Find the biggest number in a vector<int>.

Sample solution:

int max(const vector<int>& v, int begin, int end) {
    if (begin >= end) cmpt::error("empty vector has no max");
    if (end - begin == 1) {
        return v[begin];
    } else {
        return max(v[begin], max(v, begin + 1, end));
    }
}

int max(const vector<int>& v) {
    return max(v, 0, v.size());
}

void max_test() {
    cout << "Testing max ... ";
    vector<int> a = {2};
    vector<int> b = {-2, 1, 4, 0, -10};
    vector<int> c = {1, 2, 3};
    vector<int> d = {-1, -2, -3};
    assert(max(a) == 2);
    assert(max(b) == 4);
    assert(max(c) == 3);
    assert(max(d) == -1);
    cout << "all tests passed\n";
}

Write a function similar to expand_MOMS(n) that expands, n times, the acronym YOPY = Your Own Personal YOPY.

Sample solution:

const string acronym = "YOPY";
const string expansion = "Your Own Personal YOPY";
string expand_YOPY(int n) {
    if (n == 0) {
        return "";
    } else if (n == 1) {
        return expansion;
    } else { // n > 1
        string prev = expand_YOPY(n - 1);
        // replace every occurrence of "MOMS" with its expansion
        int i = prev.find(acronym);
        while (i != string::npos) {
           prev.replace(i, acronym.size(), expansion);
           // search for next acronym after the current one
           i += expansion.size(); // skip over the just-replaced string
                                  // so the acronyms within it are not expanded
           i = prev.find(acronym, i);
        }
        return prev;
    } // if
}

void expand_YOPY_test() {
    cout << "Testing expand_YOPY ... ";
    cout << expand_YOPY(5) << "\n";
    cout << "all tests passed\n";
}

Previous topic

Next topic

Sample Solutions to Recursion Practice Questions¶