Tutorial Exercises: Set 5

---

Click on the links above

Exercise 1

Write a recursive function for the computation of the gcd of two positive integers using Euclid's algorithm.

Solution 1

   unsigned int gcd ( unsigned int a , unsigned int b )
   {
      if (a == 0) return b;
      if (b == 0) return a;
      return gcd(b,a%b);
   }

Exercise 2

A Lucas sequence is a generalization of the Fibonacci sequence and is recursively defined as follows.

   U₀ = 0,
   U₁ = 1,
   U_n = aU_n-1 - bU_n-2 for n >= 2.

Write a recursive function for the computation of U_n (given n, a and b as parameters).

Solution 2

   int Lucas ( unsigned int n , int a , int b )
   {
      if (n == 0) return 0;
      if (n == 1) return 1;
      return a * Lucas(n-1,a,b) - b * Lucas(n-2,a,b);
   }

Exercise 3

Write an iterative function for the computation of U_n of Exercise 2. Compare the running times of the recursive and the iterative functions.

Solution 3

   int LucasIterative ( unsigned int n , int a , int b )
   {
      int i, U_1, U_2, U;

      if (n == 0) return 0;
      if (n == 1) return 1;
      U_2 = 0; U_1 = 1;
      for (i = 2; i <= n; ++i) {
         U = a * U_1 - b * U_2;
         U_2 = U_1;
         U_1 = U;
      }
      return U;
   }

Here is a complete program for comparing the running times of the recursive and the iterative functions.

Exercise 4

Catalan numbers C_n are defined recursively as follows:

   C₀ = 1
   C_n = C₀C_n-1 + C₁C_n-2 + C₂C_n-3 + ... + C_n-1C₀ for n >= 1.

Write a recursive function that, upon input n, returns C_n. Also write a main() function that invokes the recursive function on an argument supplied by the user.

Solution 4

   unsigned long int Catalan ( unsigned long int n )
   {
      unsigned long int s, i;

      if (n == 0) return 1;
      for (s = i = 0; i < n; ++i) s += Catalan(i) * Catalan(n-i-1);
      return s;
   }

   int main ()
   {
      unsigned long int n;

      printf("Enter n: "); scanf("%lu", &n);
      printf("C(%lu) = %lu\n", n, Catalan(n));

      exit(0);
   }

Exercise 5

You are sitting at the origin (0,0) of a two-dimensional plane. Your task is to reach the point (m,n) in the plane, where m and n are positive integers. At each step, you are allowed to move by one unit of length either to the right or to the top. Write a recursive function to enumerate the number of ways you can reach (m,n). Also write a main() function which reads m and n from the user and invokes the recursive function.

(Remark: If m = n and you are not allowed to move above the line x = y, then the number of ways is equal to the Catalan number C_n.)

Solution 5

Let us first look at a recursive formulation of the problem. Suppose that you are sitting at the coordinates (i,j), and there are R(i,j,m,n) ways to reach (m,n) from (i,j). Initially, i = j = 0, that is, the desired answer is R(0,0,m,n).

At position (i,j), there are two possibilities: reaching (i+1,j) or (i,j+1). Therefore, the total count of possibilities at (i,j) is

   R(i,j,m,n) = R(i+1,j,m,n) + R(i,j+1,m,n).

This is the recursive formula to be used for solving the problem.

We must also specify a set of boundary conditions for the recursion to stop. Here are these.

   R(m,n,m,n) = 1. (You have reached (m,n), that is, you have discovered a way to reach the destination.)

   R(i,j,m,n) = 0 if i > m or j > n. (From this position, you cannot reach (m,n) by rightward and upward movements only.)

The following code snippet implements these ideas.

   int R ( int i , int j , int m , int n )
   {
      if ((i == m) && (j == n)) return 1;
      if ((i > m) || (j > n)) return 0;
      return R(i+1,j,m,n) + R(i,j+1,m,n);
   }

   int main ()
   {
      int m, n;

      printf("Enter m: "); scanf("%d", &m);
      printf("Enter n: "); scanf("%d", &n);
      printf("Number of ways = %d\n", R(0,0,m,n));

      exit(0);
   }

Remark: The desired output is the binomial coefficient C(m+n,m). For the sake of illustration, we have used a recursive formulation.

Brain-teaser

What is the return value of the following function in terms of its two arguments m and n? Justify your answer.

   unsigned int f ( unsigned int m , unsigned int n )
   {
      unsigned int sum;

      if (m > n) return f(n,m);
      sum = 1;
      while (++m <= n) sum += f(m,n);
      return sum;
   }

---

Back  |  Home