Computer Science at IUS
Fall
2000 - C 202
Study Guide #1
Solution to Lab #1
Student Name:
1 - Typically,
solutions to the problems use either _______________________ or _______________________
2
- Recursion involves solving a problem T by performing another task T' where:
a) T' is the hardest part of T.
b) T' has exactly the same nature as T.
c) T' is larger than T.
d) T' is smaller than T.
3
- What is the purpose of the degenerate, or the base case in a recursive
solution?
4
- What four questions must be considered in designing a recursive solution?
5
- In the following recursive code, which line represents the degenerate case?
int f(int n)
{
a) if ( 0 == n ) return 1;
b) else return 2 * f(n-1);
}//end f
6
- What value is returned by the call f(3), where f is the recursive function
given by the following code?
int f(int n)
{
if ( 0 == n )
return 1;
else return 2 * f(n-1);
}//end f
7
- consider the following recursive code?
void doIt(int n)
{
if (n > 0)
{
cout << n;
doIt(n+1);
}//end if
}//end recWrite
What,
if anything, is wrong with this function?
8
- Consider the recursive function defined by the following:
int f(int n)
{
if ( 0 == n)
return 2;
else
return 3 + f(n-2);
}// end f
What
is the value of f(6) ?
9
- In the function defined in question 8, Is there anything that will make the
code not run properly? True or False? Explain.
10
- Why the recursion is sometimes preferred to iteration? Explain.
Which
of the following functions is a recursive function that returns the product n*m
when n and m are initially integers greater than zero? Each of these functions
compiles and runs. However, except for one, each is either not a recursive
solution, or there is another reason why it is not a solution to the problem.
Explain why each is or is not a solution to this problem.
(problems 11 through 14)
11 -
int
multi1 ( int n, int m)
{
int temp = 0;
while(n>0)
{
temp = temp + m;
n = n - 1;
}
return temp;
}//end
multi1
12 -
int
multi2 ( int n, int m)
{
if ( n > 0)
return m;
else
return n + multi2(n-1, m);
}//end
multi2
13 -
int
multi3 ( int n, int m)
{
if ( 1 == n)
return m;
else
return m + multi3(n-1, m);
}//end
multi3
14 -
int
multi4 (int n, int m)
{
if ( n <= 1)
return m;
else
return n + multi4(m, n-1);
}//end
multi4
15 - Given a batch of data,
write all the steps to perform Quicksort, Selection sort and Binary search.
16 - Given a recursive
algorithm, show the recursive stack with corresponding activation records.