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