Принцип индуктивного определения в рекурсивных алгоритмах заключается в том, что значения функции для данных аргументов определяются значениями функции для более простых аргументов (уже вычисленных) или значениями более простых функций. 3

Например, простейшим примером рекурсивного определения являются числа Фиббоначи, представляющие собой последовательность чисел, где каждое последующее число является суммой двух предыдущих чисел. 3

Также существует метод структурной индукции, который используется для доказательства свойств рекурсивных программ. 5 Схема доказательства включает два шага: 5

1. Доказать, что программа работает правильно для простейших данных (аргументов функции). 5
2. Доказать, что программа работает правильно для более сложных данных (аргументов функции) в предположении, что она работает правильно для более простых данных. 5