CSE143 - Spring 1999

Homework 3a Solution

#1

1. The problem can be defined in terms of a smaller problem of the same type.
For an array of size N, determine if the last element in the array matches.
Then recursively apply the function to the array, but looking only at the
first N-1 elements. When the function returns, combine the results.

2. Each recursive call diminishes the size of the problem by one, because each
recursive call is made with N one smaller than before.

3. An array of size zero has zero equal elements. This is the base case.

4. It will reach the base case because each recursive call is made with an N
one smaller than the previous.

#5

void PrintN(int N)
{
    // Only positive integers are allowed.
    assert(N > 0);

    // Recursively print the sequence 1, 2, ..., N-1
    if (N > 1)
    {
        PrintN(N - 1);
        cout << ", ";
    }

    // Then print N.
    cout << N;
}

#6

void PrintDigitsReverse(int N)
{
    // Only positive integers are allowed.
    assert(N > 0);

    // Print out the ones digit first.
    cout << N % 10;

    // If the number requires one than one digits, divide the number by 10,
    // effectively erasing the ones digit, then recurse.
    if (N >= 10)
        PrintDigitsReverse(N / 10);
}

#9

Enter: First = 1 Last = 30
Enter: First = 1 Last = 14
Enter: First = 1 Last = 6
Enter: First = 4 Last = 6
Leave: First = 4 Last = 6
Leave: First = 1 Last = 6
Leave: First = 1 Last = 14
Leave: First = 1 Last = 30
5

The Mystery() function returns the square root of N rounded down to the closest
integer. At each step, the Search() function considers the middle number in
the range [First, Last]. If that number is too large, it searches in
[First,Mid-1], otherwise the number is too small and it searches in
[Mid+1,Last].

#11

Function entered with N = 8
Function entered with N = 6
Function entered with N = 4
Function entered with N = 2
Function entered with N = 0
Function entered with N = 2
Function entered with N = 4
Function entered with N = 2
Function entered with N = 0
The value of F(8) is 27

Any N < 0 will cause the program to miss the base cases (N = 0, 1, or 2) and
recurse forever. F(3) calls F(-1), so F(3) recurses forever too. Since F(N)
calls F(N-2), any odd N > 1 will cause F to recurse forever.