Рекурсия: различия между версиями

Перейти к навигации Перейти к поиску
1080 байт добавлено ,  7 лет назад
м
Откат правок 178.187.172.184 (обс.) к версии 213.87.128.86
м (Откат правок 178.187.172.184 (обс.) к версии 213.87.128.86)
 
Вы, наверное, уже заметили сходство понятий рекурсии и [[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>.
 
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
 
== Проблемы рекурсии и как их решать ==

Навигация