Please follow directions of format.PNG and the PDF
Here is youtube link for the assignment:https://www.youtube.com/watch?v=oPu9l5Lr0MU
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 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 similar to the for and while loops you use in your programs. In fact, anything that can be solved recursively can also be solved iteratively (Church-Turing Thesis). Recursive functions solve problems by breaking larger problems into smaller 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 number 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="" -="" 1)="" +="" fibonacci(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="" reduction="" 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="" breaks="" 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(1))="" +="" (f(1)="" +="" f(0))="" f(4)="((f(1)" +="" f(0))="" +="" f(1))="" +="" (f(1)="" +="" f(0))="" f(4)="((1" +="" f(0))="" +="" f(1))="" +="" (f(1)="" +="" f(0))="" f(4)="((1" +="" 0)="" +="" f(1))="" +="" (f(1)="" +="" f(0))="" f(4)="((1" +="" 0)="" +="" 1)="" +="" (f(1)="" +="" f(0))="" f(4)="((1" +="" 0)="" +="" 1)="" +="" (1="" +="" f(0))="" f(4)="((1" +="" 0)="" +="" 1)="" +="" (1="" +="" 0)="" f(4)="1" +="" 0="" +="" 1="" +="" 1="" +="" 0="" 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.="" bubble="" 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="" array.="" 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="" arrays="" 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="" your="" 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="" below:)="" 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="" brackets,="" 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="" currentindex="" ,="" unsigned="" int="" strlen="" ,="" bool="" left="" ,="" bool="" right);="" write="" a="" function="" to="" count="" the="" number="" of="" times="" a="" specific="" character="" c="" appears="" in="" a="" character="" array.="" you="" will="" be="" provided="" the="" character="" array,="" the="" character="" to="" search="" for,="" the="" current="" index="" that="" is="" being="" looked="" at,="" the="" length="" of="" the="" character="" array,="" 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 currentindex. if the right bool is true, then you must still count all the characters to the right of the currentindex. 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 currentheight , unsigned int currentwidth , unsigned int height , unsigned int width , char balloon); 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 color that are adjacent to the balloon (up, left, right, down). observe the grid below with yellow balloons, blue balloons, and red balloons: 1 | 0 1 2 3 4 5 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 blue balloon touching the initial balloon. those other blue balloons would then pop their adjacent neighbors too, etc. 1 | 0 1 2 3 4 5 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 | 0 1 2 3 4 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 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="" currentindex.="" if="" the="" right="" bool="" is="" true,="" then="" you="" must="" still="" count="" all="" the="" characters="" to="" the="" right="" of="" the="" currentindex.="" 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="" currentheight="" ,="" unsigned="" int="" currentwidth="" ,="" unsigned="" int="" height="" ,="" unsigned="" int="" width="" ,="" char="" balloon);="" 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="" color="" that="" are="" adjacent="" to="" the="" balloon="" (up,="" left,="" right,="" down).="" observe="" the="" grid="" below="" with="" yellow="" balloons,="" blue="" balloons,="" and="" red="" balloons:="" 1="" |="" 0="" 1="" 2="" 3="" 4="" 5="" 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="" blue="" balloon="" touching="" the="" initial="" balloon.="" those="" other="" blue="" balloons="" would="" then="" pop="" their="" adjacent="" neighbors="" too,="" etc.="" 1="" |="" 0="" 1="" 2="" 3="" 4="" 5="" 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="" |="" 0="" 1="" 2="" 3="" 4="" 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’);="">