# Section3: Recursion!

Section materials curated by our Head TA Trip Master,
drawing upon materials from previous quarters. Special thanks to

Nick Bowman
and Julie Zelenski for awesome ideas!

This weekâ€™s section exercises explore the topic of recursion! You'll learn how to utilize self-similarity to solve solve difficult problems elegantly!

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*

```
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 Output
recursionMystery(6, 13); ______________
recursionMystery(14, 10); ______________
recursionMystery(37, 12); ______________
```

```
6
4
1
```

## 2) Recursion Mystery Part 2 Electric Boogaloo

*Topics: recursive function calls, output tracing*

```
void recursionMysteryBoogaloo(int x, int y) {
if (y == 1) {
cout << x;
} else {
cout << (x * y) << ", ";
recursionMysteryBoogaloo(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
recursionMysteryBoogaloo(4, 1); ___________________________________
recursionMysteryBoogaloo(4, 2); ___________________________________
recursionMysteryBoogaloo(8, 2); ___________________________________
recursionMysteryBoogaloo(4, 3); ___________________________________
recursionMysteryBoogaloo(3, 4); ___________________________________
```

```
4
8, 4, 8
16, 8, 16
12, 8, 4, 8, 12
12, 9, 6, 3, 6, 9, 12
```

## 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")`

along the lines of what we did in lecture, showing recursive call information for each call thatâ€™s made and how the final value gets computed.

Our initial call to `reverseOf("stop")`

fires off a call to `reverseOf("top")`

. This call fires off a call to `reverseOf("op")`

. This in turn calls `reverseOf("p")`

. This in turn calls `reverseOf("")`

. This triggers the base case and returns the empty string. (Notice that the reverse of the empty string `""`

is indeed the empty string `""`

). We now append `p`

to return `"p"`

. We now append `o`

to return `"po"`

. We append `t`

to return `"pot"`

. And finally we append `s`

to return `"pots"`

back to whoever called us. Yay!

## 4) Human Pyramids (`pyramid.cpp`

)

*Topics: Recursion*

A human pyramid is a triangular stack of a bunch of people where each person (except the person at the top) supports their weight on the two people below them. A sample human pyramid is shown below.

Your task is to write a function

```
int peopleInPyramidOfHeight(int n)
```

that takes as input the height of the human pyramid (the number of layers; the pyramid above has height three) and returns the number of people in that pyramid.

Your function should be completely recursive and should not involve any loops of any sort. As a hint, think about what happens if you take the bottom layer off of a human pyramid.

Once youâ€™ve written your solution, trace through the execution of `peopleInPyramidOfHeight(3)`

similarly to how we traced through other recursive function calls in class, showing each function call and how values get returned.

As a note, thereâ€™s a closed-form solution to this problem (you can directly compute how many people are in the pyramid just from the height through a simple formula). Itâ€™s described in the solutions.

The key recursive insight here is that a human pyramid of height 0 is a pyramid of no people, and that a human pyramid of height `n`

is a group of `n`

people supporting a human pyramid of `n-1`

people. Using that idea, we can write this function:

```
int peopleInPyramidOfHeight(int n) {
if (n == 0) {
return 0;
} else {
return n + peopleInPyramidOfHeight(n - 1);
}
}
```

As a note, you can directly evaluate `peopleInPyramidOfHeight(n)`

by computing `n(n + 1) / 2`

.

## 5) 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);
}
}
```

## 6) 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!

Here is one possible solution:

```
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));
}
}
```

This function is based on the recursive observation that there is only one possible random shuffle of the empty string (namely, itself), and then using the algorithm specified in the handout for the recursive step.

Here is another possible solution (using a modified function header) which shows how to implement this function using references and no return value. Shoutout to one of our awesome SLs, Rachel Gardner, for this alternate solution!

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

## 7) 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) + ">";
}
}
```

# đź›‘Note:đź›‘ The material beyond this point is a flavor of recursion called "Backtracking", which we'll discuss on Thursday

## 8) Win some, lose sum (`sum.cpp`

)

*Topics: recursive backtracking*

Write a recursive function named `canMakeSum`

that takes a reference to a `Vector<int>`

and an `int`

target value and returns true if it is possible to have some selection of values from the `Vector`

that sum to the target value. In particular, you should be implementing a function with the following declaration

```
bool canMakeSum(Vector<int>& values, int target)
```

For example, let's say that we executed the following code

```
Vector<int> nums = {1,1,2,3,5};
canMakeSum(nums, 9)
```

We should expect that the call to `canMakeSum`

should return true. Given the values specified in `nums`

, we can select 1, 3, and 5 such that `5 + 3 + 1 = 9`

.

However, let's say that we executed the following code instead

```
Vector<int> nums = {1,4,5,6};
canMakeSum(nums, 8);
```

We should expect that the call to `canMakeSum`

in this case should return false, since there is no possible combination of values from the vector that sum up to the target value of 8.

```
bool canMakeSumHelper(Vector<int>& v, int target, int cur, int index) {
if (index >= v.size()) {
return cur == target;
}
return canMakeSumHelper(v, target, cur + v[index], index + 1) ||
canMakeSumHelper(v, target, cur, index + 1);
}
bool canMakeSum(Vector<int>& v, int target) {
return canMakeSumHelper(v, target, 0, 0);
}
```

## 9) Weights and Balances (`weights.cpp`

)

*Topics: recursive backtracking*

measured, and priced everything; for whom

what could not be weighed, measured, and

priced had no existence.

â€”Charles Dickens, Little Dorrit, 1857

In Dickensâ€™s time, merchants measured many commodities using weights and a two-pan balance â€“ a practice that continues in many parts of the world today. If you are using a limited set of weights, however, you can only measure certain quantities accurately.

For example, suppose that you have only two weights: a 1-ounce weight and a 3-ounce weight. With these you can easily measure out 4 ounces, as shown below:

Itâ€™s more interesting to discover that you can also measure out 2 ounces by shifting the 1-ounce weight to the other side, as follows below:

Write a recursive function

```
bool isMeasurable(int target, Vector<int>& weights)
```

that determines whether it is possible to measure out the desired target amount with a given set of weights, which is stored in the vector weights.

As an example, the function call

```
Vector<int> weights = {1, 3};
isMeasurable(2, weights);
```

should return `true`

because it is possible to measure out two ounces using the sample weight set as illustrated in the preceding diagram. On the other hand, calling

```
Vector<int> weights = {1, 3};
isMeasurable(5, weights);
```

should return `false`

because it is impossible to use the 1- and 3-ounce weights to add up to 5 ounces. However, the call

```
Vector<int> weights = {1, 3, 7};
isMeasurable(6, weights);
```

should return true: you can measure the six-ounce weight by placing it and the one-ounce weight on one side of the scale and the seven-ounce weight on the other.

Hereâ€™s a function question to ponder: letâ€™s say that you get to choose n weights. Which ones would you pick to give yourself the best range of weights that youâ€™d be capable of measuring?

```
bool isMeasurable(int target, Vector<int>& weights) {
if (weights.isEmpty()) {
return target == 0; // base case; no weights left to place
} else {
int last = weights[weights.size() - 1]; //using last index is fastest
weights.remove(weights.size() - 1);
// "choose and explore" all of the three possibilities
bool result = isMeasurable(target + last, weights) ||
isMeasurable(target - last, weights) ||
isMeasurable(target, weights);
// un-choose
weights.add(last);
return result;
}
}
```

## 10) Change We Can Believe In (`change.cpp`

)

In the US, as is the case in most countries, the best way to give change for any total is to use a greedy strategy â€“ find the highest-denomination coin thatâ€™s less than the total amount, give one of those coins, and repeat. For example, to pay someone 97Â˘ in the US in cash, the best strategy would be to

- give a half dollar (50Â˘ given, 47Â˘ remain), then
- give a quarter (75Â˘ given, 22Â˘ remain), then
- give a dime (85Â˘ given, 12Â˘ remain), then
- give a dime (95Â˘ given, 2Â˘ remain), then
- give a penny (96Â˘ given, 1Â˘ remain), then
- give another penny (97Â˘ given, 0Â˘ remain).

This uses six total coins, and thereâ€™s no way to use fewer coins to achieve the same total.

However, itâ€™s possible to come up with coin systems where this greedy strategy doesnâ€™t always use the fewest number of coins. For example, in the tiny country of Recursia, the residents have decided to use the denominations 1Â˘, 12Â˘, 14Â˘, and 63Â˘, for some strange reason. So suppose you need to give back 24Â˘ in change. The best way to do this would be to give back two 12Â˘ coins. However, with the greedy strategy of always picking the highest-denomination coin thatâ€™s less than the total, youâ€™d pick a 14Â˘ coin and ten 1Â˘ coins for a total of fifteen coins. Thatâ€™s pretty bad!

Your task is to write a function

```
int fewestCoinsFor(int cents, Set<int>& coins)
```

that takes as input a number of cents and a Set

You can assume that the set of coins always contains a 1Â˘ coin, so you never need to worry about the case where itâ€™s simply not possible to make change for some total. You can also assume that there are no coins worth exactly 0Â˘ or a negative number of cents. Finally, you can assume that the number of cents to make change for is nonnegative.

Makes cents? I certainly hope so.

The idea behind this solution is the following: if we need to make change for zero cents, the only (and, therefore, best!) option is to use 0 coins. Otherwise, we need to give back at least one coin. Whatâ€™s the first coin we should hand back? We donâ€™t know which one it is, but we can say that itâ€™s got to be one of the coins from our options and that that coin canâ€™t be worth more than the total. So weâ€™ll try each of those options in turn, see which one ends up requiring the fewest coins for the remainder, then go with that choice. The code for this is really elegant and is shown here:

```
/**
* Given a collection of denominations and an amount to give in change, returns
* the minimum number of coins required to make change for it.
*
* @param cents How many cents we need to give back.
* @param coins The set of coins we can use.
* @return The minimum number of coins needed to make change.
*/
int fewestCoinsFor(int cents, Set<int>& coins) {
/* Base case: You need no coins to give change for no cents. */
if (cents == 0) {
return 0;
}
/* Recursive case: try each possible coin that doesnâ€™t exceed the total as
* as our first coin.
*/
else {
int bestSoFar = cents + 1; // Can never need this many coins;
for (int coin: coins) {
/* If this coin doesnâ€™t exceed the total, try using it. */
if (coin <= cents) {
bestSoFar = min(bestSoFar,
fewestCoinsFor(cents - coin, coins));
}
}
return bestSoFar + 1; // For the coin we just used.
}
}
```