Означення називається рекурсивним, якщо воно задає елементи множини за допомогою інших елементів цієї ж множини. Об'єкти, задані рекурсивним означенням, також називаються рекурсивними.
Рекурсія — це такий спосіб організації обчислювального процесу, за якого процедура або функція звертається сама до себе. Такі звернення називаються рекурсивними викликами, а підпрограма, що містить рекурсивні виклики, — рекурсивною.
У рекурсивних підпрограмах можна виділити два процеси: рекурсивне занурення підпрограми в себе, що відбувається доти, доки її параметр не сягне граничного значення, та рекурсивне повернення з підпрограми, що відбувається доти, доки її параметр не сягне початкового значення. При розробці рекурсивної підпрограми необхідно визначити умову зупинення рекурсивного занурення, що називається умовою завершення рекурсії.
Максимальна кількість незавершених рекурсивних викликів під час виконання рекурсивної підпрограми називається глибиною рекурсії.
Використання рекурсії може призвести до нестачі стекової пам'яті та уповільнення швидкості виконання програми. Тому не варто застосовувати рекурсію тоді, коли задача має очевидне ітеративне розв'язання. Значні витрати стекової пам'яті пов'язані із тим, що в рекурсивній підпрограмі, як правило, оголошується численна кількість локальних об'єктів: змінних, констант, типів, вкладених підпрограм тощо. Кожного разу, коли підпрограма викликається рекурсивно, виділяється стекова пам'ять для всіх її локальних об'єктів, і тому велика глибина рекурсії може призвести до нестачі стекової пам'яті.