Рекурсія

Рекурсія - Це такий спосіб організації допоміжного алгоритму (підпрограми), при якому ця підпрограма (процедура або функція) в ході виконання її операторів звертається сама до себе. Взагалі, рекурсивним називається будь-який об'єкт, який частково визначається через себе.

Наприклад, наведене нижче визначення двійкового коду є рекурсивним:

:: = |

:: = 0 | 1

Тут для опису поняття були використані, так звані, металінгвістіческій формули Бекуса-Наура (мова БНФ); знак "::=" означає "за визначенням є ", знак" | "-" або ".

Взагалі, в рекурсивної визначенні повинно присутньо обмеження, граничне умова, при виході на яке подальша ініціація рекурсивних звернень припиняється.

Наведемо інші приклади рекурсивних визначень.

Приклад 1. Класичний приклад, без якого не обходяться ні в одному оповіданні про рекурсії, - визначення факторіалу. З одного боку, факторіал визначається так: n! = 1 * 2 * 3 *...* n. З іншого боку, Граничним умовою в даному випадку є n