Приветствую вас, дорогие читатели! Сегодня я хочу рассказать о таком замечательном понятии как Рекурсия. А также решить несколько задач с подробным объяснением.
Что такое рекурсия?
Рекурсия - ситуация, когда подпрограмма вызывает сама себя.
Если объяснять еще более простым языком, то Рекурсия - это повторение одного и того же объекта несколько раз. Самый яркий пример рекурсии - это матрешка. С каждым разом она становится все меньше и меньше, повторяя себя каждый раз.
Большинство современных языков программирования поддерживают механизм рекурсивного вызова, когда функция, как элемент структуры языка программирования, возвращающая вычисленное значение по своему имени, может вызывать сама себя с другим аргументом.
С теорией разобрались, а теперь переходим к практике:
Рассмотрим первую и самую простую задачу на рекурсию:
1. Алгоритм вычисления значения функции F(n) , где n - натуральное число, задан следующими соотношениями:
F(1) = 1
F(n) = F(n-1)*n, при n > 1
Чему равно значение функции F(5) ?
Разбор задачи:
Проще говоря: n - это число, которое записано в F. По условию, нам нужно вычислить, чему равно F(5). Его мы записываем самым первым, затем вычисляем, чему оно равно. Исходя из нашей задачи F() вычисляется так: F(n) = F(n-1)*n. В случае с F(5) = F(5-1)*5. Мы видим, что 5-1 это 4, значит нам нужно узнать F(4), аналогично F(5). В конечном счете, мы доходим до F(1), а оно равно 1 по условию. Теперь остается подставить к F(2) значение F(1) и посчитать всё остальное до F(5).
F(5) = F(5-1)*5 = F(4)*5 = 24*5 = 120
F(4) = F(4-1)*4 = F(3)*4 = 6*4 = 24
F(3) = F(3-1)*3 = F(2)*3 = 2*3 = 6
F(2) = F(2-1)*2 = F(1)*2 = 1*2 = 2
F(1) = 1 (по условию)
Ответ: 120.
Как видите здесь нет ничего сложного. Нужно только знать порядок и внимательно читать условие задачи. Ну и естественно не ошибиться в расчетах)
Разберем более сложную задачу:
2. Алгоритм вычисления значения функции F(n) , где n - натуральное число, задан следующими соотношениями:
F(1) = 1, F(2) = 1
F(n) = F(n-2)*(n-1), при n > 2
Чему равно значение функции F(7) ?
Разбор задачи:
Здесь чуть сложнее стало в вычислениях, а так алгоритм абсолютно тот же.
F(7) = F(5)*6
F(5) = F(3)*4
F(3) = F(1)*2
F(1) = 1 (по условию)
Считаем:
F(7) = F(5)*6 = 8*6 = 48
F(5) = F(3)*4 = 2*4 = 8
F(3) = F(1)*2 = 1*2 = 2
Ответ: 48.
Бывают задания, где нужно посчитать количество звездочек. Условие к таким задачам к сожалению не смог найти, но зато есть решение:
F(6) = *F(3)F(4)F(3)F(3) = 97
F(4) = *F(1)F(2)F(2)F(2) = 45
F(3) = *F(0)F(1)F(1)F(1) = 17
F(2) = *F(-1)F(0)F(1)F(1) = 13
F(1) = *F(-2)F(-1)F(0)F(0) = 5
F(0) = *
F(-1) = *
F(-2) = *
Ответ: 97 звездочек.
Разберем последний пример, когда есть не только F, но и G. Условия то же к сожалению не нашел. Здесь, как видите тоже нужно посчитать количество звездочек:
F(11) = G(10) = 4
G(10) = *F(8) = 4
F(8) = G(7) = 3
G(7) = *F(5) = 3
F(5) = G(4) = 2
G(4) = *F(2) = 2
F(2) = G(1) = 1
G(1) = *
Ответ: 4 звездочки.
В заключение:
Надеюсь мне удалось вам подробно объяснить, как что такое рекурсия и как её решать.
Потренироваться решать задачи на рекурсию
Подписывайтесь на канал, чтобы не пропустить все самое интересное, обучаться новому и прокачать свой скилл.
Пишите в комментариях ваши вопросы и я обязательно на них отвечу!