CS211Lab10F12 < CS211

CS211 Web>AssignmentsF12>CS211Lab10F12 (2012-11-14, Main.troy) (raw view)EditAttach
---+ CS 211 - Fall 2012
---+++ <a name="Lab_9"></a> <a name="Lab_9"></a> Lab 10
 Due: Monday, November 12, 2012 
---+++ <a name="Maze_Solver"></a> <a name="Balanced_Symbol_Checker"></a> Recursion
 Recursive code is code that calls itself. This is often a tough concept and many jokes are created about this such as:

The definition of <strong>recursion </strong>in the dictionary is:
<blockquote> see recursion </blockquote> Also if you look up recursion in the index in the back of the K&R C book, one of the page numbers listed is the location of recursion in the index. Even the authors were trying to make light of a difficult subject.

One thing to recall is that recursion is based on induction. So don't forget to define your base case as well as your recusrive case(s).

Often recursion is just another way to create a loop. This is often called "tail recursion".

The following code is a recursive way that the linked list in Lab 9 could have been printed in reverse order with out destroying or modifying the list:
<blockquote> typedef struct nodeStruct<br />{<br /> int x;<br /> int y;<br /> struct nodeStruct *next;<br />} node;<br /><br />void printReversed (node* *head)<br />{<br /> if (head != null) /*NOTE THis should be NOT EQUAL. THe wiki formatting removes the ! */<br /> {<br /> printReversed (head-&gt;next);<br /> printf ("(%d, %d)\n", head-&gt;x, head-&gt;y);<br /> }<br />} </blockquote>

---+++ Lab Assignment 10
 For this lab, write a C program that will implement the following recursive algorithms:

   * factorial
   * fibonacci
   * isPrime
   * Greatest Common Divisor (Using Dijkstra's Algorithm)
   * exponentiation
All of this code can be found on the internet. For a great page check out: [[http://www.arl.wustl.edu/~jst/cse/131/Notes/Recursion/recursion.html][http://www.arl.wustl.edu/~jst/cse/131/Notes/Recursion/recursion.html ]]. Of course, I don't want you just to copy the code from that page, but I want you to understand how it is working!!!

Your program is to prompt the user for an integer value. If the user enters the value of zero, quit the program. If the user enters a value in the range from 1 to 5, perform one of the following operations based on the values given next to the name of the algorithm:
   1 factorial
   1 fibonacci
   1 isPrime
   1 Greatest Common Divisor: "GCD"
   1 exponentiation
If the user gives any other value, print out a menu of values listing the users options.

If the user entered a value from 1 to 5, you will then need to prompt the user for the proper number of inputs. Factorial, fibonacci and isPrime take a single integer as input. GCD and exponentiation take two integers as input. When two input values are given, the user is to enter these values on one line of input.

Verify that the input falls into the proper range of values for the rercursive algorithm. If not print a message stating the required range for the input.

If the input values are valid, perform the algorithm abd print a descriptive message showing the input and the output of the algorithm.
---+++ Recursive Definitions:
 Factorial of n, written as __n!__, is recursively defined as: <blockquote> When n &gt;= 0 
   * n! = 1 if n == 0
   * n! = n * (n-1)! otherwise
</blockquote> Fibonacci of n, written as __fib(n)__, is recursively defined as: <blockquote> When n &gt;= 0 
   * fib(n) = 0 if n == 0
   * fib(n) = 1 if n == 1
   * fib(n) = fib(n-1) + fib(n-2) otherwise
</blockquote> IsPrime of n, written as __isPrime(n)__, is recursively defined with the use of a helper function as follows. Recall: an integer _n_ is prime iff _n_ &gt;= 2 and <em>n</em>'s only factors are 1 and itself:

   * isPrime(n) = FALSE if n &lt; 2
   * isPrime(n) = TRUE if (factorInRange (2, n) == FALSE)
   * isPrime(n) = FALSE otherwise

   * factorInRange (m, n) = FALSE if m &gt;= n
   * factorInRange (m, n) = TRUE if n % m == 0
   * factorInRange (m, n) = factorInRange(m+1, n) otherwise
Greatest Common Demonimator of m and n, written as __gcd(m, n)__, using Dijkstra's Algorithm, is recursively defined as: <blockquote> When m &gt; 0 and n &gt; 0 
   * gcd (m, n) = m if m == n
   * gcd (m, n) = gcd ( m-n, n) if m &gt; n
   * gcd (m, n) = gcd (m, n-m) if m &lt; n
</blockquote> Exponentiation of m and n, written as __exp(m, n)__, has multiple recursive definitions. You must use the following recursive definition: <blockquote> When n &gt;= 0 
   * exp (m, n) = 1 if n == 0
   * exp (m, n) = m if n = 1
   * exp (m, n) = exp (m, n/2) * exp (m, n/2) if n is even
   * exp (m, n) = m * exp (m, n-1) if n is odd
</blockquote> For the even case of exp(m, n), *don't make two recursive calls!* Make one recursive call and store the result in a local temporary variable. Then return the value in the local temporary variable multiplied by itself!

---+++ <a name="Command_Line_Argument_Debug_Mode"></a> <a name="Command_Line_Argument_Debug_Mode"></a> Command Line Argument: Debug Mode
 Your program is to be able to take one optional command line argument, the -d flag. When this flag is given, your program is to run in "debug" mode.

When in debug mode, your program is to have each recursive function print out two messages. These messages will help show how the recursive functions work and how many recursive calls are actually made.
   1 Print out a message as the first line of every recersive function that shows the name of the function and current values of all of the parameters.
   1 Print out a message right before the return that shows the name of the function, the values of the parameters when this instance of the function was called and the value about to be returned. Note to print out the parameters for this call, you may need to save those values in a local temporary variable and then print out these saved values. This will be needed if the recursive function modifies the parameter(s) values while executing the function.
When the flag is not given, this debugging information should not be displayed. One simple way to set up a "debugging" mode is to use a boolean variable which is set to true when debugging mode is turned on but false otherwise. Then usig a simple if statement controls whether information should be output. <blockquote style="margin-top: 0px; margin-right: 0px; margin-bottom: 0px; margin-left: 40px; border-style: none; padding: 0px"> if ( debugMode == TRUE )

<blockquote>

printf (" Debugging Information \n");
</blockquote>

</blockquote>

---++ <a name="Program_Submission"></a> <a name="Program_Submission"></a> Program Submission
 <span style="font-family: arial, verdana, sans-serif; font-size: 13px; line-height: 18.9px">Your are to submit the programs for this lab via the Assignments Page in </span><a target="_top" href="https://blackboard.uic.edu/" style="text-decoration: none; color: #58438b; background-color: #ffffff; border-color: #58438b; border-style: none none dotted; border-width: 1px; font-family: arial,verdana,sans-serif; font-size: 13px; line-height: 18.9px">Blackboard</a><span style="font-family: arial, verdana, sans-serif; font-size: 13px; line-height: 18.9px">.</span>

To help the TA, name your file with your net-id and the assignment name, like:
   * ptroy1LabX.c
---+++ <a name="Submit_this_file_via_the_Assignm"></a> Submit this file via the Assignment Link for the Lab in Blackboard.
   1 In the CS 211 Web Pages in <a target="_top" href="https://blackboard.uic.edu/webapps/login/" style="text-decoration: none; color: #58438b; border-color: #58438b; border-style: none none dotted; border-width: 1px">Blackboard</a>, go to the Assignments Page
   1 Click on the link for the correct lab. This will open a web page with the title: "Upload Assignment: Lab X", where X is the number of the lab
   1 Scroll down and click on the button "Browse for Local File"
   1 Select the file that you created that contains the program. Then click OK.
   1 Repeat steps 3 and 4 for your second program.
   1 Click the submit button on the "Upload Assignment: Lab X" page.
   1 You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.
-- Main.troy - 2012-11-07
Topic revision: r5 - 2012-11-14 - 18:02:10 - Main.troy
CS211
[edit this menu]
WISEST
Helping Women Faculty Advance
Funded by NSF