C#, Theory

C#. Recursion. Examples of recursive methods (functions) in C#

Recursion. Examples of recursive methods (functions) in C#

This topic shows that using recursion you can easily develop methods that solve problems of any complexity.

Contents

Search other websites:

 
1. What is recursion? What is a recursive method (function)?

Recursion is the development of a method in such a way that it calls itself. Recursive method calls must end when a certain condition is reached. Otherwise, a memory overflow will occur and the program will “hang” without reaching the calculation of the required result.

A recursive method is a method that calls itself. In a recursive method, the same method is called using it’s name.

The sequential process of recursive method calls is similar to a cyclic process.

  ⇑

2. How does the recursive method call?

If the method calls itself, then the following processes occur in memory:

  • system stack allocates memory for new local variables and parameters;
  • the program code of the method is executed first with new local variables and parameters. These local variables and parameters receive new initial values. The program code itself is not copied;
  • when returning from the recursive method (the return operator), old local variables and parameters are restored, as well as their values at the call point of this method.

  ⇑

3. What are the advantages of using recursion in programs?

Recursion is always compared with iteration. For many tasks, recursion provides the following interrelated advantages:

  • when calling a recursive function, it is not necessary to additionally save the temporary values of local variables. The compiler builds the code of the recursive function in such a way that the temporary values of local variables are automatically saved with each recursive call;
  • in some cases, recursive algorithms look more simplistic and more vividly than iterative ones. This is due to the fact that in iterative algorithms for storing intermediate results it is necessary to introduce additional variables that may complicate the perception of the progress of the algorithm itself.

  ⇑

4. What are the disadvantages of using recursion in programs?

In comparison with iterative calls, the developing of recursive calls has the following disadvantages:

  • for a given algorithm, recursive calls work slower than iterative calls. This is due to the additional cost of system resources for repeated calls to methods;
  • reusable method calls may overflow the system stack. In this case, the CLR will generate the corresponding exception. Therefore, it is important that the recursive method be designed in such a way that it declares the minimum possible number of parameters and local variables.

  ⇑

5. Example of calculating the sum of a series

Develop a recursive function to calculate the sum of a series

S = 5 + 10 + 15 + … + 5·n,

here n>0.

The function code is as follows.

// recursive function - sum
static int S(int n)
{
    if (n == 1)
        return 5;
    else
        return 5 * n + S(n - 1);
}

  ⇑

6. Example of converting the string “AAABCCCCAADDDEF” => “3AB4C2A3DEF”

This problem is very conveniently solved using recursion. In this sample, you can develop recursive functions that process strings by any rules. The recursive function ConvertStr() recursively scans the entire string. Each recursive call processes one character of the string. Depending on the position of the current symbol being processed, the corresponding recursive function call occurs.

The recursive function contains the following parameters:

  • string s of type string that is being processed;
  • a variable that determines the position of the character in string s at a given recursion level. The symbol s[pos] is of type char;
  • an integer k specifying the number of repetitions of the symbol s[pos] at a given recursion level;
  • a variable c of type char, which represents the character at the previous recursion level. This is necessary because the characters that occur once in a row should be handled in a special way.
// recursive string processing function
static string ConvertStr(string s, int pos, char c, int k, string s2)
{
  if (pos < s.Length)
  {
    if (pos == 0) // first character of string
      // go on to the next symbol
      return ConvertStr(s, pos + 1, s[pos], 1, s2);
    else // not the first character of a string
    {
      if (s[pos] == c) // if the next and previous characters are the same, then move on.
        return ConvertStr(s, pos + 1, s[pos], k + 1, s2);
      else // if the characters are different, then fix the temporary result in the s2 line
      {
        // if k == 1, then simply add the symbol c to s2,
        // otherwise, put the number k in front of the character c
        if (k == 1)
          s2 = s2 + c.ToString();
        else
          s2 = s2 + k.ToString() + c.ToString(); // s2 = s2 + "AAA' = s2 + "3A"

        // go to the next recursion level, continue processing the string
        return ConvertStr(s, pos + 1, s[pos], 1, s2);
      }
    }
  }
  else // passed the entire string
  {
    // complete the string processing
    if (k == 1)
      s2 = s2 + c.ToString();
    else
      s2 = s2 + k.ToString() + c.ToString();
    return s2; // finish the recursive process
  }
}

Using the function in another program code

string resStr;
string s2 = "";
string s = "AAABCCCCAADDDD";
resStr = ConvertStr(s, 0, ' ', 0, s2); // resStr = "3AB4C2A4D"
resStr = ConvertStr("ACDDVFFSA", 0, '+', 0, ""); // resStr = "AC2DV2FSA"
resStr = ConvertStr("+++---;;;zzxkf", 0, '+', 0, ""); // resStr = "3+3-3;2zxkf"
resStr = ConvertStr("ddd", 0, 'z', 0, ""); // resStr = "3d"

  ⇑

7. Example of string comparison

Develop a recursive function that compares two strings for identity. Two strings are considered identical if:

  • the length of the strings is the same;
  • the characters of each string that are in the same positions are matched.

The recursive function should receive the following parameters:

  • reference to the first string, which is compared with the second string;
  • reference to the second string, which is compared with the first string;

The function must return a bool result. If the strings are identical, the function returns true, otherwise the function returns false.

// recursive function of string comparison
static bool EqualStrings(string s1, string s2, int pos)
{
  if (s1.Length != s2.Length) // are the lengths of the strings equal?
    return false;
  else
    if (pos < s1.Length)
    {
      // if the characters in the same positions do not match, then false
      // otherwise go to the next recursion level
      if (s1[pos] != s2[pos])
        return false;
      else
        return EqualStrings(s1, s2, pos + 1);
    }
    else
      return true; // all characters of strings are processed: strings are equal
}

Using the function in another program code

bool b;
b = EqualStrings("abc", "abc", 0); // b = true
b = EqualStrings("abc", "abcd", 0); // b = false
b = EqualStrings("AAA", "AAB", 0); // b = false
b = EqualStrings("", "", 0); // b = true

  ⇑

8. An example of the recursive function of reversing a string

The function code is as follows

// string reversal
static string RString(string s1, int pos)
{
  if (pos < s1.Length)
    return s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1);
  else
    return ""; // passed the entire string - the end of the recursive process
}

In the RString() function, the definition of the last character in a string is as follows:

s1[s1.Length - pos - 1]

Then this character is translated into a string using the ToString() method. The string character is added to the next (previous) character in the string using a recursive call

s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1)

Since the function must return something, then before the formula for processing the string you need to insert the operator return

return s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1);

Using the RString() function in another method may be as follows:

string s;
s = RString("abcd", 0); // s = "dcba"
s = RString("A", 0); // s = "A"
s = RString("", 0); // s = ""
s = RString("www.bestprog.net", 0); // s = "ten.gorptseb.www"

  ⇑

9. An example of a recursive function to determine whether a string is symmetric

Develop a recursive function that determines whether there is a symmetric part of string s, starting with the i-th element and ending with the j-th element

// recursive function that determines whether a string is symmetric
// parameter pos offset from i to (j-i) / 2
static bool IsSymmetric(string s, int i, int j, int pos)
{
  if ( (i + pos) <= ((j - i) / 2))
  {
    if (s[i + pos] != s[j - pos]) // string character comparison
      return false;
    else
      return IsSymmetric(s, i, j, pos + 1); // consider the following two characters
  }
  else
    return true; // passed the entire string
}

The above function compares characters that are placed at i+pos and j-pos positions of a string using the if statement

if (s[i + pos] != s[j - pos])
...

The parameter pos is the offset that is added to the value of i: i+pos. Between the positions i and j there are some symbols that form a certain range. You do not need to pass the entire range from i to j with the pos parameter. It is enough to view only half of the range, so the function contains a check:

if ( (i + pos) <= ((j - i) / 2))
{
  ...
}

here

((j - i) / 2)

is the middle of the range (j-i) in accordance with the condition of the problem.

Using the function in another program code

bool b;
b = IsSymmetric("abcd", 1, 3, 0); // b = false
b = IsSymmetric("abcdefed", 3, 7, 0); // b = true
b = IsSymmetric("aaaa", 2, 2, 0); // b = true
b = IsSymmetric("aabbccbbaa", 0, 9, 0); // b = true
b = IsSymmetric("aabbcbbaa", 0, 8, 0); // b = true
b = IsSymmetric("aabbccbaa", 0, 8, 0); // b = false

  ⇑

Related topics

  ⇑