Examples of tasks solving on recursion in the Java programming language

---

Contents

• 1. Calculating the area of a triangle
• 2. Calculate the value of the square of the number based on the dependence
• 3. Combinatorial problem
• 4. The parser for the concept of “identifier”
• 5. Ackermann function value
• 6. The parser for the notion of “simple expression”
• 7. Parser for the concept of “sum”
• 8. Conversion from one number system to another
• 9. Recursive function Min(). Finding the minimum value in an array of type double[]
• 10. Recursive function ConvertAnyR(). Converting a number from one number system to another
• 11. Recursive function isPrime(). Determine if a number is prime
• Related topics

---

Search other websites:

1. Calculating the area of a triangle

Task. A triangle of size m×n is given, where m, n are integers and m>0, n>0. Develop a recursive function that calculates the area of a triangle based on the dependency:

Decision. If the dependency is known, then the implementation of the function presents no particular problems. The recursive process will be stopped when the condition n = m = 1 is fulfilled.
The program code of the S() function is as follows:

static int S(int n, int m) {
  if ((n==1)&&(m==1)) return 1;
    else
    if (n>1)
      return S(n-1,m)+m;
    else
      return S(n,m-1)+1;
}

⇑

2. Calculate the value of the square of the number based on the dependence

Task. Calculate the value of the square of a positive integer n, if the dependence is known

n² = (n-1)² + 2·(n-1) + 1

From this dependence we get the recursion formula:

Decision.

// calculating the square of a number
static int f(int n) {
    if (n==1)
        return 1;
    else
        return f(n-1)+2*n-1;
}

⇑

3. Combinatorial problem

Task. Calculate the number of combinations of n different elements for m. The number of combinations is determined by the dependence

Decision.

// number of combinations of n by m
static int C(int n, int m) {
    if ((m==0)&&(n>0) || (m==n)&&(n>0))
        return 1;
    else
        if ((m>n)&&(n>=0))
            return 0;
        else
            return C(n-1,m-1) + C(n-1,m);
}

⇑

4. The parser for the concept of “identifier”

Task. Develop a recursive function that implements the parser for the concept ‘identifier’. As is known, in the Java programming language, the identifier obeys the following rules:

• the first character of the identifier is necessarily the letter of the Latin alphabet;
• second, third, etc. the symbol identifier can be a letter or a number.

The general identifier formula is as follows:

here

• identifier – an identifier;
• letter – some letter of the Latin alphabet (from ‘a’ to ‘z’ or from ‘A’ to ‘Z’);
• digit – digit from ‘0’ to ‘9’.

Decision. In this case, a recursive function is implemented with the name IsIdentifier().Since the function analyzes the concept of “identifier”, the result of returning from a function is a value of type boolean. If the function returns true, then the identifier name is correct in accordance with the condition of the task. If the function returns false, then there is an error in the identifier name.

The input parameter of the recursive function IsIdentifier() is a string of type String. This line contains the identifier name. The condition for the end of the recursive process is the achievement of the first character of the identifier.

The text of the IsIdentifier () method is as follows

// determining whether string is a identifier
static boolean IsIdentifier(String s, int pos) {
    char c;
    if (pos==0) {
        c = s.charAt(pos); // get a symbol in position pos
        if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
            return IsIdentifier(s,pos+1);
        else
            return false;
    }
    else
        if (pos<s.length()) {
            c = s.charAt(pos); // get a symbol
            if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z') || (c>='0')&&(c<='9'))
                return IsIdentifier(s, pos+1);
            else
                return false;
        }
        else
            return true;
}

Using the IsIdentifier() function in other program code

boolean b;
String s = "Alkjlkjlkj445l25k3j1";
b = IsIdentifier(s,0); // b = true

⇑

5. Ackermann function value

Task. Calculate the value of the Ackermann function for two non-negative integers n and m, where

Decision. If dependencies are known, the implementation of the function is not a difficult task. In accordance with the condition of the task, the function gets two parameters. These are non-negative integers n and m. The function also returns a non-negative integer.
For large values of n and m, a stack overflow may occur, since the Ackermann function is twice recursive: one of the arguments to the function is the same recursive function.

The implementation of the function is as follows:

static int A(int n, int m) {
    if (n==0)
        return m+1;
    else
        if ((n!=0)&&(m==0))
            return A(n-1,1);
        else
            return A(n-1,A(n,m-1));
}

Using the function for small values of n and m:

int res;
res = A(1,2); // res = 4
res = A(0,1); // res = 2
res = A(0,0); // res = 1
res = A(2,2); // res = 7
res = A(3,2); // res = 29
res = A(3,3); // res = 61

⇑

6. The parser for the notion of “simple expression”

Task. Create a program that implements the parser for the concept of “expression”

here

• Expression – a simple expression;
• simple_identifier – a simple identifier;
• letter – Latin letter from ‘a’ to ‘z’ or from ‘A’ to ‘Z’;
• operation – operation sign ‘+’, ‘–’ or ‘*’.

Decision. To solve this problem, you need to implement three functions:

• the IsIdentifier() function, which determines whether a simple identifier is a letter;
• the function IsOperation(), which determines whether there is an operation syntactically correct in accordance with the task;
• the recursive function IsExpression(), which determines whether a simple expression is syntactically correct in accordance with the task.

The recursive function IsExpression() receives 3 parameters:

• string s, which is analyzed;
• the position pos of the current symbol in the string s;
• an IsOp flag that indicates whether the previous symbol was an operation sign.

The implementations of the functions IsIdentifier(), IsOperation() and IsExpression() are as follows:

// an identifier
static boolean IsIdentifier(char c) {
  // check if the identifier is a letter
  if ((c>='a')&&(c<='z') || (c>='A')&&(c<='Z'))
    return true;
  else
    return false;
}

// operation sign
static boolean IsOperation(char c) {
  if ((c=='-') || (c=='+') || (c=='*'))
    return true;
  else
    return false;
}

// Expression Analyzer Recursive Function
static boolean IsExpression(String s, int pos, boolean IsOp) {
  char c;
  c = s.charAt(pos);

  // if the first character
  if (pos==0) {
    if (IsIdentifier(c)) // check if a first symbol is a letter
      return IsExpression(s,pos+1,false);
    else
      return false;
  }
  else
    if (pos<s.length()-1) {
      // not the first nor the last symbol
      if (IsIdentifier(c)) // if the identifier, then move on to the next symbol
        return IsExpression(s,pos+1,false);
      else {
        // after the operation should be a simple expression
        if (IsOperation(c) && (!IsOp))
          return IsExpression(s,pos+1,true); // indicate at the next level that there was an operation
        else
          return false;
      }
    }
    else {
      // otherwise, process the last symbol in the string
      if (IsOperation(c)) // if the last symbol is an operation, then the expression is wrong
        return false;
      else
        return IsIdentifier(c); // check if there is last character an identifier
    }
}

Demonstration of using IsExpression() in another method:

boolean res;
res = IsExpression("a+b",0,false); // res = true
res = IsExpression("+a+b",0,false); // res = false
res = IsExpression("ABCsdl-Sdl+Dfjls",0,false); // res = true
res = IsExpression("a+-b-c",0,false); // res = false
res = IsExpression("a+b;",0,false); // res = false
res = IsExpression("alsd+bsldk-",0,false); // res = false
res = IsExpression("AbcDEf",0,false); // res = true

Using a similar pattern, you can create several recursive functions that will analyze complex expressions or their fragments. It is important for each function to determine the correct dependencies (algorithm).

⇑

7. Parser for the concept of “sum”

Task. Create a program that implements the parser for the concept of “sum”

here

• Sum – a function that analyzes the total amount;
• Integer – a function that analyzes an integer;
• Digit – a function that analyzes a digit;
• Operation – a function that implements the sign of the operation. The sign of the operation can be ‘+’ or ‘–’.

The expression in braces { } can be repeated except for the operation.

Decision. Using this example as a sample, you can develop your own analyzers of complex expressions. The representation of each complex expression can be broken apart. For each part, its own recursive function can be developed.

To solve this problem, 4 functions have been developed:

• the IsSignOp() function, which determines whether is a character c with an operation sign. The character c is passed to the function as an input parameter. The function returns true or false;
• the function IsDigit(), which determines whether is an input symbol c with an integer. The symbol c is a function parameter;
• the recursive function IsInteger(), which analyzes the entire expression. Function receives 3 parameters. The first parameter is the analyzed string. The second parameter pos is the position of the current symbol in the analyzed string s. The third, auxiliary parameter IsOp indicates whether the previous character was an operation sign. The third parameter IsOp is necessary to avoid repeating two characters of operations, for example, “++”;
• the IsSum() function, which calls the recursive IsInteger() function. The IsSum() function performs a simple redirection to the execution of the IsInteger() function.

The implementation of the functions is as follows:

// operation sign
static boolean IsSignOp(char c) {
  if ((c=='+') || (c=='-'))
    return true;
  else
    return false;
}

// an integer (digit)
static boolean IsDigit(char c) {
  if ((c>='0') && (c<='9'))
    return true;
  else
    return false;
}

// the recursive function IsInteger (), implements the check of the whole expression,
// pos - current character position from string s, which is analyzed
// IsOp=true, if the previous character at the top level was a sign of the operation
static boolean IsInteger(String s, int pos, boolean IsOp) {
  char c;
  if (pos==0) {
    // first character of expression
    // the first must be an integer (digit)
    c = s.charAt(pos);
    if (IsDigit(c)) // if c symbol is a digit
      return IsInteger(s,pos+1,false); // then go to check the next character
    else
      return false;
  }
  else
  if (pos<s.length()-1) {
    c = s.charAt(pos);
    if (IsDigit(c)) // if number (digit)
      return IsInteger(s,pos+1,false); // then process the next character
    else {
      // if not a number
      if (IsSignOp(c)) {
        // if the sign of the operation,
        if (!IsOp) // if the previous character is not an operation character,
          return IsInteger(s,pos+1,true); // then process the next symbol
        else
          return false; // otherwise, an error in the expression: 2 characters of the operation follow in a row
      }
      else
        return false; // error, invalid character expression
    }
  }
  else {
    // end of expression
    c=s.charAt(pos);
    return IsDigit(c); // the last character of the expression must be a number (digit)
  }
}

// the IsSum() function that calls the recursive IsInteger() function
static boolean IsSum(String s) {
  // invoke the recursive function IsInteger()
  return IsInteger(s, 0, false);
}

Using the IsSum() function in another method

boolean b;
b = IsSum("253+23"); // b = true
b = IsSum("2345w-18"); // b = false
b = IsSum("750-450+200"); // b = true
b = IsSum("-200"); // b = false
b = IsSum("2019"); // b = true
b = IsSum("210+-5"); // b = false
b = IsSum("300-"); // b = false
b = IsSum("4564+2+"); // b = false

---

⇑

8. Conversion from one number system to another

Task. Develop a recursive conversion function from decimal to binary.

Decision. The conversion algorithm is classic. It is necessary to divide the input parameter num by 2 as long as num>2. For each division, you need to select the remainder using the expression num%2. The % operation is intended to highlight the remainder of the division of two numbers.

The function Convert10to2() receives two arguments:

• an argument of an unsigned integer type with a parameter named num. This is the given number in decimal notation.
• temporary argument that serves to memorize the current result in binary calculus.

The result of the function is an inverse (reversible) string to the string res. Because, when dividing, the resulting value is formed in the reverse order.
The function has the following implementation:

// conversion of a natural number from the 10th number system to the binary
static String Convert10to2(int num, String res) {
    if (num<2) {
        if (num==0)
            res = res + "0";
        else
            res = res + "1";

        // reversing of the res string and returning the result
        String res2 = "";
        for (int i=res.length()-1; i>=0; i--)
            res2 += res.charAt(i);
        return res2;
    }
    else {
        if (num%2==0)
            res = res + "0";
        else
            res = res + "1";
        return Convert10to2(num/2,res); // go to the next step
    }
}

Using a function in another method

String res;
res = Convert10to2(19,""); // res = 10011
res = Convert10to2(119,""); // res = 1110111
res = Convert10to2(250,""); // res = 11111010

⇑

9. Recursive function Min(). Finding the minimum value in an array of type double[]

Task. Develop a recursive Min() function to calculate the minimum value in array A, which contains n double numbers (n>0).

Solution. To ensure a cyclic process, the following parameters must be passed to the Min() function:

• A – array in which the search for the minimum value is carried out;
• item – index of the array element, which is compared with the current minimum value;
• min – current minimum value.

 

// A recursive function that computes the minimum in array A.
// Function parameters:
// - A - the array in question;
// - item - the number of the element that is compared with the minimum;
// - min - current minimum, result.
public static double Min(double[] A, int item, double min)
{
  // Calculate minimum
  if (min>A[item])
    min = A[item];      

  // Check whether the last element
  if (item == A.length-1) // if the last element, then return the minimum
    return min;
  else // if not the last element, then recursively call the Min function
    return Min(A, item+1, min);
}

Using the Min() function could be like this

...

// The array under test
double[] A = { 2.8, -1.3, 2.9, -1.5, -1.0, 2.2, 0, 3.7 };
double res;
res = Min(A, 1, A[0]);
System.out.println("Min = " + res);

...

⇑

10. Recursive function ConvertAnyR(). Converting a number from one number system to another

Task. Develop a recursive function ConvertAny() for converting a number from a calculus system with basis m to a calculus system with basis n. The function should receive the following parameters:

• the number num, which needs to be converted from the calculus system m to the calculus system n;
• unsigned integer number m specifying the denomination of the calculus system with the base m (2<m≤10);
• unsigned integer number n specifying the denomination of the calculus system with the base n (2<n≤10);

The function must return a string of type string, which is the result.

Solution. To convert a number from the m number system to the n number system, you need to do the following:

• first convert the number from the m number to the decimal number system;
• convert a number from decimal to base n.

For comparison purposes, the solution to the problem in two ways is given below:

• using the non-recursive ConvertAny() function;
• using the recursive function ConvertAnyR(). This function uses the additional recursive function ConvertTo10R() to convert a number to decimal.

The text of the non-recursive function is as follows

// Recursive function that converts a number from one number system to another
// m = 2..10, n = 2..10
public static String ConvertAny(long num, int m, int n)
{
  String res = ""; // result
  long t;
  int i;
  long num10;

  // 1. Checking the correctness of input parameters
  if ((m<2)||(m>10)||(n<2)||(n>10))
    return "Incorrect data";

  // 2. First you need to convert the number num(m)=>num(10) - to the decimal system
  num10 = 0; // the number in the decimal system
  i = 0;

  while (num>0) {
    t = (num % 10) * (long)Math.pow(m, i);
    num10 += t;
    num = num / 10;
    i = i+1;
  }

  // 2. Convert number num10 in number in the system for calculating n
  while (num10>0) {
    t = num10%n;
    res = String.valueOf(t) + res;
    num10 = num10/n;
  }

  return res;
}

Using a non-recursive function could be like this

...

// Convert the number 22 of the numbering system with a base 3
// to number system with the base 5
String number = ConvertAny(22, 3, 5);
System.out.println("number = " + number);

...

The text of the recursive functions ConvertTo10R() and ConvertAnyR() is as follows

// Recursive function, which converts the number to the number system 10
public static long ConvertTo10R(long num, int m, int i) {
  long t;

  if (num>0) {
    t = (num%10) * (long)Math.pow(m, i);
    return t + ConvertTo10R(num/10, m, i+1);
  }
  else {
    return 0;
  }
}

// Recursive function that translates a number from one system to another
public static String ConvertAnyR(long num, int m, int n) {
  long t;
  long num10;

  // 1. Checking data for correctness
  if ((m<2)||(m>10)||(n<2)||(n>10))
    return "Incorrect data";

  if (m==10) {
    // Convert to the number system with base n
    if (num>0) {
      t = num%n;     // get the last number
      return ConvertAnyR(num/n, 10, n) + String.valueOf(t);
    }
    else {
      return "";
    }
  }
  else {
    // First, translate to the 10th number system
    num10 = ConvertTo10R(num, m, 0);

    // Then call the recursive function
    return ConvertAnyR(num10, 10, n);
  }
}

An example of using the recursive function ConvertAnyR() is given below

...

// Convert the number of calculation system 22 with a base 3
// in a number system with base 5
String numberR = ConvertAnyR(22, 3, 5);
System.out.println("numberR = " + numberR);

...

⇑

11. Recursive function isPrime(). Determine if a number is prime

Task. Develop a recursive function that determines whether a given positive integer N is prime number. A prime number is the number N>1 which has no other divisors except 1 and itself.

Solution. An integer is considered prime if it is divisible by 1 and evenly divided by itself. For example, prime numbers are 2, 3, 5, 17, etc.

The recursive isPrime() function returns true if the number is prime. Otherwise, the function returns false

// Recursive function that determines if a number is prime
public static boolean isPrime(int num, int tnum, int k) {
  if (tnum>1) {
    // If the number num is evenly divisible by tnum, then increase k
    if ((num%tnum)==0)
      k++;

    // Move to next iteration decreasing tnum by 1
    return isPrime(num, tnum-1, k);
  }
  else {
    k++;
    if (k>2)
      return false;
    else
      return true;
  }
}

A function call from another method can be, for example, like this

...

// Determine if 25 is prime
boolean f = isPrime(25, 25, 0);
System.out.println("isPrime(25) = " + f);

// Determine if 2 is prime
f = isPrime(2, 2, 0);
System.out.println("isPrime(2) = " + f);

...

⇑

---

Related topics

• Recursion. Examples of tasks solving. Advantages and disadvantages of recursion

⇑

---