Section 3. Recursion

This week’s section exercises continue our exploration of recursion to tackle even more challenging and interesting problems. In particular, many of this week's section problems center around recursive backtracking, a very powerful and versatile problem-solving technique.

Remember that every week we will also be releasing a Qt Creator project containing starter code and testing infrastructure for that week's section problems. When a problem name is followed by the name of a .cpp file, that means you can practice writing the code for that problem in the named file of the Qt Creator project. Here is the zip of the section starter code:

📦 Starter code

1) Recursion Mystery Part 1

Topics: recursive function calls, return value tracing

Code Snippet A

int recursionMystery(int x, int y) {
    if (x < y) {
        return x;
    } else {
        return recursionMystery(x - y, y);
    }
}

For each call to the above recursive function, indicate what value is returned by the function call.

Call                                   Return value  

recursionMystery(6, 13);               ______________
recursionMystery(14, 10);              ______________
recursionMystery(37, 12);              ______________

2) Recursion Mystery Part 2

Topics: recursive function calls, output tracing

void recursionMystery2(int x, int y) {
    if (y == 1) { 
        cout << x;
    } else {
        cout << (x * y) << ", ";
        recursionMystery2(x, y - 1);
        cout << ", " << (x * y);
    } 
}

For each call to the above recursive function, write the output that would be produced, as it would appear on the console.

Call                                   Output
        
recursionMystery2(4, 1);        ___________________________________
recursionMystery2(4, 2);        ___________________________________
recursionMystery2(8, 2);        ___________________________________
recursionMystery2(4, 3);        ___________________________________
recursionMystery2(3, 4);        ___________________________________

3) Recursion Tracing

Topics: Recursion, strings, recursion tracing

Below is a recursive function to reverse a string.

string reverseOf(string s) {
    if (s.empty()) {
        return "";
    } else {
        return reverseOf(s.substr(1)) + s[0];
    }
}

Trace through the execution of reverseOf("stop"), showing recursive call information for each call that’s made and how the final value gets computed.

4) Sum of Squares (squares.cpp)

Topics: Recursion

Write a recursive function named sumOfSquares that takes an int n and returns the sum of squares from 1 to n. For example, sumOfSquares(3)should return 1^2 + 2^2 + 3^2 = 14. If n is negative, you should report an error to that effect.

int sumOfSquares(int n) {
    if (n < 0) {
        error("Value of provided n was negative");
    } else if (n == 0) {
        return 0;
    } else {
        return n * n + sumOfSquares(n-1);
    }
}

5) Random Shuffling (shuffle.cpp)

How might the computer shuffle a deck of cards? This problem is a bit more complex than it might seem, and while it's easy to come up with algorithms that randomize the order of the cards, only a few algorithms will do so in a way that ends up generating a uniformly-random reordering of the cards.

One simple algorithm for shuffling a deck of cards is based on the following idea:

• Choose a random card from the deck and remove it.
• Shuffle the rest of the deck.
• Place the randomly-chosen card on top of the deck. Assuming that we choose the card that we put on top uniformly at random from the deck, this ends up producing a random shuffle of the deck.

Write a function

	   		   string randomShuffle(string input)

that accepts as input a string, then returns a random permutation of the elements of the string using the above algorithm. Your algorithm should be recursive and not use any loops (for, while, etc.).

The header file "random.h" includes a function

                           int randomInteger(int low, int high);

that takes as input a pair of integers low and high, then returns an integer greater than or equal to low and less than or equal to high. Feel free to use that here.

Interesting note: This shuffling algorithm is a variant of the Fisher-Yates Shuffle. For more information on why it works correctly, take CS109!

string randomShuffle(string input) {
    /* Base case: There is only one possible permutation of a string
    * with no characters in it.
    */
    if (input.empty()) {
        return input;
    } else {
        /* Choose a random index in the string. */
        int i = randomInteger(0, input.length() - 1);
        /* Pull that character to the front, then permute the rest of
        * the string.
        */
        return input[i] + randomShuffle(input.substr(0, i) + input.substr(i + 1));
    }
}

void randomShuffle(string &input) {
    if (input == "") return;
    int rand = randomInteger(0, input.length() - 1);
    char chosen = input[rand];
    input.erase(rand, 1);
    randomShuffle(input);
    input = chosen + input;
}

6) Zig Zag (zigzag.cpp)

Topics: Recursion, printing output to console

Write a recursive function named zigzag that returns a string of n characters as follows. The middle character (or middle two characters if n is even) is an asterisk (*). All characters before the asterisks are '<'. All characters after are '>'. Report an error if n is not positive.

Call            Output
zigzag(1)       * 
zigzag(4)       <**> 
zigzag(9)       <<<<*>>>>

string zigzag(int n) {
    if (n < 1) {
        error("The value of n was negative");
    } else if (n == 1) {
        return "*";
    } else if (n == 2) {
        return "**";
    } else {
        return "<" + zigzag(n-2) + ">";
    }
}

7) Double Stack (double.cpp)

Topics: Recursion, Stacks

Write a recursive function named doubleStack that takes a reference to a stack of ints and replaces each integer with two copies of that integer. For example, if s stores {1, 2, 3}, then doubleStack(s) changes it to {1, 1, 2, 2, 3, 3}.

void doubleStack(Stack<int>& s) 
{ 
    if (!s.isEmpty()) {
        int n = s.pop();
        doubleStack(s); 
        s.push(n); 
        s.push(n);
    }
}

8) String Subsequences (subsequence.cpp)

Topics: Recursion, verifying properties

Write a recursive function named isSubsequence that takes two strings and returns true if the second string is a subsequence of the first string. A string is a subsequence of another if it contains the same letters in the same order, but not necessarily consecutively. You can assume both strings are already lower-cased.

Call                                    Output
isSubsequence("computer", "core")       false 
isSubsequence("computer", "cope")       true 
isSubsequence("computer", "computer")   true

bool isSubsequence(string big, string small) 
{ 
    if (small.empty()) {
        return true;
    } else if (big.empty()) {
        return false;
    } else {
        if (big[0] == small[0]) {
            return isSubsequence(big.substr(1), small.substr(1));
        } else {
            return isSubsequence(big.substr(1), small);
        } 
    }
}

9) Recursion and Time Complexity and Exponents, (Big-)Oh My

Topics: recursion, time complexity, big O, algorithm comparison

Below is a simple function that computes the value of m^n when n is a nonnegative integer:

int raiseToPower(int m, int n) {
    int result = 1;
    for (int i = 0; i < n; i++) {
        result *= m;
    }
    return result;
}

1) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

2) If it takes 1 microsecond (μs) to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?

Below is a recursive function that computes the value of m^n when n is a nonnegative integer:

int raiseToPower(int m, int n) {
    if (n == 0) return 1;
    return m * raiseToPower(m, n - 1);
}

3) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

4) If it takes 1μs to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?

Here’s an alternative recursive function for computing m^n that uses a technique called exponentiation by squaring. The idea is to modify the recursive step as follows:

• If n is an even number, then we can write n as n = 2k. Then m^n = m^(2k) = (m^k)^2.
• If n is an odd number, then we can write n as n = 2k + 1. Then m^n = m^(2k+1) = m * m^(2k) = m * (m^k)^2.

Based on this observation, we can write this recursive function:

int raiseToPower(int m, int n) {
    if (n == 0) {
        return 1;
    } else if (n % 2 == 0) {
        int halfPower = raiseToPower(m, n / 2);
        return halfPower * halfPower;
    } else {
        int halfPower = raiseToPower(m, n / 2);
        return m * halfPower * halfPower;
    }
}

5) What is the big-O complexity of the above function, written in terms of m and n? You can assume that it takes time O(1) to multiply two numbers.

6) If it takes 1μs to compute raiseToPower(100, 100), approximately how long will it take to compute raiseToPower(200, 10000)?