- Questions & Answers
- Accounting
- Computer Science
- Automata or Computationing
- Computer Architecture
- Computer Graphics and Multimedia Applications
- Computer Network Security
- Data Structures
- Database Management System
- Design and Analysis of Algorithms
- Information Technology
- Linux Environment
- Networking
- Operating System
- Software Engineering
- Big Data
- Android
- iOS
- Matlab

- Economics
- Engineering
- Finance
- Thesis
- Management
- Science/Math
- Statistics
- Writing
- Dissertations
- Essays
- Programming
- Healthcare
- Law

- Log in | Sign up

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

your code. The existence of block comments (comments written like the one

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

points. Please replace all block comments with line comments (

).

There are 3 files:

• recursiveFuncs.h

• recursiveFuncs.cpp (your code here)

• 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.PDF## Answer To This Question Is Available To Download

- Design and write a Java program to read the file system beneath a particular folder, and store it in a tree data structure. Description: Requirements: Your program should be able to look at a folder...SolvedMay 14, 2022
- JUST TO REMIND THAT THE NUMBER ONE ONLY NEED 150 WORDS AND NUMBER TWO FOR 1100 WORDS KINDLY MAKE SURE THAT THE NUMBER TWO HAS ABSTRACT AND USING INTEXT CITATION, THE NUMBER 1, I WILL BE USING IT IN...SolvedMay 12, 2022
- CASE STUDY Heartland Equestrian Centre App Project Heartland Equestrian Centre located in Macedon Ranges, Victoria. It offers a full service boarding facility geared towards the needs of riders and...SolvedMay 10, 2022
- Hello, this is a programming assignment with the details enclosed in the pdf below, the zip file is the work I have done on it so far. In the pdf if you scroll all the way to the bottom it breaks down...SolvedMay 08, 2022
- Task Summary You will be provided with a Microsoft excel .csv file. This file contains a large volume of data. You must develop an executable that respects the permissions and rules that the file has...SolvedMay 08, 2022
- I will attach file in chat Simple add functionality to navigation that opens page and writes logic to make buttons call specific functions. i will complete functions so do not touch the functions in...SolvedMay 08, 2022
- Please do in java andmake sure to include all the required files (README, source files).SolvedMay 07, 2022
- Assignment in file.SolvedMay 07, 2022
- Assessment Details and Submission Guidelines Semester 1 Unit Code ICT 205 Unit Title Mobile Application Development Assessment Type Individual Assessment Assessment Title Laboratory Session Week 8...SolvedMay 07, 2022
- Guide to Project for Supervisors ITECH 7401 LEADERSHIP IN IT PROJECT MANAGEMENT ITECH 1103 BIG DATA AND ANALYTICS Assignment: SQL Database Overview The purpose of this task is to develop student’s...SolvedMay 07, 2022

Copy and Paste Your Assignment Here

About Us | Contact Us | Help | Privacy Policy | Revision and Refund Policy | Terms & Conditions | Honor Code

Copyright © 2022. All rights reserved.