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:

intpower(intbase,intexponent){// raise base to the power exponentif(n==0)return1;elsereturnbase*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:

intsum(intnumberOfIntegers) {// Compute 1+2+3+...+nif(n==1)// This is called the "base case"return1;elsereturnn + 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.

voidpattern(intn) {// assume that n is non-negativeif(n==0)return; pattern (n-1); printRowStars(n);return; }voidprintRowStars(intm) {for(inti=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.

voidprintPattern(intstart,intmiddle) {if(start == middle) { printRowStars(start);return; } printRowStars(start); printPattern(start + 1, middle); printRowStars(start); }voidprintRowStars(intm) {for(inti=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 palindromeif(???)// base casereturntrue;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.

The laboratory report should include the following elements:

- Brief statement of the objectives of the lab and a description of what you did during the lab session (A paragraph or two).
- 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.”
- Discussion of any difficulties you encountered and what you did to resolve them (A paragraph or two).
- Discussion of what you learned or how the lab experience reinforced things you already knew (A paragraph or two).
- Your overall rating of the lab on a scale of 1-4 and an explanation of your rating. Ratings are as follows:

-- JimSkon - 2010-05-06

Topic revision: r5 - 2011-05-13 - JimSkon

Copyright &© by the contributing authors. All material on this collaboration platform is the property of the contributing authors.

Ideas, requests, problems regarding TWiki? Send feedback

Ideas, requests, problems regarding TWiki? Send feedback