# data[].attributes.body
Задачи для тренировки

# data[].attributes.attachment_link.readable_text
Здравствуй Хабрахабр!

В этой статье речь пойдет о задачах на рекурсию и о том как их решать.

Кратко о рекурсии

Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию - это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив. Таким образом, камера будет записывать изображение экрана компьютера, и выводить его же на этот экран, получится что-то вроде замкнутого цикла. В итоге мы будем наблюдать нечто похожее на тоннель.

В программировании рекурсия тесно связана с функциями, точнее именно благодаря функциям в программировании существует такое понятие как рекурсия или рекурсивная функция. Простыми словами, рекурсия - определение части функции (метода) через саму себя, то есть это функция, которая вызывает саму себя, непосредственно (в своём теле) или косвенно (через другую функцию).

О рекурсии сказано много. Вот несколько хороших ресурсов:

Предполагается что читатель теоритически знаком с рекурсией и знает что это такое. В данной статье мы бóльшее вниманиее уделим задачам на рекурсию.

Задачи

При изучении рекурсии наиболее эффективным для понимания рекурсии является решение задач.

Как же решать задачи на рекурсию ?

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

из сети

Так же как и у перебора (цикла) у рекурсии должно быть условие остановки - Базовый случай (иначе также как и цикл рекурсия будет работать вечно - infinite). Это условие и является тем случаем к которому рекурсия идет (шаг рекурсии). При каждом шаге вызывается рекурсивная функция до тех пор пока при следующем вызове не сработает базовое условие и произойдет остановка рекурсии(а точнее возврат к последнему вызову функции). Всё решение сводится к решению базового случая. В случае, когда рекурсивная функция вызывается для решения сложной задачи (не базового случая) выполняется некоторое количество рекурсивных вызовов или шагов, с целью сведения задачи к более простой. И так до тех пор пока не получим базовое решение.

Итак рекурсивная функция состоит из

Условие остановки или же Базовый случай

Условие продолжения или Шаг рекурсии - способ сведения задачи к более простым.

Рассмотрим это на примере нахождения факториала:
public class Solution { public static int recursion(int n) { // условие выхода // Базовый случай // когда остановиться повторять рекурсию ? if (n == 1) { return 1; } // Шаг рекурсии / рекурсивное условие return recursion(n - 1) * n; } public static void main(String[] args) { System.out.println(recursion(5)); // вызов рекурсивной функции } }

Тут Базовым условием является условие когда n=1. Так как мы знаем что 1!=1 и для вычисления 1! нам ни чего не нужно. Чтобы вычислить 2! мы можем использовать 1!, т.е. 2!=1!*2. Чтобы вычислить 3! нам нужно 2!*3... Чтобы вычислить n! нам нужно (n-1)!*n. Это и является шагом рекурсии. Иными словами, чтобы получить значение факториала от числа n, достаточно умножить на n значение факториала от предыдущего числа.

В сети при обьяснении рекурсии также даются задачи нахождения чисел Фибоначчи и Ханойская башня

Рассмотрим же теперь задачи с различным уровнем сложности.
Попробуйте их решить самостоятельно используя метод описанный выше. При решении попробуйте думать рекурсивно. Какой базовый случай в задаче? Какой Шаг рекурсии или рекурсивное условие?

Поехали! Решения задач предоставлены на языке Java.

A: От 1 до n
Дано натуральное число n. Выведите все числа от 1 до n.

B: От A до B
Даны два целых числа A и В (каждое в отдельной строке). Выведите все числа от A до B включительно, в порядке возрастания, если A < B, или в порядке убывания в противном случае.

C: Функция Аккермана
В теории вычислимости важную роль играет функция Аккермана A(m,n), определенная следующим образом:

Даны два целых неотрицательных числа m и n, каждое в отдельной строке. Выведите A(m,n).

D: Точная степень двойки
Дано натуральное число N. Выведите слово YES, если число N является точной степенью двойки, или слово NO в противном случае.
Операцией возведения в степень пользоваться нельзя!

E: Сумма цифр числа
Дано натуральное число N. Вычислите сумму его цифр.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется).

F: Цифры числа справа налево
Дано натуральное число N. Выведите все его цифры по одной, в обратном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

G: Цифры числа слева направо
Дано натуральное число N. Выведите все его цифры по одной, в обычном порядке, разделяя их пробелами или новыми строками.
При решении этой задачи нельзя использовать строки, списки, массивы (ну и циклы, разумеется). Разрешена только рекурсия и целочисленная арифметика.

H: Проверка числа на простоту
Дано натуральное число n>1. Проверьте, является ли оно простым. Программа должна вывести слово YES, если число простое и NO, если число составное. Алгоритм должен иметь сложность O(logn).
Указание. Понятно, что задача сама по себе нерекурсивна, т.к. проверка числа n на простоту никак не сводится к проверке на простоту меньших чисел. Поэтому нужно сделать еще один параметр рекурсии: делитель числа, и именно по этому параметру и делать рекурсию.

I: Разложение на множители
Дано натуральное число n>1. Выведите все простые множители этого числа в порядке неубывания с учетом кратности. Алгоритм должен иметь сложность O(logn).

J: Палиндром
Дано слово, состоящее только из строчных латинских букв. Проверьте, является ли это слово палиндромом. Выведите YES или NO.
При решении этой задачи нельзя пользоваться циклами, в решениях на питоне нельзя использовать срезы с шагом, отличным от 1.

Решение
public class Solution { public static String recursion(String s) { // Базовый случай if (s.length() == 1) { return "YES"; } else { if (s.substring(0, 1).equals(s.substring(s.length() - 1, s.length()))) { // Базовый случай if (s.length() == 2) { return "YES"; } // Шаг рекурсии / рекурсивное условие return recursion(s.substring(1, s.length() - 1)); } else { return "NO"; } } } public static void main(String[] args) { System.out.println(recursion("radar")); // вызов рекурсивной функции } }

public class Solution { public static boolean recursion(String s) { char firstChar; char lastChar; int size = s.length(); String subString; // Базовый случай if (size <= 1) { return true; } else { firstChar = s.toCharArray()[0]; lastChar = s.toCharArray()[size - 1]; subString = s.substring(1, size - 1); // Шаг рекурсии / рекурсивное условие return firstChar == lastChar && recursion(subString); } } public static void main(String[] args) { // вызов рекурсивной функции if (recursion("radar")) { System.out.println("YES"); } else { System.out.println("NO"); } } }

K: Вывести нечетные числа последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Выведите все нечетные числа из этой последовательности, сохраняя их порядок.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция не возвращает значение, а сразу же выводит результат на экран. Основная программа должна состоять только из вызова этой функции.

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

M: Максимум последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите наибольшее значение числа в этой последовательности.
В этой задаче нельзя использовать глобальные переменные и передавать какие-либо параметры в рекурсивную функцию. Функция получает данные, считывая их с клавиатуры. Функция возвращает единственное значение: максимум считанной последовательности. Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

N: Среднее значение последовательности
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите среднее значение элементов этой последовательности (без учета последнего нуля).
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает кортеж из пары чисел: число элементов в последовательности и их сумма. В программе на языке C++ результат записывается в две переменные, которые передаются в функцию по ссылке.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

O: Второй максимум
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите значение второго по величине элемента в этой последовательности, то есть элемента, который будет наибольшим, если из последовательности удалить наибольший элемент.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы два числа (кроме нуля).

P: Количество элементов, равных максимуму
Дана последовательность натуральных чисел (одно число в строке), завершающаяся числом 0. Определите, какое количество элементов этой последовательности, равны ее наибольшему элементу.
В этой задаче нельзя использовать глобальные переменные. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметра. В программе на языке Python функция возвращает результат в виде кортежа из нескольких чисел и функция вообще не получает никаких параметров. В программе на языке C++ результат записывается в переменные, которые передаются в функцию по ссылке. Других параметров, кроме как используемых для возврата значения, функция не получает.
Гарантируется, что последовательность содержит хотя бы одно число (кроме нуля).

Q: Количество единиц
Дана последовательность натуральных чисел (одно число в строке), завершающаяся двумя числами 0 подряд. Определите, сколько раз в этой последовательности встречается число 1. Числа, идущие после двух нулей, необходимо игнорировать.
В этой задаче нельзя использовать глобальные переменные и параметры, передаваемые в функцию. Функция получает данные, считывая их с клавиатуры, а не получая их в виде параметров.

R: Треугольная последовательность
Дана монотонная последовательность, в которой каждое натуральное число k встречается ровно k раз: 1, 2, 2, 3, 3, 3, 4, 4, 4, 4,...
По данному натуральному n выведите первые n членов этой последовательности. Попробуйте обойтись только одним циклом for.

S: Заданная сумма цифр
Даны натуральные числа k и s. Определите, сколько существует k-значных натуральных чисел, сумма цифр которых равна d. Запись натурального числа не может начинаться с цифры 0.
В этой задаче можно использовать цикл для перебора всех цифр, стоящих на какой-либо позиции.

T: Без двух нулей
Даны числа a и b. Определите, сколько существует последовательностей из a нулей и b единиц, в которых никакие два нуля не стоят рядом.

U: Разворот числа
Дано число n, десятичная запись которого не содержит нулей. Получите число, записанное теми же цифрами, но в противоположном порядке.
При решении этой задачи нельзя использовать циклы, строки, списки, массивы, разрешается только рекурсия и целочисленная арифметика.
Фунция должна возвращать целое число, являющееся результатом работы программы, выводить число по одной цифре нельзя.
Update от Eivind

Вот и все. Надеюсь решение задач принесло вам столько же удовольствия сколько и мне!

Статья носит информативный характер и в основном расчитана для людей не имеющих большого опыта с рекурсией.
И конечно же, отмечу что, решения задач написанные мной могут не являться самыми эффективными и легкими в понимании. Было бы полезно и интересно увидеть ваши варианты в коментариях.

Буду также очень рад вашим отзывам и замечаниям.

Спасибо!

P.S.: И на последок шутки про рекурсию и еще шутки про рекурсию

# data[].attributes.attachment_link.title
Рекурсия. Тренировочные задачи

# data[].attributes.attachment_link.description
Здравствуй Хабрахабр! В этой статье речь пойдет о задачах на рекурсию и о том как их решать. Рекурсия достаточно распространённое явление, которое встречается не только в областях науки, но и в повседневной жизни. Например, эффект Дросте, треугольник Серпинского и т. д. Один из вариантов увидеть рекурсию - это навести Web-камеру на экран монитора компьютера, естественно, предварительно её включив.

# data[].attributes.headline
Рекурсивная функция 

# data[].attributes.subject
Рекурсивная функция 

# data[].attributes.body
№2

# data[].attributes.attachment_link.title
Рекурсия в C++

# data[].attributes.attachment_link.description
Материалы для изучения рекурсии в языке C++

# data[].attributes.attachment_link.title
Что такое рекурсия - самое простое объяснение