Recursion

---

Q) Describe this recursion

Consider the following recursive function:

int foo(int n)
{
    if (n == 0) {
        return 1;
    }
    return 2 * foo(n - 1);
}

Which of the following is the best description for this function?

a) Computes 2^n ("2 to the n")
b) Compute n!
c) Compute sum of values from 1 to n
d) Computes 2 * n

Q) Describe this recursion

Consider the following recursive function:

void bar(int n) 
{
    if (n == 0) {
        return;
    }

    bar(n / 2);
    cout << n % 2;
}

Which of the following is the best description for this function?

a) Print n % 2 to the screen.
b) Print n / 2 to the screen.
c) Print n to the screen.
d) Print n to the screen in binary.

Q) Complete this recursion

Consider the following partial implementation of a function which will return true when there is a negative number in the array; false otherwise.

bool hasNegative(const int data[], int size) 
{
    if (size == 0) {
        return false;
    }
    // XXXXXXXXXX
}

Which of the following correctly completes this function?

a) return (data[size - 1] < 0) && hasNegative(data, size - 1);
b) return (data[size - 1] < 0) || hasNegative(data, size - 1);
c) return data[size - 1] + hasNegative(data, size - 1);
d) return hasNegative(data, size - 1);

---

Answers

1 = a) computes 2^n because each time through it multiples the previous value by 2.
2 = d) Print n to the screen in binary.
b) return (data[size - 1] < 0) || hasNegative(data, size - 1);
because it analyzes the last element checking if it's negative. OR it with checking the rest of the array (moving forward)