TITLE

RECURSIVE FUNCTIONS - THREE SMALL PROGRAMS

INTRODUCTION

Recursion is a programming technique in which a function calls itself. It is another way of implementing repetitive computations, which we have previously associated with loops. When called to solve a problem, a recursive function passes a smaller version (or versions) of the problem to another instance (or instances) of itself, then uses the results returned by the recursive call or calls to build or complete a solution to the original problem.

DESCRIPTION

Design, implement, and document recursive functions to solve the three problems described below; test those functions by calling them from appropriate main functions; and document the resulting programs and their functions. Note that you will write three small programs.

Keep in mind the questions that arise in designing recursive algorithms:

• What is/are smaller but identical problem(s)?

• How will the smaller solution(s) be used to solve the larger problem?

• What is/are the base case(s)?

EXPONENTIATION

Write and exercise a recursive function exp(x,n) that returns the value of the double x raised to the non-negative integer power n. A run of a program that exercises this function might look like this: Enter a real value: 2.4 Enter an integer: 3 2.4^3 = 13.824 Remember that any non-zero value raised to the power 0 is 1.

DETERMINE IF A VALUE IS PRESENT IN AN ARRAY

Implement and test a recursive function present(a,n,k) that returns TRUE if the value k is present in the array a[0..n-1], FALSE if it is not. Read values from a file into the array. Read values to test from the terminal. Terminate the program with an input of 0.

If the values read into the array are [14, 66, 34, 51, 44, 16, 29, 33], then a run of the program might look like this:

Data file name -> vals.dat Test value -> 51 Present Test value -> 63 Not present Test value -> 29 Present Test value -> 0

IDENTIFY PALINDROMES

As we saw in Project 1, a palindrome is a string in which the letters read the same in both directions, disregarding non-letters and capitalization. For example, "Eva, can I see bees in a cave?" is this kind of palindrome.

This time, solve the problem of the previous project with a recursive function, say pal(a,low,high). This function will return a boolean value. Note that you can re-use the rest of your program from the first project.

HINT: Count the letters as they are read in.

HINT: Use an array of characters rather than the string type.