# CS 202 - S22 - Assignment 7 Mr. Piotrowski Recursion 1 Assignment Introduction Welcome to Assignment 7! This assignment will be a little different than your previous assignments because there will be...

CS 202 - S22 - Assignment 7
Mr. Piotrowski
Recursion
1 Assignment Introduction
Welcome to Assignment 7! This assignment will be a little different than you
previous assignments because there will be no use of classes. The only goal of
this assignment is to practice recursion.
1
1.1 Brief Description of Recursion
Recursive Function (programming): Any function in which the function
definition includes a call to itself.
Recursion is a method for solving problems. The closest related thing to recur-
sion that you may find familiar is iteration. Recursion can be thought of simila
to the for and while loops you use in your programs. In fact, anything that can
e solved recursively can also be solved iteratively (Church-Turing Thesis).
Recursive functions solve problems by
eaking larger problems into smalle
problems. Before we describe more about how recursive functions work, let’s
look at an example.
Example: The Fibonacci Sequence
f(n) = f(n− 1) + f(n− 2)
where:
f(0) = 0, f(1) = 1
Observe the Fibonacci function above. This function only takes one numbe
from the set of positive integers N (where n ∈ N) as a parameter. The C++
code for this function may look like:
1 unsigned int fibonacci(unsigned int n){
2 if(n <= 1){
3 return n;
4 }
5 return fibonacci(n XXXXXXXXXXfibonacci(n - 2);
6 }
This function is recursive because the definition includes at least one call to
itself (on line 5 ).
Any function can be recursive just by including a call to itself, but this does
not make it useful. In computer science, a finite recursive function is really
the only recursive function we care about. Any function that flat out calls itself
without any extra work results in an infinite recursion:
1 void foo(){
2 foo();
3 }
Assuming this function is called, under what condition does the function stop
calling itself? This recursive function is a infinite because there is no condition.
2
All finite recursive functions include the following 3 things:
1. At least one call to itself.
2. At least one base case.
3. At least one reduction operation.
A base case stops the recursion from continuing and the reduction opera-
tion is some work that takes the recursive function closer to the base case.
Looking back at the fibonacci function, this function has 2 base cases. In the
case that n is either 1 or 0, the function returns 1 or 0 and does not recurse. The
eduction operations are the (n − 1) and (n − 2) within the recursive function
calls. These operations ensure that n will eventually reach the base cases of
either 0 or 1.
As previously mentioned, recursion
eaks larger problems into smaller ones.
With the fibonacci function, what is the smallest problem? It is in fact the base
cases, and the work done by this function is the addition of a bunch of ones and
zeroes. Observe below:
f(4) = f(3) + f(2)
f(4) = (f(2) + f(1)) + f(2)
f(4) = (f(2) + f XXXXXXXXXXf(1) + f(0))
f(4) = ((f(1) + f(0)) + f XXXXXXXXXXf(1) + f(0))
f(4) = ((1 + f(0)) + f XXXXXXXXXXf(1) + f(0))
f(4) = XXXXXXXXXXf XXXXXXXXXXf(1) + f(0))
f(4) = XXXXXXXXXXf(1) + f(0))
f(4) = XXXXXXXXXX + f(0))
f(4) = XXXXXXXXXX + 0)
f(4) = XXXXXXXXXX
f(4) = 3
Note this is a very inefficient way to solve this problem. Recursion always
uses more resources than iteration, thus, recursion really should only be used if
problems are difficult to solve with loops, or if the algorithm is faster than the
loop solution (for example, quick sort vs. bu
le sort).
3
Recursive functions can be represented with a tree diagram, which shows how
the recursive function calls itself. Let us use the same example of fibonacci(4):
We can see that this function is called 9 times to completely solve the problem.
We can also see that this tree is binary or 2-ary as each recursive case will call
itself at most twice (each node has 2 children). Functions that call themselves
at most once can be represented with a unary or 1-ary tree, and any recursive
function that calls itself at most z times would make a z-ary tree.
2 Program Flow
Your goals are to write 5 recursive functions to solve the following problems:
1. Integer exponentiation. (nx)
2. Counting the number of times a character c appears in a character a
ay.
3. Popping Balloons and adjacent balloons of the same color in a 2D grid.
4
4. Counting the number of non-space characters in a sentence that is stored
in a 2-dimensional character pointer.
5. Merging 2 alphabetical character a
ays in alphabetical order (whilst also
counting the total number of chars).
There is no particular flow. Each function you write will be tested individually
on multiple test cases.
3 Coding The Assignment
Important Note: The codegrade for this assignment automatically checks to
see if the function you wrote is recursive. If you code a solution to the function
that is not recursive, codegrade will not give you points! In order to check you
functions for recursive function calls, I had to write a python script that reads
elow:)
1 /* This is a block comment *
make it very difficult for my script to verify that your function is truly recursive,
so you may NOT use block comments for this assignment. If there are
any block comment symbols ( /* and */ ), codegrade will not give you any
).
There are 3 files:
• recursiveFuncs.h
• main.cpp
The function skeletons are already provided for you in the recursiveFuncs.cpp
file. You may not alter the parameters for any of the functions.
For each function, I have included the number of lines I used in my solution.
This includes lines that are just
ackets, so, the number of lines that actually do
something in my functions are anywhere between 1/3 and 1/2 the number you
will see. The number is there to remind you not to overthink. If your functions
start going way over the number of lines I used, you are likely overthinking and
need to re-approach the problem.
5
3.1 Integer Exponentiation
INSTRUCTOR SOLUTION LINE COUNT: 4
1 unsigned int integerPow(unsigned int num , unsigned int pow);
Write a function to calculate numpow. The first parameter is the number and
the second parameter is the exponent. The function will be called like this:
1 unsigned int result = integerPow (2,3);
2^3 = 8
Exponentiation is just the repeated multiplication of a number. 23 is just 2∗2∗2.
That is also just (2∗20)∗ (2∗20)∗ (2∗20) which gives you (2∗1)∗ (2∗1)∗ (2∗1).
1. What are your base case(s)?
2. What are your reduction operation(s)?
3. Draw the tree diagram for this function when called for 34.
4. What kind of tree does your function make?
6
3.2 Counting Specific Characters
INSTRUCTOR SOLUTION LINE COUNT: 11
1 unsigned int countCharacter(char *str , char c, unsigned int
cu
entIndex , unsigned int strLen , bool left , bool right);
Write a function to count the number of times a specific character c appears in
a character a
ay. You will be provided the character a
ay, the character to
search for, the cu
ent index that is being looked at, the length of the characte
a
ay, and the 2 directions to search as parameters. This function should work
no matter what index is provided as a starting position. For example:
1 const unsigned int strLen = 30;
2 char str[strLen] = "hello and welcome to my guide!";
3
4 cout
countCharacter(str , ’m’, 0, strLen , true , true)
endl;
5 cout
countCharacter(str , ’m’, 5, strLen , true , true)
endl;
6 cout
countCharacter(str , ’m’, 20, strLen , true , true)
endl;
7 cout
countCharacter(str , ’m’, 29, strLen , true , true)
endl;
8
9 cout
countCharacter(str , ’e’, 0, strLen , true , true)
endl;
10 cout
countCharacter(str , ’e’, 5, strLen , true , true)
endl;
11 cout
countCharacter(str , ’e’, 20, strLen , true , true)
endl;
12 cout
countCharacter(str , ’e’, 29, strLen , true , true)
endl;
The code above should print:
1 2
2 2
3 2
4 2
5 4
6 4
7 4
8 4
The purpose of the bools is to help you stop the recursion. If the left bool is
true, then you must still count all the characters to the left of the cu
entIndex.
If the right bool is true, then you must still count all the characters to the right
of the cu
entIndex.
1. What are your base case(s)?
2. What are your reduction operation(s)?
3. Draw the tree diagram for this function when called as countCharac-
ter(”las vegas”, ’s’, 0, strLen).
4. What kind of tree does your function make?
7
3.3 Popping Balloons
INSTRUCTOR SOLUTION LINE COUNT: 10
1 void popBalloons(char **grid , unsigned int cu
entHeight , unsigned
int cu
entWidth , unsigned int height , unsigned int width , cha
alloon);
Given a 2d grid of balloons, the coordinates of a specific balloon in the grid,
and the color of a balloon, pop that balloon and all balloons of the same colo
that are adjacent to the balloon (up, left, right, down). Observe the grid below
with yellow balloons, blue balloons, and red balloons:
1 | XXXXXXXXXX
2 ----------------------
3 0 | [Y][Y][Y][Y][Y][Y]
4 1 | [Y][B][B][B][B][Y]
5 2 | [Y][B][R][R][B][Y]
6 3 | [Y][B][B][B][B][Y]
7 4 | [Y][Y][Y][Y][Y][Y]
8 ----------------------
9 |
If this function were to be called like this:
1 popBalloons(grid , 3, 3, 5, 6, ’B’);
The blue balloon at [3][3] would pop and set off a chain reaction to pop every
lue balloon touching the initial balloon. Those other blue balloons would then
pop their adjacent neighbors too, etc.
1 | XXXXXXXXXX
2 ----------------------
3 0 | [Y][Y][Y][Y][Y][Y]
4 1 | [Y][ ][ ][ ][ ][Y]
5 2 | [Y][ ][R][R][ ][Y]
6 3 | [Y][ ][ ][ ][ ][Y]
7 4 | [Y][Y][Y][Y][Y][Y]
8 ----------------------
9 |
8
The function does not consider diagonals. Example below:
1 | XXXXXXXXXX
2 -------------------
3 0 | [Y][Y][Y][Y][Y]
4 1 | [Y][Y][B][B][B]
5 2 | [Y][B][Y][Y][Y]
6 -------------------
7 |
1 popBalloons(grid , 2, 4, 3, 5, ’Y’);
1
Answered 1 days AfterApr 08, 2022

## Solution

Vaibhav answered on Apr 09 2022
SOLUTION.PDF