The Problem

Below are a series of problems you need to solve usingrecursive functions. You will write a program thatwill read commands from an input file, with each command referringto one of the recursive problems to be executed. Each command willbe followed (on the same line of input) by the respectiveparameters required for that problem.

Implementation

Each recursive function MUST have a wrapper function enclosingit where you will do input/output file processing as well ascalling the actual recursive function. From Wikipedia, “A wrapperfunction is a function in a computer program whose main purpose isto call a second function”.   As an example, here is oneof the wrapper functions you will use:

     voidKnightsFlip(FILE *fin, FILE *fout);

This would be the wrapper function for one of the recursiveproblems, called KnightsFlip (described, indetail, below). These wrapper functions will simply do threethings:

1. deal with the processing of the input file
2. most importantly, the wrapper function will make the initialcall to your recursive function that will actually solve theproblem.
3. Finally, the wrapper functions will print to the output file.Note: printing to the output file may also occur in the actualrecursive functions.

Of course, at your own discretion (meaning, your own choice),you can make auxiliary functions for your recursive functions touse, such as functions to swap values in an array, take the sum ofan array of values, printing functions, etc.

Five Problems to Solve UsingRecursion:

(1) KnightsMultiply

Write a recursive function that multiplies all values fromk up to n and returns the result (as a double).For example: if k = 5, and n = 10, then multiply5 * 6 * 7 * 8 * 9 * 10 to return 151200.

(2) KnightsFlip

You have an index card with the letter K written on one side,and F on the other. You want to see ALL of the possible ways thecard will land if you drop it n times. Write a recursivefunction that prints each session of dropping the cards with K'sand F's.   For example of you drop it 4 times in a givensession, all possible ways to drop it are as follows:

KKKK

KKKF

KKFK

KKFF

KFKK

KFKF

KFFK

KFFF

FKKK

FKKF

FKFK

FKFF

FFKK

FFKF

FFFK

FFFF

*Note: The possible ways would have to print in this specificorder.

(3) KnightsShape

Simply write a recursive function that prints a large X composedof smaller X's with a given “width”, n, which isguaranteed to be odd. Example for an X of width n = 7:

X     X

X   X   X X

   X

X X

X   X

X     X

*Note: to be clear, the “width” is the length (number) of X’salong one line of the large X.

(4) KnightsScotch

No, this has nothing to do with drinking Scotch! Suppose you areplaying a special game of hopscotch on a line of integer numbersdrawn on the ground like so:

           4 4 1 5 2 6 3 4 2 0

The number, with a square around it, indicates where you arecurrently standing. You can move left or right down the line byjumping the number of spaces indicated by the number you arestanding on. So if you are standing on a 4, you can jump eitherleft 4 spaces or right 4 spaces. You cannot jump past either end ofthe line.

For example, the first number (4) only allows you to jump right,since there are no numbers to the left that you can jump to.

The goal: you want to get to the 0 at the farend (right side) of the line. You are also guaranteed that therewill be only one zero, which, again, will be at the far rightside.

Here is how you do that with the above line:

Starting         4 4 1 5 2 6 3 4 2 0 position

^{Step 1:            Â} 4 4 1 5 2 6 3 4 2 0

Jump right

^{Step 2:            Â} 4 4 1 5 2 6 3 4 2 0

Jump left

^{Step 3:            Â} 4 4 1 5 2 6 3 4 2 0

Jump right

^{Step 4:            Â} 4 4 1 5 2 6 3 4 2 0

Jump right

^{Step 5:            Â} 4 4 1 5 2 6 3 4 2 0

Jump left

^{Step 6:            Â} 4 4 1 5 2 6 3 4 2 0

Jump right

Some KnightsScotch lines have multiple paths to 0 from the givenstarting point. Other lines have no paths to 0, such as thefollowing:

3 1 2 3 0

In this line, you can jump between the 3's, but not anywhereelse.

You are to write a recursive function that returns an integer 1(for solvable) or 0 (for not solvable), indicating if you are ableto get to the rightmost 0 or not.

(5) KnightsDepot

You are working on an engineering project with other studentsand are in need of 2x4s (2 by 4’s) of various lengths. Thankfully,UCF has its very own “Depot” store: KnightsDepot…so you don’t haveto drive far. Unfortunately, KnightsDepot only carries 2x4s infixed lengths. So your team will have to purchase the 2x4s and thencut them as needed. Because of your tight college student budget,you want to buy the least number of 2x4s in orderto cover the lengths requested by your team.

The recursive function you are designing will return the minimumnumber of 2x4s you need to purchase, in order to cover the lengthsrequested by your team. Example:

Array of 2x4 lengths requested by your team: { 6, 4, 3,4, 1, 3 }

Fixed length of 2x4s at KnightsDepot: 6 (soeach purchased 2x4 has a length of 6)

A possible arrangement of of 2x4s: { 6 } { 3, 3 } { 4, 1} { 4 }

Minimum number of 2x4s needed to purchase:4

Wrapper Functions

As mentioned, you MUST use the following five wrapper functionsEXACTLY as shown:

     voidKnightsMultiply(FILE *fin, FILE *fout); void KnightsFlip(FILE *fin,FILE *fout); void KnightsShape(FILE *fin, FILE *fout); voidKnightsScotch(FILE *fin, FILE *fout); void KnightsDepot(FILE *fin,FILE *fout);

Input File Specifications

You will read in input from a file,\"KnightsRecurse.in\". Have this AUTOMATED. Do not ask theuser to enter “KnightsRecurse.in”. You should read in thisautomatically (this will expedite the grading process). The filewill contain an arbitrary number of lines and on each line therewill be a command. Each command will be followed by relevant dataas described below (and this relevant data will be on the same lineas the command).

We will not tell you the number of commands in the file. So howdo you know when you’ve read all the commands in the input file?You can use the function feof(FILE * file) todetermine if you have reached the end of the file.

The commands (for the five recursive functions), and theirrelevant data, are described below:

KnightsMultiply - This command will be followed by the followinginformation: k and then n, as describedabove.

KnightsFlip - This command will be followed by a single integer,n, as described above.

KnightsShape - This command will be followed by a singleinteger, n, as described above.

KnightsScotch - This command will be followed by an integer,start, representing the initial position on the line you areplaying on (0 means the far left, the first position); size, thenumber of integers drawn on the ground; size will be followed bysize number of integers, the integers drawn on the ground. (seeinput file for examples)

KnightsDepot - This command will be followed by an integermaxlen, which represents the maximum 2x4 length the store sells;size, the number of 2x4s your team needs; size will be followed bysize number of integers, the length of each 2x4 your team needs. Itis guaranteed that the requested lengths will all be less than orequal to the maxlen sold by the store.