Рекурсия: различия между версиями
Содержимое удалено Содержимое добавлено
JenVan (обсуждение | вклад) м Откат правок 178.187.172.184 (обс.) к версии 213.87.128.86 |
|||
Строка 11:
Вы, наверное, уже заметили сходство понятий рекурсии и [[w:Математическая индукция|математической индукции]]. У рекурсии, как и у математической индукции, есть ''база'' — аргументы, для которых значения функции определены (элементарные задачи), и ''шаг рекурсии'' — способ сведения задачи к более простым.
== Числа Фибоначчи ==
Рассмотрим последовательность чисел <math>1, 1, 2, 3, 5, 8, 13, 21, \dots</math> в которой каждое число является суммой двух предыдущих. Это [[w:Числа Фибоначчи|числа Фибоначчи]]. Формальное их определение таково:
:<math>F(1) = 1</math>, <math>F(2) = 1</math>, <math>F(n) = F(n - 2) + F(n - 1)</math>, если <math>n > 2</math>.
Функция <math>F(n)</math> задана ''рекурсивно'', то есть «через себя». База — значения функции <math>F</math> на аргументах 1 и 2, а шаг — формула <math>F(n) = F(n - 2) + F(n - 1)</math>.
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
== Проблемы рекурсии и как их решать ==
| |||