Рекурсія означає «визначення проблеми в термінах самої себе». Це може бути дуже потужним інструментом для написання алгоритмів. Рекурсія походить безпосередньо з математики, де є багато прикладів виразів, записаних через самих себе. Наприклад, послідовність Фібоначчі визначається так: F(i) = F(i-1) + F(i-2)
Рекурсія застосовується до проблем (ситуацій), де ви можете розбити (зменшити) на менші частини, і кожна частина (частини) виглядає схожою на вихідну проблему. Хороші приклади речей, які містять менші частини, схожі на себе: структура дерева (гілка схожа на дерево) списки (частина списку залишається списком)
Рекурсивна формула — це формула, яка визначає будь-який член послідовності в термінах його попереднього(их) терміна(ів). Наприклад: рекурсивна формула арифметичної послідовності: an = an-1 + d. Рекурсивна формула геометричної послідовності: an = an-1r.
Послідовність Фібоначчі є ще одним класичним прикладом рекурсії: Fib(0) = 0 як базовий випадок 1, Fib(1) = 1 як базовий випадок 2. Для всіх цілих чисел n > 1 Fib(n) = Fib(n − 1) + Fib( n − 2).
Властивості рекурсії Речення можуть бути вкладені в інші речення, іменні фрази в інші іменні фрази тощо. Собаки сестри Наталі. Речення містить іменник dogs, і цей іменник зустрічається в іменниковій фразі sister's dogs, яка міститься в іншій іменниковій фразі, Natalie's sister's dogs.
Завдання, яке можна визначити за допомогою подібної підзадачі, рекурсія є одним із найкращих рішень для цього. наприклад; Факторіал числа. Властивості рекурсії: багаторазове виконання тих самих операцій з різними вхідними даними.