Теория:

Когда существует правило, позволяющее находить n - е значение переменной, используя ее предыдущие значения, говорят, что переменная задана рекуррентно. Само правило при этом называют рекуррентным соотношением.
Рекуррентные соотношения часто применяют для вычисления тех или иных «длинных» сумм.
 
Например Sn=1+12+13+14+15+16+17+...+1n1+1n.
Отсюда следует, что
Sn=Sn1+1n.
Полученная формула показывает, что n - е значение переменной S получается из (n-1) - го значения прибавлением 1n.
 
Рассмотрим ещё один классический пример —  игру «Ханойские башни», придуманную ещё в 1883 году Эдуардом Люка. Есть три стержня и 64 кольца, нанизанных на них. В начале все коольца находятся на первом стержне, причём все коольца разного диаметра, и меньшие коольца лежат на боольших. За ход разрешается взять верхнее кольцо с любого стержня и положить на другой стержень сверху, при этом запрещается класть большее кольцо на меньшее. Цель игры состоит в том, чтобы переместить всю пирамиду с первого стержня на второй.
 
1h.png
 
Составить алгоритм сразу для случая 64 дисков кажется сложным. Ясно, что первым действием переносится на другой стержень самый маленький диск. Вторым действием надо на другой стержень перенести второй по размеру диск. А вот третий диск уже и переносить некуда.
Попробуем решить задачу иначе. Пусть на стержене Nr.1 имеется n дисков. При n = 1, переложил диск на второй и все. При n = 2: верхний диск переносим на  стержень Nr.2, второй диск переносим на  стержень Nr.3 и, наконец, меньший диск переносим на  стержень Nr.3. Нетрудно понять, как модифицировать последовательность действий, если мы хотим собрать диски на стержне Nr.2.
Пусть мы умеем переносить башню из n -1 дисков со стержня на любой другой стержень. Берем теперь башню из n дисков. Верхние n - 1 дисков переносим на другой стержень. Оставшийся диск перекладываем на свободный стержень и теперь пользуясь тем же алгоритмом, перекладываем n-1 дисков. Задача решена. Решение построено на том, что при исполнении алгоритма для n дисков мы обращаемся к тому же алгоритму для n -1 дисков.
Ситуация, в которой какой-то алгоритм сам или через другие алгоритмы вызывает себя в качестве вспомогательного, называется рекурсией. Сам алгоритм при этом называется рекурсивным. Из определения рекурсивного алгоритма следует, что он всегда должен быть оформлен как вспомогательный алгоритм. В частности, он может быть представлен подпрограммой - функцией.
 
 
Источники:
Информатика и ИКТ. 10.класс. А.Г. Гейн, А.Б. Ливчак. Москва "Просвещение" 2012