EE 312 - Project 7 - Recursion

A reminder of the course academic honesty policy:
You may not acquire from any source (e.g., another student or an internet site) a partial or complete solution to a problem or project that has been assigned. You may NOT show other students your solution to an assignment. You may not have another person "walk you through" how to solve an assignment, or walk another student through the solution. You may get help from the instructional staff. You may discuss general ideas and approaches. Review the class policy on collaboration from the syllabus. I will run plagiarism detection software on project submissions. If you cheat, you will receive a 0 on all programming projects and I will submit a report to the office of the dean of students. If you provide your solution to another student, you are as guilty of cheating as the other student.

Make sure that you follow the EE 312 style guide. You will lose points if you do not.

Include the following at the top of your file: 
// Recursive.c -- EE 312 Project 7

/* Student information for project:
 *
 * Replace <NAME> with your name.
 *
 * On my honor, <NAME>, this programming project is my own work
 * and I have not provided this code to any other student.
 *
 * Name:
 * email address:
 * UTEID:
 * Section 5 digit ID:
 * Number of slip days used on this assignment.
 */


Your code must be written in C. In addition to using a #include for Recursive.h, you may include <stdio.h>, <stdbool.h> and <string.h> in your Recursive.c file. The only function you are allowed to use from <string.h> is strlen().

The purpose of this assignment is to practice writing recursive algorithms and implementing them in C. You will implement recursive solutions to the problems described below. You must write recursive functions to receive credit.

You are required to include prototypes for all helper functions at the top of your Recursive.c file. The prototypes for required functions are in Recursive.h. For the required functions described below, use the provided prototype, exactly as it is in the descriptions and in Recursive.h. Test code should be placed in a separate .c file, e.g., RecursiveTester.c. Your Recursive.c file must NOT contain a main function. You are not allowed to use any globals or statics in your solutions. Your program must compile and run correctly on the LRC machines in order to receive credit. Do not wait until the last minute to test your program on kamek.

I've provided a file that contains some tests. These tests are not sufficient for checking correctness. You must write your own tests, as well. The tests in RecursiveTester.c are just to get you started.

Problem descriptions of the functions you will write:

1. Binary Conversion
int getBinary(int n)
Write a recursive function that returns the base 2 representation of int n. You may assume that n is non-negative.

2. isPalindrome
bool isPalindrome(char *s)
Write a recursive function that returns true if str is a palindrome, and false otherwise.

3. nextIsDouble
int nextIsDouble(int data[], int N)
This function returns the number of elements in data that are directly followed by double that element.

For example, if the array {1, 2, 4, 8, 16, 32, 64, 128, 256} was passed to the function, the function would return 8, since 2 is 2*1, 4 is 2*2, 8 is 2*4, etc.

Given the array {1, 3, 4, 2, 32, 8, 128, -5, 6}, the function would return 0. No element of the array is immediately followed by double that element.

Given {1, 0, 0, -5, -10, 32, 64, 128, 2, 9, 18}, the function would return 5. The elements 0, -5, 32, 64, and 9 are all followed directly by double their value.

Write a helper function that is passed an index into the array. This is where the recursion takes place. The nextIsDouble function calls the helper function.

4. Water flowing off a map
bool canFlowOff(int M, int N, int map[M][N], int row, int col)


In this problem, an area of land is represented as a two dimensional array of ints. The array element represents the elevation of that point on land. The higher the elevation, the higher the number. A flat plain at an elevation of 100 feet above sea level look like this:

100
 100
 100
 100
 100
 100
 100
 100
 100
 100
100
 100
 100
 100
 100
 100
 100
 100
 100
 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100


A river flowing through a 200 foot  gorge looks like this. Cells that make up the river are shaded gray and yellow.

 

100 99 200 200 200 200 200 200 200 200
200 98 200 200 200 200 200 200 200 200
200 97 96 200 200 200 200 200 200 200
200 200 95 200 200 200 85 84 83 200
200 200 94 93 92 200 86 200 82 200
200 150 200 200 91 200 87 200 81 200
200 200 200 200 90 89 88 200 80 200
200 150 100 200 200 200 200 200 79 200
200 200 200 200 200 200 200 200 78 77
200 200 200 200 200 200 200 200 200 76

 

Function canFlowOff has a parameter that represents a map of elevations as a 2D array of ints. It also has parameters that represent the starting location of a drop of water on the map.

In the first example, the plain, the water in any cell that is not on the border of the array cannot flow to any other cell, since all adjacent cells have the same elevation. Water on any of the border cells could flow off the map. In the second example, if a drop of water started at the cell in row 2, column 2 (the yellow cell) it could eventually flow off the map by following the river. Each segment of the river is one foot lower than the previous.

Recall that water on the border can also flow off. In the second example, if water started at the cell in row 3, column 0 (the red cell), then it can flow off the map. The elevation in that cell is 200. The water cannot flow to any adjacent cell, but that doesn't matter because the cell is on the border.

If the starting cell is row 3, column 1 (the blue cell), the water can flow off the map. That cell has elevation 200. The water cannot flow west or south because those cells also have elevation 200. But the water can flow north or east to the cells in the river. The water falls off the bank into the river, and then off the map via the river.

Finally, the cell at row 6, column 1 (the green cell) cannot flow off the map. It tries north and reaches a dead-end. It cannot move east or west. It tries south, but reaches a dead-end.

When thinking about the problem, it may help to think that off the edge of border rows and columns is an infinitely deep canyon. So if you are on the border (row 0, column 0, last row or last column), then you flow off the map. (Base case?)

canFlowOff returns true if a drop of water starting at the location specified by row, column can reach the edge of the map, false otherwise.

Checklist: Did you remember to

Many thanks to Mike Scott for the idea for this project.