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

2 байта убрано ,  13 лет назад
Нет описания правки
пока не доберёмся до самых элементарных «шажочков».
 
Представим, что нужно пройти 1000 шагов. Для решения делаем один шаг, остаётся 999: задача упростилась. Сделав такое упрощение 999 раз, дойдём до самой элементарной задачи — шагнуть один раз. Конечно, этот пример слишком прост. Далее мы рассмотрим более сложные примеры, освещающие явление рекурсии как с хорошей так, и с плохой стороны.
 
Вы, наверное, уже заметили сходство понятий рекурсии и [[w:математическая индукция|математической индукции—индукции]]. У рекурсии, как и у математической индукции, есть '''база'''  — аргументы, для которых значения функции определены (элементарные задачи), и '''шаг рекурсии''' — способ сведения задачи к более простым.
 
==Числа Фибоначчи==
<center><math>F(1)=1, F(2)=1, F(n)=F(n-2)+F(n-1)</math>, если <math>n>2</math>.</center>
 
Функция <math>F(n)</math> задана ''рекурсивно'', то есть «через себя». База — значения функции <math>F</math> — её значения на аргументах 1 и 2, а шаг&nbsp;— формула <math>{F(n)=F(n-2)+F(n-1)}</math>.
 
Современные языки программирования дают возможность программировать рекурсивные определения без особых усилий, но в таких определениях таятся опасности.
481

правка