C#, Теория

C#. Рекурсия. Примеры рекурсивных методов (функций) в C#




Рекурсия. Примеры рекурсивных методов (функций) в C#

В данной теме показано, что с помощью рекурсии можно легко разрабатывать методы, которые решают задачи любой сложности.

Содержание

Поиск на других ресурсах:

1. Что такое рекурсия? Что такое рекурсивный метод (функция)?

Рекурсия – это разработка метода таким образом, чтобы он вызывал сам себя. Рекурсивные вызовы метода должны завершаться при достижении некоторого условия. В противном случае произойдет переполнение памяти и программа «зависнет» не достигнув вычисления необходимого результата.

Рекурсивный метод – это метод, который вызывает сам себя. В рекурсивном методе помещается вызов этого же метода по его имени.

Последовательный процесс рекурсивных вызовов метода подобен циклическому процессу.

  ⇑

2. Как работает рекурсивный вызов метода?

Если метод вызывает сам себя, то в памяти происходят следующие процессы:

  • в системном стеке выделяется память для новых локальных переменных и параметров;
  • программный код метода выполняется сначала с новыми локальными переменными и параметрами. Эти локальные переменные и параметры получают новые начальные значения. Сам программный код метода не копируется;
  • при возврате из рекурсивного метода (оператор return) происходит восстановление старых локальных переменных и параметров а также их значений в точке вызова этого метода.

  ⇑

3. Какие преимущества дает использование рекурсии в программах?

Рекурсию всегда сравнивают с итерацией. Для многих задач рекурсия дает следующие взаимосвязанные преимущества:

  • при вызове рекурсивной функции не нужно дополнительно сохранять временные значения локальных переменных. Компилятор строит код рекурсивной функции таким образом, что временные значения локальных переменных автоматически сохраняются при каждом рекурсивном вызове;
  • в некоторых случаях рекурсивные алгоритмы выглядят более упрощенно и более наглядно чем итерационные. Это связано с тем, что в итерационных алгоритмах для запоминания промежуточных результатов нужно вводить дополнительные переменные, которые могут усложнить восприятие хода выполнения самого алгоритма.

  ⇑

4. Какие недостатки использования рекурсии в программах?

В сравнении с итерационными вызовами, построение рекурсивных вызовов имеет следующие недостатки:

  • для заданного алгоритма рекурсивные вызовы работают медленнее чем итерационные. Это связано с дополнительными затратами системных ресурсов на неоднократные вызовы методов;
  • многоразовый вызов методов может привести к переполнению системного стека. В этом случае среда CLR сгенерирует соответствующую исключительную ситуацию. Поэтому, важно, чтобы рекурсивный метод был разработан таким образом, чтобы в нем объявлялось минимально возможное количество параметров и локальных переменных.

  ⇑

5. Пример вычисления суммы ряда

Разработать рекурсивную функцию вычисления суммы ряда

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

при n>0.

Программный код функции следующий

// рекурсивная функция - сумма
static int S(int n)
{
    if (n == 1)
        return 5;
    else
        return 5 * n + S(n - 1);
}

  ⇑

6. Пример конвертирования строки «AAABCCCCAADDDEF» => «3AB4C2A3DEF»

Данная задача очень удобно решается с помощью рекурсии. По данному образцу можно разрабатывать рекурсивные функции, которые обрабатывают строки по любым правилам.

В рекурсивной функции ConvertStr() рекурсивно просматривается вся строка. На каждом рекурсивном вызове обрабатывается один символ строки. В зависимости от позиции текущего обрабатываемого символа происходит соответствующий рекурсивный вызов функции.

Рекурсивная функция содержит следующие параметры:

  • строка s типа string, которая обрабатывается;
  • переменная, определяющая позицию символа в строке s на данном уровне рекурсии. Символ s[pos] имеет тип char;
  • целое число k, определяющее количество повторений символа s[pos] на данному уровне рекурсии;
  • переменная c типа char, которая представляет символ на предыдущем уровне рекурсии. Это необходимо, так как символы, которые встречаются один раз подряд должны обрабатываться по особому.
// рекурсивная функция обработки строки
static string ConvertStr(string s, int pos, char c, int k, string s2)
{
  if (pos < s.Length) // пока не последний символ S[pos] - осуществляются рекурсивные вызовы
  {
    if (pos == 0) // первый символ строки
      // перейти к обработке следующего символа
      return ConvertStr(s, pos + 1, s[pos], 1, s2);
    else // не первый символ строки
    {
      if (s[pos] == c) // если следующий и предыдущий символы совпадают, то движемся дальше
        return ConvertStr(s, pos + 1, s[pos], k + 1, s2);
      else // если символы отличаются, то зафиксировать в строке s2 временный результат
      {
        // если k==1, то просто добавить к s2 символ c,
        // иначе, перед символом c поставить число k
        if (k == 1)
          s2 = s2 + c.ToString();
        else
          s2 = s2 + k.ToString() + c.ToString(); // s2 = s2 + "AAA' = s2 + "3A"
        // перейти на следующий уровень рекурсии, продолжить обработку строки
        return ConvertStr(s, pos + 1, s[pos], 1, s2);
      }
    }
  }
  else // пройдена вся строка
  {
    // завершить обработку строки
    if (k == 1)
      s2 = s2 + c.ToString();
    else
      s2 = s2 + k.ToString() + c.ToString();
    return s2; // окончание рекурсивного процесса
  }
}

Использование функции в другом программном коде

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. Пример сравнения строк

Разработать рекурсивную функцию, которая сравнивает две строки на идентичность. Две строки считаются идентичными, если:

  • длина строк совпадает;
  • совпадают символы каждой строки, которые находятся на одинаковых позициях.

Рекурсивная функция должна получать следующие параметры:

  • ссылку на первую строку, которая сравнивается со второй строкой;
  • ссылку на вторую строку, которая сравнивается с первой строкой;
  • текущую позицию символов строк, которые сравниваются.

Функция должна возвращать результат типа bool. Если строки идентичны, то функция возвращает true, иначе функция возвращает false.

// рекурсивная функция сравнения строк
static bool EqualStrings(string s1, string s2, int pos)
{
  if (s1.Length != s2.Length) // равны ли длины строк?
    return false;
  else
    if (pos < s1.Length)
    {
      // если символы в одинаковых позициях не совпадают, то false
      // иначе перейти на следующий уровень рекурсии
      if (s1[pos] != s2[pos])
        return false;
      else
        return EqualStrings(s1, s2, pos + 1);
    }
    else
      return true; // пройдены все символы строк: строки равны
}

Использование функции в другом программном коде

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. Пример рекурсивной функции реверсирования строки

Программный код функции следующий

// реверсирование строки
static string RString(string s1, int pos)
{
  if (pos < s1.Length)
    return s1[s1.Length - pos - 1].ToString() + RString(s1, pos + 1);
  else
    return ""; // пройдена вся строка - окончание рекурсивного процесса
}

В функции RString() определение последнего символа в строке происходит по формуле:

s1[s1.Length - pos - 1]

Затем этот символ переводится в строку методом ToString(). Символ строки добавляется к следующему (предшествующему) символу в строке с помощью рекурсивного вызова

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

Поскольку функция должна что-то возвратить, то перед формулой обработки строки нужно вставить оператор return

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

Использование функции RString() в другом методе может быть следующим:

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. Пример рекурсивной функции определения, является ли строка симметричной

Разработать рекурсивную функцию, которая определяет есть ли симметричной часть строки s, начиная с i-го элемента и заканчивая j-м элементом

// рекурсивная функция, которая определяет, есть ли строка симметричной
// параметр pos смещение от i к (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]) // сравнение символов строки
      return false;
    else
      return IsSymmetric(s, i, j, pos + 1); // рассмотреть следующие два символа
  }
  else
    return true; // пройдена вся строка
}

В вышеприведенной функции сравниваются символы, которые размещаются на позициях i+pos и j-pos строки с помощью оператора if

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

Параметр pos есть смещением, которое добавляется к значению i: i+pos. Между позициями i и j есть некоторые символы, которые формируют некоторый диапазон. Не нужно проходить параметром pos весь диапазон от i к j. Достаточно просмотреть только половину диапазона, поэтому функция содержит проверку:

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

где

((j - i) / 2)

есть середина диапазона (j-i) в соответствии с условием задачи.

Использование функции в другом программном коде

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

  ⇑

Связанные темы

  ⇑