Object-Oriented Data Structures Using JavaChapter 4Page | 1
Basics (Sections 4.1 and 4.2)
Exercises 6-7 use the following method:
intpuzzle(intbase,intlimit)
{
if(baselimit)
return-1;
else
if(base==limit)
return1;
else
returnbase*puzzle(base+1,limit);
}
6.Identify
a.The base case(s) of the puzzlemethod
b.The general case(s) of the puzzlemethod
c.Constraints on the arguments passed to the puzzlemethod
7.Show what would be written by the following calls to the recursive methodpuzzle.
a.System.out.println(puzzle(14,10));
b.System.out.println(puzzle(4,7));
c.System.out.println(puzzle(0,0));
8.Given the following method:
intexer(intnum)
{
if(num==0)
return0;
else
returnnum+exer(num+1);
}
a.Is there a constraint on the value that can be passed as an argument for this method to pass the smaller-caller test?
b.Is exer(7)a valid call? If so, what is returned from the method? c. Is exer(0)a valid call? If so, what is returned from the method? d. Is exer(-5)a valid call? If so, what is returned from the method?
9.For each of the following recursive methods, identify the base case, the general case, and the constraints on the argument values, and explain what the method does.
a.intpower(intbase,intexponent)
{
if(exponent==0)
return1;
else
return(base*power(base,exponent-1));
}
b.intfactorial(intn)
{
if(n0)
return(n*factorial(n - 1));
else
if(n==0)
return1;
}
c.intrecur(intn)
{
if(n0)
return-1;
elseif(n10)
return1;
else
return(1+recur(n/10));
}
d.intrecur2(intn)
{
if(n0)
return-1;
elseif(n10)
returnn;
else
return((n%10)+recur2(n/10));
}
20.You must assign the grades for a programming class. Right now the class is studying recursion, and students have been given this simple assignment: Write a recursive method sumSquaresthat takes a reference to a linked list of Integerelements and returns the sum of the squares of the elements. The list nodes are of class LLNode<Integer>. The objects in the list are all of class Integer.
Example:
UN figure p. 291
Assume that the list is not empty.
You have received quite a variety of solutions. Grade the methods below, marking errors where you see them.
a.intsumSquares(LLNode<Integer>list)
{
return0;
if(list!=null)
return(list.getInfo()
*list.getInfo()
+sumSquares(list.getLink()));
}
b.intsumSquares(LLNode<Integer>list)
{
intsum=0;
while(list!=null)
{
sum=list.getInfo()+sum;
list=list.getLink();
}
returnsum;
}
c.intsumSquares(LLNode<Integer>list)
{
if(list==null)
return0;
else
returnlist.getInfo()*list.getInfo()
+sumSquares(list.getLink());
}
d.intsumSquares(LLNode<Integer>list)
{
if(list.getLink()==null)
returnlist.getInfo()*
list.getInfo();
else
returnlist.getInfo()*list.getInfo()
+sumSquares(list.getLink());
}
e.intsumSquares(LLNode<Integer>list)
{
if(list==null)
return0;
else
return(sumSquares(list.getLink())*
sumSquares(list.getLink()));
}
27. True or False? Explain your answers. Recursive methods:
a.Often have fewer local variables than the equivalent nonrecursive methods
b.Generally use while or for statements as their main control structure
c.Are possible only in languages with static storage allocation
d.Should be used whenever execution speed is critical
e.Are always shorter and clearer than the equivalent nonrecursive methods
f.Must always contain a path that does not contain a recursive call
g.Are always less efficient in terms of Big-O complexity, than the equivalent nonrecursive methods