Introduction to Recursion Lab

Recursion*

Recursion is an extremely powerful programming technique in which a method calls itself (either directly or indirectly). It is elegant and can lead to easy solutions of a problem that may be otherwise extremely difficult to solve. In this lab we will explore only simple recursive problems; later, having introduced arrays, we will return to this topic and explore a variety of interesting recursive sorting and searching methods. If time permits, we will also explore the use of recursion in graphical methods (such as fractals). The primary drawback of recursion is that the recursive algorithm may be less efficient than a corresponding iterative (or non-recursive) solution.

I Suppose that we wish to compute 3 to the power 5, and we know that 3 to the power 4 is 81. Then the answer we seek is simply 3 times 81. In general, if we wish to compute base to the power exponent (where base and exponent are positive integers), then we have only to multiply base by the result of raising base to the power exponent -1. Of course, if exponent =1, then our answer is simply base.

Examine and test the following recursive static method:

int power(int base, int exponent){ 
// raise base to the power exponent 
 if (n==0) 
     return 1; 
 else 
     return base*power(base, exponent-1); 
}

II Next, let us find a recursive solution to the problem of summing the first n integers. If sum(n) represents the value 1+2+3+...+n, then (for n>=2) sum(n) = n + sum(n-1). This suggests the following recursive method:

int sum (int numberOfIntegers) { 
 // Compute 1+2+3+...+n 
 if (n==1) // This is called the "base case" 
 return 1; 
 else 
 return n + sum(n-1); 
}

Next, write and test recursive methods to compute each of the following:

(A) the sum of the cubes of the first n integers.
(B) n! (i.e., factorial(n) = 1*2*3*...*n)
(C) the sum of the first n odd integers (i.e., oddSum(n) = 1 + 3 + 5 + 7 + ... + (2*n-1) )

III (A) Study the following recursive method, pattern , without first running it. Try to predict the output for various input values.

void pattern (int n) { 
// assume that n is non-negative 
 if (n==0) 
 return; 
 pattern (n-1); 
 printRowStars(n); 
 return; 
} 
void printRowStars(int m) { 
 for (int i=0; i<m; i++) 
 cout<< "*" << endl;
}

Now, create a client which tests this method, and check to see if your predictions are confirmed.

(B) Next, consider the following recursive method which has two parameters. Try to predict what it does by choosing small integers for each parameter value. Again, compare your prediction to reality by testing.

void printPattern(int start, int middle) { 
if (start == middle) { 
 printRowStars(start); 
 return; 
 } 
 printRowStars(start); 
 printPattern(start + 1, middle); 
 printRowStars(start); 
} 
void printRowStars(int m) { 
 for (int i=0; i<m; i++) 
 cout << "*" << endl; 

}

IV Recall that the number of combinations of N items taken R at a time, denoted by C(N,R), satisfies the following recursive formula:

C(N, R) = C(N-1, R-1) + C(N-1, R)

Note also that C(N,0)=1 and that C(N,R) = 0 if N<R.
Using this information, write and test a recursive method to compute C(N,R). (In testing, you may wish to know that C(5,2) = 10; C(8,6) = 28; C(13,1) = 13.)

V Next, let us write a recursive method to recognize if a String object is a palindrome (recall that a string, such as "radar" or "able was I ere I saw elba", is a palindrome if it reads the same forward and backward.) Complete the following skeleton:

palindromeTest(String line) { 
// return boolean true if line is a palindrome 
 if (???) // base case 
 return true; 
 else 
 // consider line.substring(1, line.length()-1) 
 return ??? 
{

VI Design, write, and test recursive static methods that perform each of the following tasks:

(A) returns the number of digits of an integer n.
For example numberDigits(1134) returns 4; numberDigits(4) returns 1. Note that, if n>0, numberDigits(n) returns 1 + numberDigits(n/10).

(B) returns the number of zeroes in the integer n.
For example, numberZeroes(8) returns 0, numberZeroes(103004) = 3. Note that if n>0 and n%10 equals 0, then numberZeroes(n) returns 1 + numberZeroes(n/10). If n>0 and n%10 = 0, then numberZeroes(n) returns numberZeroes(n/10).

(C) If time permits, create a recursive method to change a number from base 2 into base 10. For example, changeBase(101) returns 5; changeBase(10000) returns 16. Hint: if n>0, changeBase(n) returns 2*changeBase(n/10) + n%10.

What to turn in on _BlackBoard_

The laboratory report should include the following elements:

  1. Brief statement of the objectives of the lab and a description of what you did during the lab session (A paragraph or two).
  2. Lab results such as program listings, input and/or output files, tables of data produced, answers to specific questions posed, etc. as appropriate to the lab assignment. If there were no results, indicate this with “No Results.”
  3. Discussion of any difficulties you encountered and what you did to resolve them (A paragraph or two).
  4. Discussion of what you learned or how the lab experience reinforced things you already knew (A paragraph or two).
  5. Your overall rating of the lab on a scale of 1-4 and an explanation of your rating. Ratings are as follows:
* Based on http://webpages.cs.luc.edu/~ajs/courses/170sp2000/labs/lab9.html

-- JimSkon - 2010-05-06

Topic revision: r5 - 2011-05-13 - JimSkon
 
This site is powered by the TWiki collaboration platformCopyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.
Ideas, requests, problems regarding TWiki? Send feedback