Practice problems on recursive functions.

(1) Write a recursive function  rectangle(int n) that prints a rectangle with
n rows and 10 columns. For example it could be applied as follows:

int main() {
   cout << rectangle(5) << endl;
   return 0;
}

This program should output:

********** 
********** 
********** 
********** 
********** 

How is this picture related to the simpler picture drawn by rectangle(4)?
What value of n makes the task of the function as easy as possible?

Solution:

string rectangle (int n) {
   if (n == 1) return "**********\n";
   return rectangle(n - 1) + rectangle(1);
}


(2) Write a function with title:

int triangle(int n)

that calculates the triangular number whose specification is:

triangle(n) = n + triangle(n - 1) if n is positive
and triangle(0) = 0.

Why are these numbers known as triangular numbers?

Solution:

int triangle(int n) {
   if (n <= 1) return 1;
   return triangle(n - 1) + n;
}

(3) Write a recursive function  secondDigit   that could be called
as follows:

int main() {
   cout << secondDigit(7295) << endl;
   return 0;
}

This program should output 2.

Solution:

int secondDigit(int n) {
   if (n < 10) return -1;  // there is no sensible answer 
   if (n < 100) return n % 10;
   return secondDigit(n / 10);
}

(4) Write a recursive function print binary, that prints
a positive integer n in binary.  For example, the following
program would output 10111:

int main() {
   cout << printBinary(23) << endl;
   return 0;
}

Solution:

string printBinary(int n) {
   if (n == 0) return "0";
   if (n == 1) return "1";
   return printBinary(n / 2) + printBinary(n % 2);
}

(5) Write a recursive function with title:

int toBinary(int n)

It could be used in the following main program which should
print 10111.

int main() {
   int x;
   x = toBinary(23);
   cout << x << endl;;
   return 0;
}

Solution:

int toBinary(int n) {
   if (n < 2) return n;
   return 10 * toBinary(n/2) + n % 2;
}

(6) Write a recursive function with title:

  string baseChange(int n, int base)

which converts the decimal number n to the given base.
For example,

   baseChange(5,156)

would return 1111, because 156 is 125 + 25 + 5 + 1 which is
written as 1111 in base 5. 

Solution:

string baseChange(int n, int base) {
   if (base > 36 || base < 2) {
      cout << "Bases greater than 36 are not covered by this program." << endl;
      exit(0);
   }
   string digitCode[36]={"0","1","2","3","4","5","6","7","8","9",
                         "A","B","C","D","E","F","G","H","I","J",
                         "K","L","M","N","O","P","Q","R","S","T",
                         "U","V","W","X","Y","Z"};
   if (n < base) return digitCode[n];
   return baseChange(n / base, base) + baseChange(n % base, base);
}