CMPT 102 Lab #8

November 20-23 2006

This lab is designed to give practice with strings and recursion

Practice Problem 1: Determine if a supplied string is a palindrome

A palindrome is a string of characters that is the same read forward or backward.   For example “do geese see god”.  Note that white space is not considered when determining if the string is a palindrome.  Write a function  isPalindrome to test a string and determine if it is a palindrome.  The definition of the function is:

int isPalindrome(char *inputstring);

The integer returned by isPalindrome is 0 if the string is a palindrome and 1 if the string is not a palindrome. The inputstring must not be changed within the function isPalindrome.

Write a simple main program to prompt the user to enter a string to be tested, to call isPalindrome to determine if the entered string is a palindrome, and to informing the user if the string they input is a palindrome (by printing a message to the screen.

Practice Problem 2: Calculating a Fibonacci series

Some mathematical problems, like calculating factorial, a power, or the elements of some special types of sequences are excellent problems to start with when you begin to try to design your own recursive algorithms. Your text shows you an example for the bisection function. In class notes we discussed printTriangle and quick sort. In this lab you will develop a recursive solution to another similar example. A basic problem is chosen to make it is easier for you to design and implement your recursive function. You have already written an interative solution to this problem, now you will write a recursive solution. You will be able to focus on the basics.  You will develop a recursive function to determine the nth Fibonacci number. You will write a simple main program to use the recursive function to generate and print the elements of a Fibonacci sequence of length M.  The value of M should be supplied by the user (read from the keyboard). The function Fib should have the following declaration

int fib( int M);

 

The Fibonacci numbers form a sequence with the following properties

§    The first number in the sequence is 0

§    The second number in the sequence is 1

§    Each remaining number in the sequence is the sum of the previous two numbers in the sequence

nth element of sequence = (n-2)nd element in the sequence + (n-1)st element in the sequence

§    The sequence is:    0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233 …

 

You will write a recursive function to calculate the nth Fibonacci number, the nth number in the sequence above

The prototype of this function will be int Fibonacci( int n );

The function will return the value of the nth Fibonacci number as its value. The argument of the function indicates which element in the sequence you are trying to determine.

 

This problem lends itself to recursion; lets think about the general case;

§    To determine the nth element of the sequence we add the (n-2)nd element and the (n-1)st element in the sequence

§    We do not yet know the values of the (n-2)nd element and the (n-1)st element

§    Inside our recursive function we will determine the values of these elements by calls to function Fibonacci

§    Somewhere in our function we will have a line of code something like       return (Fibonacci( n-1 ) + Fibonacci( n-2 ));

§    This line of code can be though of as equivalent to

Value1 = Fibonacci(n-1);

Value2 = Fibonacci(n-2);

 return (Value1 + Value2);

§    Now you can see the parallel to the quick sort example we discussed in class. The recursive function is called twice (inside the recursive function) just like our example in class (quick sort).

§    We need a stopping case. When do we no longer want to continue recursively calling the function? We have special definitions that control the first two elements of the sequence. We cannot determine the value of the second element by adding the first element to the element before it, because there is not an element before it.  We cannot determine the first element of the sequence by adding the two elements before it because there are no elements before it.

1.     We want Fibonacci to return 1 (without recursively calling itself) if we ask for the 2nd member of the sequence.

2.     We want Fibonacci to return 0  (without recursively calling itself) if we ask for the 1st member of the sequence