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

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

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

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

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

Решение данной задачи в итеративном виде (через цикл) – это последовательный перебор всех символов строки и обнаружение (с суммированием) признаков «конца слова».
Для рекурсивного подхода применяется «ленивое вычисление» — при очередном вызове такая функция проверит только текущую пару символов на «конец слова», прибавит 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. Дано слово, состоящее только из строчных латинских букв. Разработайте рекурсивную функцию, проверяющую, что это слово является палиндромом. При решении этой задачи нельзя пользоваться циклами.


NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.


Понравилась статья? Поделиться с друзьями:
0 0 голоса
Рейтинг статьи
Подписаться
Уведомить о
0 комментариев
Межтекстовые Отзывы
Посмотреть все комментарии
0
Оставьте комментарий! Напишите, что думаете по поводу статьи.x
()
x