Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Свойства рекурсивных алгоритмов:

• Правильный рекурсивный алгоритм не должен создавать бесконечную последовательность вызовов самого себя.
• Для этого он обязательно должен содержать нерекурсивный выход, т.е. при некоторых исходных данных вычисления в алгоритме должны производиться без вызовов его самого - тривиальный случай.
• Определение сложного случая в терминах более простого.
• При любых исходных данных нерекурсивный выход должен достигаться за конечное число рекурсивных вызовов. Для этого каждый новый вызов рекурсивного алгоритма должен решать более простую задачу, т.е. рекурсивный алгоритм должен содержать определение некоторого сложного случая в терминах более простого случая.