The definition of **recursion **in the dictionary is:

see recursionAlso 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:

typedef struct nodeStruct

{

int x;

int y;

struct nodeStructnext;*head)

} node;

void printReversed (node

{

if (head = null)

{

printReversed (head->next);

printf ("(%d, %d)\n", head->x, head->y);

}

}

- factorial
- fibonacci
- isPrime
- Greatest Common Divisor (Using Dijkstra's Algorithm)
- exponentiation

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:

- factorial
- fibonacci
- isPrime
- Greatest Common Divisor: "GCD"
- exponentiation

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.

When n >= 0Fibonacci of n, written as

- n! = 1 if n == 0
- n! = n * (n-1)! otherwise

When n >= 0IsPrime of n, written as

- fib(n) = 0 if n == 0
- fib(n) = 1 if n == 1
- fib(n) = fib(n-1) + fib(n-2) otherwise

- isPrime(n) = FALSE if n < 2
- isPrime(n) = TRUE if (factorInRange (2, n) == FALSE)
- isPrime(n) = FALSE otherwise

- factorInRange (m, n) = FALSE if m >= n
- factorInRange (m, n) = TRUE if n % m == 0
- factorInRange (m, n) = factorInRange(m+1, n) otherwise

When m > 0 and n > 0Exponentiation of m and n, written as

- gcd (m, n) = m if m == n
- gcd (m, n) = gcd ( m-n, n) if m > n
- gcd (m, n) = gcd (m, n-m) if m < n

When n >= 0For the even case of exp(m, n),

- 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

When in debug mode, your program is to have each recurvice function print out two messages. These messages will help show how the recursive functions work and how many recursive calls are actually made.

- 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.
- 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.

if ( debugMode == TRUE )

printf (" Debugging Information \n");

To help the TA, name your file with your net-id and the assignment name, like:

- ptroy1LabX.c

- In the CS 211 Web Pages in Blackboard, go to the Assignments Page
- 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
- Scroll down and click on the button "Browse for Local File"
- Select the file that you created that contains the program. Then click OK.
- Repeat steps 3 and 4 for your second program.
- Click the submit button on the "Upload Assignment: Lab X" page.
- You should see the Submission History page that shows what you submitted. Verify you actually submitted the correct information.

Topic revision: r3 - 2012-11-07 - 18:56:35 - Main.troy

Copyright 2016 The Board of Trustees of the University of Illinois.webmaster@cs.uic.edu |
WISEST Helping Women Faculty Advance Funded by NSF |