Sample Solutions to Recursion Practice Questions

Implement the following using recursion (and no loops). For some questions, you may want to create a helper function with extra parameters.

1. The product of the integers from 1 to \(n\), i.e. the factorial function \(n! = 1 \cdot 2 \cdot \ldots \cdot n\), for \(n \geq 0\). Note that \(0! = 1\).

   Sample solution:

   int factorial_rec(int n) {
       if (n == 0) {
           return 1;
       } else {
           return n * factorial_rec(n - 1);
       }
   }
   
   void factorial_rec_test() {
       printf("Testing factorial_rec ... ");
       assert(factorial_rec(0) == 1);
       assert(factorial_rec(1) == 1);
       assert(factorial_rec(2) == 2);
       assert(factorial_rec(3) == 6);
       assert(factorial_rec(4) == 24);
       printf("all tests passed\n");
   }
   

2. The sum of the first n squares, i.e. \(1^2 + 2^2 + \ldots + n^2\), for \(n \geq 0\).

   Sample solution:

   int square_rec(int n) {
       if (n == 0) {
           return 0;
       } else {
           return n * n + square_rec(n - 1);
       }
   }
   
   void square_rec_test() {
       printf("Testing square_rec ... ");
       assert(square_rec(0) == 0);
       assert(square_rec(1) == 1);
       assert(square_rec(2) == 5);
       assert(square_rec(3) == 14);
       assert(square_rec(4) == 30);
       printf("all tests passed\n");
   }
   

3. Print the numbers from n down to 1, one number per line. Assume \(n \geq 1\).

   Sample solution:

   void print_down_from(int n) {
       if (n == 1) {
           printf("1\n");
       } else {
       printf("%d\n", n);
           print_down_from(n-1);
       }
   }
   
   void print_down_from_test() {
       printf("Testing print_down_from ...\n");
       print_down_from(5);
       printf("all tests passed\n");
   }
   

4. Print the numbers from 1 up to n, one number per line. Assume \(n \geq 1\). Hint: Write a recursive function that takes two inputs, n, and also another int representing the current value to be printed.

   Sample solution:

   void print_up_to(int start, int n) {
       if (start == n) {
           printf("%d\n", start);
       } else {
           cout << start << "\n";
           printf("%d\n", start)
           print_up_to(start + 1, n);
       }
   }
   
   void print_up_to_test() {
       printf("Testing print_up_to ...\n");
       print_up_to(1, 5);
       printf("all tests passed\n");
   }