Programming Lab 5 : Recursion

CSCI-UA 9102, Data Structures

  • Exercise 1.1. Write a recursive method to compute the series m(i) = 1/2 + 2/3 + 3/4 + … + i/(i+1). Then write a test program that displays m(i) for i=1,2,…,10
  • Exercise 1.2. Write a recursive method to compute the series m(i) = 1 + 1/2 + 1/3 + … + 1/i and write a test program that displays m(i) for i=1,2,…, 10
  • Exercise 1.3. The gcd(m,n) can also be defined recursively as follows: If m%n is 0, gcd(m,n) is n. Otherwise, gcd(m,n) is gcd(n, m%n). Write a recursive method to find the gcd. Write a test program that prompts the user to enter two integers and displays their GCD.
  • Exercise 1.4. Describe a recursive algorithm to compute the integer part of the base 2 logarithm of a integer n by using only addition and integer division
  • Exercise 1.5. Use recursion to write a Java method for determining if a string s has more vowels than consonants
  • Exercise 1.6. Provide a recursive algorithm that will check if an array A of integers contains an integer A[i] that is the sum of two integers that appear earlier in A, that is such that A[i] = A[j] + A[k], for j,k
  • Exercise 1.7. Suppose that you are given an array A containing n distinct integers that are listed in increasing order. Given a number k, describe a recursive algorithm to find two integers in A that sum to k, if such a pair exists.
  • Exercise 1.8. Write a short recursive method that determines if a string s is a palindrome, that is if it is equal to its reverse. Examples of palindromes include ‘racecar’ and ‘gohangasalamiimalasagnahog’
  • Exercise 1.9. (Print the digits in an integer reversely) Write a recursive method that displays an int value reversely on the console using the header below.

public static void reverseDisplay(int value)

  • Exercise 1.10.
    Design and implement a recursive program to print the nth line of Pascal’s triangle. Each interior value is the sum of the two values above it. Hint: use an array to store the values on each line.