Число слов в тексте. Рекурсивный метод

Автор — Панфилов Александр, преподаватель.

Постановка задачи. Разработать рекурсивный метод для определения количества слов в заданной строке. Считать, что слова разделяются символом «пробел».

Замечание. Данную задачу целесообразнее выполнять в виде не рекурсивной (обычной) функции. Однако, для целей понимания связи между рекурсивным и итеративным (циклическим) алгоритмом, решим эту задачу в рекурсивном виде.

Решение.
Строку можно рассматривать как символьный массив. Для определения числа слов надо определиться с признаком «конца слова». Таким признаком является условие, что очередной символ – это «пробел», а символ перед ним – не «пробел»:

Решение данной задачи в итеративном виде (через цикл) – это последовательный перебор всех символов строки и обнаружение (с суммированием) признаков «конца слова».
Для рекурсивного подхода применяется «ленивое вычисление» — при очередном вызове такая функция проверит только текущую пару символов на «конец слова», прибавит 1 если признак «конец слова» найден, и передаст дальнейший просмотр строки следующему вызову этой же функции. Т.е. используется правило «проверю только текущую пару символов, а остальной подсчет – пусть делают другие (вызовы функций)»:

В общем виде получаем «формулу» расчета:
Число слов в строке от k до N-1 символов = (0 или 1) + Число слов в строке от k+1 до N-1 символов.

Словесный алгоритм работы будет такой:
Простейший случай – дошли до конца строки, и значит — вернуть 0 слов.
Если нашли признак конца слова, то вернуть (1 + продолжить подсчет со следующего символа).
Иначе – продолжить подсчет со следующего символа.

Полный код программы

using System;
namespace Recursive
{
   class Program
   {
      static void Main(string[] args)
      {
         string str = Console.ReadLine(); //получение строки с клавиатуры
         //вызов рекурсивной функции
         int count = RecCountWords(str + " ", 0);
         Console.WriteLine(count);            
      }
      //рекурсивный подсчет числа слов в строке str, начиная с символа start
      private static int RecCountWords(string str, int start)
      {
         //если дошли до конца строки - 0 слов
         if (start >= str.Length)
            return 0;
         else
         {
            Console.WriteLine($"вызов при {start} = \"{str[start]}\"");
            //если текущий символ="пробел", а до него НЕ "пробел"
            if (start > 0 && str[start] == ' ' && str[start - 1] != ' ')
               //найдена граница слова
               return 1 + RecCountWords(str, start + 1); //добавить 1 слово
            else
               //это не конец слова - продолжаем проверку
               return RecCountWords(str, start + 1);
         }
      }
   }
}

Задачи на самостоятельную работу
1. Дан одномерный массив целых чисел. Разработайте рекурсивную функцию для расчета суммы чисел этого массива. Подсказка: Сумма_Элементов(от k до N-1) = mas[k] + Сумма_Элементов(от k+1 до N-1).
2. Дано слово, состоящее только из строчных латинских букв. Разработайте рекурсивную функцию, проверяющую, что это слово является палиндромом. При решении этой задачи нельзя пользоваться циклами.

Оставьте комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Пролистать наверх