Рекурсивные функции

Использование функции в теле самой функции называется рекурсивным обращением к функции или рекурсией. Язык программирования С разрешает рекурсивное описание функций.

Рекурсия применяется в основном тогда, когда природа самой решаемой задачи рекурсивна. Как правило, это различные комбинаторные задачи, решаемые полным или неполным перебором; деревья, когда уже само их определение через поддеревья (которые, в свою очередь, сами являются деревьями) подчеркивает их рекурсивную природу, и многие другие задачи.

Рассмотрим пример вычисления факториала с помощью рекурсивной функции – это функция f(n)=n!. Такую функцию можно определить рекурсивно следующим образом:

Отсюда видно, что n! определяется через n×(n-1)!, т.е. через эту же функцию, но для предыдущего значения аргумента. Факториал вычисляется только от натуральных чисел, т.е. чисел больше или равных нулю, и обязательно целых.

Пример описания рекурсивной функции:

int fact(int n)

{

if (n=0)fact=1;

else fact=n*fact(n-1);

return fact;

}

Рассмотрим процесс вычисления рекурсивной функции. Пусть, например, вызывается функция в виде fact(3). При входе в функцию локальной переменной n присваивается значение равное 3 (n=3).

Так как n¹0, то выполняется оператор fact=3*fact(2); в правой части стоит вызов функции fact(2), поэтому происходит обращение к функции fact с параметром 2. Теперь переменной n присваивается новое значение равное 2 (n=2).

Так как n¹0, то выполняется оператор fact=2*fact(1); в правой части стоит вызов функции fact(1), следовательно, произойдет обращение к функции fact с параметром 1. Опять присваивается новое значение переменной n равное 1 (n=1).

Так как n¹0, то выполняется оператор fact=1*fact(0); опять происходит обращение функции самой к себе (заметим, что каждый раз откладывается завершение вычисления правой части). Теперь n=0, поэтому происходит присваивание fact=1; при получении данного результата завершается вычисление fact(2), далее выполняется оператор fact=3*fact(2), что дает конечный результат fact(3)=6.

Рекурсия обычно не даёт никакой экономии памяти, поскольку создается стек для обрабатываемых значений, не приводит она и к созданию более быстрых программ, но рекурсивные программы более компактны и они зачастую становятся более легкими для понимания и написания.

Варианты заданий

Дата добавления: 2015-07-26; просмотров: 223; Нарушение авторских прав

Мы поможем в написании ваших работ!