РЕКУРСИЯ

Рекурсивная функция – функция, вызывающая саму себя.

Линейная рекурсия, когда определение объекта включает в себя единственный аналогичный объект.

Ветвящаяся рекурсия, когда включаемых объектов.

Механизм параметров является основным способом обмена информацией между вызываемой и вызывающей функциями. Параметры, перечисленные в заголовке описания функции, называются формальными параметрами, а записанные в операторе вызова функции – фактическими параметрами, или аргументами.

При работе рекурсивной функции купируются части, связанные с локальными данными (формальные, фактические параметры, локальные переменные и точка возврата). Алгоритмическая часть (операторы, выражения) рекурсивной функции и глобальные переменные не меняются, поэтому они присутствуют в памяти компьютера в единственном экземпляре.

Этапы разработки рекурсивной функции:

1. Зацепить рекурсию – определить, что составляет шаг рекурсивного алгоритма.

2. Инварианты рекурсивного алгоритма. Основные свойства, соотношения, которые присутствуют на входе рекурсивной функции и которые сохраняют до следующего рекурсивного вызова, но уже в состоянии, более близком к цели.

3. Глобальные переменные – общие данные процесса в целом.

4. Начальное состояние шага рекурсивного алгоритма – формальные параметры рекурсивной функции.

5. Ограничения рекурсии – обнаруживайте “успеха” – достижения цели на текущем шаге рекурсии и отсечения “неудач” – заведомо неприемлемых вариантов.

6. Правила перебора возможных вариантов – способы формирования рекурсивного вызова.

7. Начальное состояние следующего шага – фактические параметры рекурсивного вызова.

8. Содержание и способ обработки результата – полный перебор с сохранением всех допустимых вариантов, первый возможный, оптимальный.

9. Условия первоначального вызова рекурсивной функции в main.

Линейная рекурсия

Простейшим примером рекурсии является линейная рекурсия, когда функция содержит единственный условный вызов самой себя. В таком случае рекурсия становится эквивалентной обычному циклу. Любой циклический алгоритм можно преобразовать в линейно-рекурсивный, и наоборот.

// рекурсивный алгоритм вычисления факториала

Int fact(int n)

{ if (n==1) return 1; return n*fact(n-1);}

//Циклический алгоритм вычисления факториала

Int fact(int n) {

For (int s=1; n!=0; n--) s*=n;

Return s:}

Типы данных

Способы комментирования

Структура программы

Библиотеки

Структуры

Массивы

Оператор ветвления

Операторы цикла

Функции

Поиск по сайту: