The following is a recursive program. Assume that it only takes the positive integers as the input:

int compute(int x, int n) {

if(n==0) return 1;

else

if(n is even) return (compute(x, n/2) * compute(x, n/2));

else return (x * compute(x, n-1);

}

Can you tell what the above program really does?

1. It always returns 1.
2. It returns the value x.
3. It returns the value xⁿ.
4. It returns the value x².

Which one of the following statements gives us a correct inductive definition of a palindrome?

1. A palindrome is a string that reads the same left to right as right to left.
2. A palindrome is a string whose left half is a mirror image of its right half.
3. A single character is a palindrome and if a string s is a palindrome, then xsx is also a palindrome.
4. Both single character and an empty string are a palindrome. If a string s is a palindrome, then xsx is also a palindrome.

Which of the following pseudo code returns the length of a given list?

a) length(L) {

if(L has a single number x) return x;

else return (head(L) + length(tail(L)));

}

b) length(L) {

if(L has a single number x) return 1;

else return (1 + length(tail(L)));

}

c) length(L) {

if(L is an empty list) return 0;

else return (length(tail(L)) + 1);

}

d) length(L) {

if(L is an empty list) return 0;

else return (head(L) + length(tail(L)));

}