Июнь 2007 1 Рекурсия Итерация свойственна человеку, рекурсия - божественна. Л. Питер Дойч. - презентация

1 Июнь Рекурсия Итерация свойственна человеку, рекурсия - божественна. Л. Питер Дойч

2 Июнь Основные вопросы Основные понятия. Основные понятия. Виды рекурсии. Виды рекурсии. Область применения рекурсивных функций. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена рекурсии итерацией. Замена итерации рекурсией. Замена итерации рекурсией. Особенности работы с памятью Особенности работы с памятью

3 Июнь Понятие рекурсии Рекурсия - это способ организации обработки данных, при котором программа (процедура) вызывает сама себя непосредственно, либо с помощью другой программы (процедуры). Рекурсия - это способ организации обработки данных, при котором программа (процедура) вызывает сама себя непосредственно, либо с помощью другой программы (процедуры). Морис Эшер «Рисующие руки» И обнаружил микроскоп Что на клопе бывает клоп, Питающийся паразитом. На нём - другой, ad infinitum. Джонатан Свифт

4 Июнь Прямая и косвенная рекурсии Прямая рекурсия – вызов подпрограммы непосредственно в ее теле Прямая рекурсия – вызов подпрограммы непосредственно в ее теле Косвенная рекурсия – вызов подпрограммы через другие подпрограммы, например, когда процедура А вызывает процедуру B, процедура B – процедуру C, процедура C – процедуру А. Косвенная рекурсия – вызов подпрограммы через другие подпрограммы, например, когда процедура А вызывает процедуру B, процедура B – процедуру C, процедура C – процедуру А.

5 Июнь Пример прямой рекурсии – вычисление факториала int Fact(int n){ if(n<2) return 1; return (n* Fact(n-1)); } int Fact(int n){ return (n>1)?(n* Fact(n-1):1; }… int res = Fact(4); 1. Вызов Fact(4) 1. Вызов Fact(3) 1. Вызов Fact(2) 1. Вызов Fact(1) 1. Возврат 1 2. Возврат 1*2 2. Возврат 2*3 2. Возврат 6*4 2. res = 24;

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

7 Июнь Область применения рекурсии 1. Компактная реализация рекурсивных алгоритмов 2. Работа со структурами данных, которые описаны рекурсивно, например, двоичные деревья.

8 Июнь Двоичное дерево

9 Июнь Достоинства и недостатки рекурсии Компактная запись, лаконичность при реализации рекурсивных алгоритмов Компактная запись, лаконичность при реализации рекурсивных алгоритмов Накладные расходы на дополнительные вызовы функций Накладные расходы на дополнительные вызовы функций Возможность переполнения стека Возможность переполнения стека Сложность алгоритма для понимания Сложность алгоритма для понимания

10 Июнь Вычисление факториала Возвращаемое значение 1 Параметр 1 Адрес возврата Возвращаемое значение 2 Параметр 2 Адрес возврата Возвращаемое значение 6 Параметр 3 Адрес возврата Возвращаемое значение 24 Параметр 4 Адрес возврата Вызов Fact(4) Вызов Fact(3) Вызов Fact(2) Вызов Fact(1) Если в функции используются локальные переменные, то под них также будет резервироваться место в стеке

11 Июнь Использование глобальных переменных В рекурсивных функциях использование глобальных переменных ограничено В рекурсивных функциях использование глобальных переменных ограничено Модификация глобальной переменной отразится на всей цепочке вызовов функции. Модификация глобальной переменной отразится на всей цепочке вызовов функции. Невозможно определить на каком шаге рекурсии была модифицирована глобальная переменная. Невозможно определить на каком шаге рекурсии была модифицирована глобальная переменная.

12 Июнь Замена рекурсии итерацией Любую рекурсивную функцию можно реализовать без применения рекурсии, для этого программист должен обеспечить хранение всех необходимых данных Любую рекурсивную функцию можно реализовать без применения рекурсии, для этого программист должен обеспечить хранение всех необходимых данных int Fact(int n){ int res = 1; for(int i = 1; i<=n; i++) res *=i; return res; }

13 Июнь Замена итерации рекурсией Любую итерацию можно заменить с помощью рекурсии Любую итерацию можно заменить с помощью рекурсии void fill(int *m, int size){ for(int i = 0; i

14 Июнь Вопросы к экзамену Рекурсия. Основные понятия. Виды рекурсии. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена итерации рекурсией. Рекурсия. Основные понятия. Виды рекурсии. Область применения рекурсивных функций. Достоинства и недостатки рекурсии. Замена рекурсии итерацией. Замена итерации рекурсией.