Лабораторная работа №5 (7 неделя) Рекурсия
Цель: изучение рекурсивного способа описания алгоритмов и использование динамических одномерных массивов.

Объекты: TEdit, TUpDown, TStringGrid, TLabel

Задание.

1. 
   Изменить приложение, выполненное на лабораторных работах №3-4 (4-6 неделя), сделав свои процедуры поиска корня рекурсивными. Рекурсивная процедура поиска корня методом бисекции приведена ниже.
   
2. 
   Написать рекурсивную процедуру/функцию для решения задачи, условие которой приведено ниже. Использовать динамический одномерный массив.
   

Рекурсия

Список задач по вариантам
Общие указания: Для решения задачи написать рекурсивную функцию. Рекурсивные вызовы заканчивать, когда останется только один-два элемента. Например, если сумму вычислять как сумму сумм ее половин (почти половин, если нечетное количество слагаемых):

N=5:

;




; ; ;
;

рекурсивные вызовы надо заканчивать при получении суммы одного слагаемого

Для произведения:

Для конъюнкции

Для дизъюнкции

Для количества:

Замечание: Хотя в условиях задач суммы/произведения/количества/конъюнкции/дизъюнкции указаны для элементов массивов с 1, не забывайте, что индекс первого элемента динамического массива – 0!

1. 
   Для заданного одномерного массива A из N элементов проверить, что существует, по крайней мере, один элемент A_i, для которого выполняется условие sin A_i > 0. Рекурсивную функцию применять отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=8: , ( – «или»)

2. 
   Для заданного одномерного массива X из N элементов проверить, что для всех элементов массива выполняется условие –10<<20. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=8: , ( – «и»)

3. 
   Для заданного одномерного массива B из N элементов найти произведение множителей, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=8:

4. 
   Для заданного одномерного массива X из N элементов найти количество элементов массива, для которых выполняется условие. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=8:

5. 
   Для заданного одномерного массива A из N элементов найти значение минимального элемента массива и его номер. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=12:

6. 
   Для заданного одномерного массива B из N элементов найти сумму выражений, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
   

Например, для N=8:

7. 
   Для заданного одномерного массива A из N элементов проверить, что существует хотя бы один элемент A_i, для которого выполняется условие . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента.
   

Например, для N=6: , ( – «или»)

8. 
   Для заданного одномерного массива X из N элементов проверить, что для всех элементов массива выполняется условие cos X_i > 0. Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента.
   

Например, для N=6: , ( – «и»)

9. 
   Для заданного одномерного массива С из N элементов найти произведение множителей, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента.
   

Например, для N=12:

10. 
    Для заданного одномерного массива B из N элементов найти количество элементов массива, для которых выполняется условие. Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента. Например, для N=6:
    

11. 
    Для заданного одномерного массива A из N элементов найти значение максимального элемента массива. Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента.
    

Например, для N=6:

12. 
    Для заданного одномерного массива X из N элементов найти сумму выражений, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один или два элемента.
    

Например, для N=9:

13. 
    Для заданного одномерного массива A из N элементов проверить, что существует по крайней мере один элемент A_i, для которого выполняется условие A_i ≤ i². Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=4: , ( – «или»)

14. 
    Для заданного одномерного массива Y из N элементов проверить, что для всех элементов массива выполняется условие Y_i < 0. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=4: , ( – «и»)

15. 
    Для заданного одномерного массива X из N элементов найти произведение множителей, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=6:

16. 
    Для заданного одномерного массива R из N элементов найти количество элементов массива, для которых выполняется условие. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=8:

17. 
    Для заданного одномерного массива B из N элементов найти значение минимального элемента массива. Рекурсивную функцию применять каждый раз отдельно для каждой из половин массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=4:

18. 
    Для заданного одномерного массива Q из N элементов проверить, что существует по крайней мере один элемент Q_i, для которого выполняется условие |Q_i| > i. Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=5: , ( – «или»)

19. 
    Для заданного одномерного массива Y из N элементов проверить, что для всех элементов массива выполняется условие Y_i sin Y_i > 5. Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=5: , ( – «и»)

20. 
    Для заданного одномерного массива X из N элементов найти произведение множителей, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=5:

21. 
    Для заданного одномерного массива D из N элементов найти количество элементов массива, для которых выполняется условие D_i > i. Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=4:

22. 
    Для заданного одномерного массива B из N элементов найти значение максимального элемента массива и его номер. Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=4:

23. 
    Для заданного одномерного массива Z из N элементов найти сумму выражений, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первого элемента массива и для остальной его части. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=12:

24. 
    Для заданного одномерного массива Y из N элементов проверить, что существует по крайней мере один элемент Y_i, для которого выполняется условие . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=9: , ( – «или»)

25. 
    Для заданного одномерного массива Z из N элементов проверить, что для всех элементов массива выполняется условие . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=9: , ( – «и»)

26. 
    Для заданного одномерного массива X из N элементов найти произведение множителей, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=6:

27. 
    Для заданного одномерного массива A из N элементов найти количество элементов массива, для которых выполняется условие i² > |A_i|. Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=12:

28. 
    Для заданного одномерного массива B из N элементов найти значение минимального значения выражения sin B_i. Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=9:

29. 
    Для заданного одномерного массива Z из N элементов найти сумму выражений, вычисляемых по формуле . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=12:

30. 
    Для заданного одномерного массива Z из N элементов найти значение максимального значения выражения . Рекурсивную функцию применять каждый раз отдельно для первой трети массива и для остальной части (2/3) массива. Рекурсивные вызовы заканчивать, когда останется только один элемент.
    

Например, для N=9:
Некоторые неформальные определения

1.	Рекурсия	А. Введение в определение объекта ссылки на сам объект. Б. Прием сведения решения некоторой задачи к решению серии задач, подобных исходной. В. Свойство алгоритмической системы на промежуточных этапах своего функционирования создавать другие системы, включая идентичные себе самой, и использовать результаты их функционирования в дальнейшей работе. При достаточно широкой трактовке понятия алгоритмической системы концепция рекурсивности отражает основные формы развития материи и является одним из важнейших методов познания. Г. Результат отчуждения (отвлечения, абстрагирования) свойств рекурсивности от совокупности рекурсивных объектов.
2.	Рекурсивный алгоритм (процедура, функция)	A. Алгоритм называется рекурсивным, если в его определении содержится прямой или косвенный вызов этого же алгоритма. Б. Рекурсивная функция - одно из математических уточнений интуитивного понятия вычислимой функции.
3.	Рекурсивные вычисления	Вычисления, проводимые с помощью рекурсивных алгоритмов (процедур, функций).
4.	Прямая рекурсия	Непосредственный вызов алгоритма (функции, процедуры) F из текста самого алгоритма F.
5.	Косвенная (взаимная) рекурсия	Циклическая последовательность вызовов нескольких алгоритмов F1, F2, …, Fk (функций, процедур) друг друга: F1 вызывает F2, F2 вызывает F3, …, Fk вызывает F1 (k>1).
6.	Рекурсивные обращения	Рекурсивные вызовы в прямой или косвенной рекурсии.
7.	Пространство параметров	Пусть tk (k=1, 2, …, n) - параметры задачи (алгоритма, процедуры, функции), принимающие значения из некоторых множеств объектов Mk (k=1, 2, …, n). Декартово произведение M множеств Mk называется пространством параметров задачи. Таким образом, элементами M являются наборы (упорядоченные множества) объектов m1, m2, …, mn , где mkÎ Mk (k=1, 2, …, n) вида: (m1, m2, …, mn). Областью определения параметризованной задачи является совокупность элементов пространства параметров, при которых она имеет решение.
8.	Рекурсивная база	Совокупность наборов значений параметров и соответствующих им решений задачи или простых правил для получения этих решений. Выделение базы - один из основных этапов решения задачи с помощью рекурсии. База может быть динамической, то есть меняться в процессе вычислений.
9.	Индикаторы завершения рекурсивных вызовов	Элементы постоянной или динамической рекурсивной базы.
10.	Полное дерево рекурсивных вызовов	Граф, вершинами которого являются наборы фактических параметров при всех рекурсивных вызовах функции, начиная с обращения к ней, а ребрами - пары таких наборов, соответствующих соседним вызовам. Заметим, что вершины этого дерева удобно называть просто рекурсивными вызовами. Полное дерево рекурсивных вызовов однозначно определяется алгоритмом (функцией, процедурой) и набором её фактических параметров. Заметим, что одни и те же наборы параметров могут соответствовать разным вершинам дерева.
11.	Корень полного дерева рекурсивных вызовов	Вершина полного дерева рекурсивных вызовов, соответствующая начальному обращению к функции (процедуре).
12.	Дерево рекурсивных вызовов	Любое поддерево полного дерева рекурсивных вызовов.
13.	Полная рекурсивная траектория	Пусть X=(x1, x2, …, xn) и F(X) - рекурсивная функция, которую требуется вычислить в некоторой точке X0 из области определения F(X). Конечная последовательность аргументов F(X) вида X0, X1, …, Xn называется рекурсивной траекторией, если элементы Xk (k=1, 2, …, n) - суть наборы параметров при последовательных рекурсивных вызовах, а Xn принадлежит базе рекурсии. Полная рекурсивная траектория указывает последовательность обхода вершин полного рекурсивного дерева.
14.	Рекурсивная траектория	Любая начальная подпоследовательность полной рекурсивной траектории.
15.	Объем рекурсии	Количество вершин полного рекурсивного дерева (полной рекурсивной траектории) без единицы.
16.	Рекурсивный стек (магазин, штабель)	Область памяти, в которую заносятся значения всех локальных переменных алгоритма (программы) в момент рекурсивного обращения. Каждое такое обращение формирует один слой данных стека. При завершении вычислений по конкретному обращению a из стека считывается соответствующий ему слой данных, и локальные переменные восстанавливаются, снова принимая значения, которые они имели в момент обращения a .
17.	Глубина рекурсивных вызовов	Максимальное количество слоев рекурсивного стека, заполняемых при конкретном вычислении значения рекурсивной функции (процедуры, алгоритма). Количество элементов полной рекурсивной траектории всегда не меньше глубины рекурсивных вызовов. Эта величина не должна превосходить максимального размера стека используемой вычислительной среды. В то же время объём рекурсии - это характеристика сложности рекурсивных вычислений для конкретного набора параметров.
18.	Декомпозиция	Процесс последовательного разложения задачи на серию подзадач двух типов: тех, которые мы решать умеем и тех, которые в чем-то аналогичны исходной задаче. В последнем случае каждая из полученных подзадач должна быть упрощенным вариантом предыдущей задачи. При этом декомпозицию следует осуществлять так, чтобы можно было доказать, что при любом допустимом наборе значений параметров рано или поздно она приведет нас к одному из выделенных тривиальных случаев, то есть к задаче с набором параметров, являющимся индикатором завершения рекурсивных вызовов.
19.	Параметризация задачи	Выявление совокупности исходных величин, определяющих постановку и решение задачи. Значения этих параметров или некоторых из них влияют на трудоемкость решения задачи.
20.	Вспомогательные параметры рекурсии	Искусственно вводимые параметры, напрямую с постановкой задачи не связанные, но помогающие изменить тип рекурсии или перейти к обобщенной задаче, где рекурсия проглядывается явно.
21.	Рекурсивная триада	Три основных этапа решения задач с помощью рекурсии: параметризация, выделение базы (или выделение начальной базы и правил её изменения), декомпозиция.
22.	Предвычисления (предварительные вычисления)	Декомпозиция предполагает наличие некоторых вычислений, предшествующих и способствующих переходам к более простым подзадачам. Их называют предварительными вычислениями или предвычислениями. Именно предвычисления и подготавливают переходы к следующим уровням рекурсивных обращений.
23.	Отложенные вычисления	Вычисления, проводимые после того, как рекурсивная траектория попала в базу, то есть стала полной. Возможно, что отложенные вычисления состоят лишь из серии передач значений и управления в порядке, обратном рекурсивным вызовам. В этом случае говорят об отсутствии отложенных вычислений.
24.	Терминальная ветвь рекурсивного алгоритма	Часть алгоритма (процедуры, функции), соответствующая проверке получения какой-либо задачи из рекурсивной базы и тем предписаниям, которые должны быть выполнены, если действительно такая задача при вычислениях будет получена. В алгоритме может быть несколько терминальных ветвей.
25.	Рабочая ветвь рекурсивного алгоритма	Дополнительная к совокупности терминальных ветвей часть алгоритма (процедуры, функции). Рабочая ветвь реализует предвычисления, рекурсивные обращения и отложенные вычисления.
26.	Управляющие параметры рекурсии	Один или несколько параметров задачи, с помощью которых организуется её декомпозиция и обеспечиваются правила выполнения рекурсивных вызовов. Значения управляющих параметров рекурсии могут участвовать в предварительных и отложенных вычислениях.
27.	Прямой и обратный ход вычислений	Рекурсивные вычисления состоят из двух стадий, называемых прямым ходом и обратным ходом. Первая из них соответствует совокупности всех предвычислений, реализуемых до входа рекурсивной траектории в базу, а вторая - совокупности отложенных вычислений, производимых после встречи с индикатором завершения рекурсивных вызовов.
28.	Срез рекурсивных вычислений	При решении задачи каждое рекурсивное обращение, в том числе и начальный запуск вычислений, инициируют работу как бы со своим экземпляром исходного алгоритма. Последовательность вычислений значений локальных и глобальных переменных, соответствующая одному конкретному “виртуальному” экземпляру алгоритма и не включающая в себя вычисления по вызовам из данного экземпляра (но использующая их результаты!), называется срезом рекурсивных вычислений.
29.	Линейная рекурсия	Тип рекурсии, при которой рекурсивные вызовы на любом рекурсивном срезе, инициируют не более одного последующего рекурсивного вызова. Для линейной рекурсии дерево рекурсивных вызовов всегда состоит из одной ветви.
30.	Повторительная рекурсия	Частный случай линейной рекурсии с отсутствующими предварительными или отложенными вычислениями. От повторительной рекурсии достаточно просто избавиться переходом к циклу.
31.	Каскадная (древовидная) рекурсия	Рекурсия, не являющаяся линейной. При каскадной рекурсии, рекурсивные обращения, как правило, приводят к необходимости многократно решать одни и те же подзадачи.
32.	Возвратная рекурсия	Рекурсивная реализация метода перебора с возвратом (backtracking).
33.	Динамическая рекурсивная база	Рекурсивная база, меняющаяся в процессе вычислений. Как правило, она расширяется за счет получения решений промежуточных задач и облегчает выполнение процесса отложенных вычислений. Возможно и сужение рекурсивной базы. Альтернативой динамической базы могут быть организуемые и поддерживаемые в процессе вычислений специальные списки решений промежуточных задач (динамическое программирование).
34.	Формуляр	Специально разработанный расчетный бланк, в котором фиксируется протокол вычислений конкретного рекурсивного среза. Формуляр может быть задан таблицей, деревом Канторовича или иным способом. В нем должна указываться взаимосвязь шагов вычислений и, кроме того, предлагаться место для проведения вычислений.
35.	Воплощение	Заполненный формуляр. Воплощение формируется для каждого рекурсивного среза на отдельном формуляре. Это же самое касается и всех вызовов нерекурсивных подпрограмм, для которых должны быть разработаны свои собственные формуляры.
36.	Рекурсограмма	Последовательность воплощений, соответствующая последовательности рекурсивных вызовов.
37.	Рекурсивная машина обработки формуляров	Если правила заполнения формуляров при решении определенного круга задач с помощью рекурсии некоторым образом формализованы, то этот процесс может быть автоматизирован. В этом смысле можно говорить о виртуальной рекурсивной машине по заполнению формуляров.
38.	Рекуррентное соотношение (рекуррентная формула)	Формула вида an+p=F(an, an+1, …, an+p-1) (p³ 1, n=1, 2, …), позволяющая вычислять любой член бесконечной последовательности a1, a2, …, если заданы её первые p членов. Определяемая рекуррентной формулой последовательность называется возвратной. Прямая реализация рекурсивных вычислений по рекуррентным формулам неизбежно приводит к каскадной рекурсии. Однако во многих важных случаях от каскадной рекурсии удается избавиться. Рекуррентные соотношения часто используются для оценки трудоемкости рекурсивных алгоритмов.
39.	Производящая функция	Производящей функцией числовой бесконечной последовательности a1, a2, …, называют степенной ряд вида с вещественной или комплексной переменной z. Подобные функции играют важную роль в аналитических методах изучения рекуррентных последовательностей.
40.	Удаленная рекурсия	Рекурсивная функция, в теле которой при рекурсивных вызовах, в выражениях, являющихся фактическими параметрами, снова встречаются рекурсивные вызовы этой функции. Удаленная рекурсия трудна в понимании и, как правило, приводит к достаточно громоздким вычислениям.
41.	Рекурсивная тавтология	A. Прямое или косвенное обращение рекурсивной функции (алгоритма, программы) к самой себе с тем же самым набором значений параметров, с которого начиналось вычисление этой функции. B. Рекурсивная функция (алгоритм, программа), допускающая рекурсивную тавтологию.
42.	Адаптивный рекурсивный алгоритм	Алгоритм, который благодаря рекурсивности учитывает те или иные индивидуальные характеристики решаемой задачи из области своего определения.
43.	Рекурсивные определения	Описание совокупности объектов через порождающие правила, содержащие ссылки на сам определяемый объект. Такое описание предполагает наличие некой базы неопределяемых первичных объектов, заданных простым перечислением. Примерами подобных определений являются синтаксические диаграммы Вирта, нотация Бэкуса-Наура. Рекурсивные определения могут быть как прямыми, так и косвенными.
44.	Визуальное мышление	A. Способ решения интеллектуальных задач с опорой на внутренние визуальные образы. B. Вид мышления, продуктом которого является порождение новых образов, создание новых визуальных форм, несущих определенную смысловую нагрузку.
45.	Рекурсивное мышление	A. Способ решения прикладных задач с преимущественной опорой на рекурсивные алгоритмы. B. Разновидность математического (диалектического, продуктивного) мышления, позволяющая видеть рекурсию там, где она на первый взгляд не просматривается.

Пример №1. Для заданного одномерного статического вещественного массива A из N элементов написать рекурсивную процедуру поиска суммы ее элементов.

(type mas = array [1..20] of real;)

a)	б) , k – целая часть от N/2
type mas = array [1..20] of real; Function Sum(A: mas; i,N: byte): real; Begin If i=N Then Result:=A[i] Else Result:=A[i]+Sum(A, i+1, N) end; Вызов S:=Sum(A, 1, 5) c 1-го по 5-ый	type mas = array [1..20] of real; Function Sum(A: mas; i1,i2: byte): real; Var k: byte; Begin If i1=i2 Then Result:=A[i1] Else Result:=Sum(A, i1, i1+(i2-i1) div 2) + Sum(A, i1+(i2-i1) div 2 +1, i2) end; Вызов S:=Sum(A, 1, 5)
Линейная рекурсия	Каскадная рекурсия
Для 5-ми элементов: Глубина рекурсии = 5 Объем рекурсии = 4 Для 8-ми элементов: Глубина рекурсии = 8 Объем рекурсии = 7 Рост дерева в глубину	Для 8-ми элементов: Глубина рекурсии = 4 Объем рекурсии = 14 = 8+4+2 Рост дерева в ширину

Для сокращения количества параметров – в частности, чтобы не передавать массив, можно сделать внешнюю процедуру со всеми параметрами и убрать «лишние» параметры у самой рекурсивной внутренней процедуры – тем самым уменьшить объем требуемой памяти для стека вызовов:

Type mas = array of real; // для динамического массива

Function Sum(const A: mas; N: byte): real;

Function Recursia(i,N: byte): real; // A – глобальная для этой функции

Begin

If i=N Then Result:=A[i] Else Result:=A[i]+ Recursia(i+1, N)

end;

Begin

Sum:=Recursia(0, N-1); // нумерация с 0 в динамическом массиве!!!

end;

Вызов в программе Sum(A,n)

Пример №2. Метод бисекции с внешней вспомогательной процедурой, параметры которой для внутренней рекурсивной функции являются глобальными:

Procedure bisection(const a,b,e:double; f:func; out x:double; out it: word); // все параметры

var с:double; // тоже можно сделать глобальной для recurse

begin

x:=recurse(a, b, 50, it);

end;

Например, найдем корень (x*0,637) на отрезке [0,4; 0,7] с точностью 0,01

Дерево вызовов	Прямой ход	Стек вызовов	Обратный ход
	X=0,55 MaxIt-1	Result=?	0,634375
		A=0,4
		B=0,7
		MaxIt=50
		It=?	it=it+1=5
	X=0,625 MaxIt-1	Result=?	0,634375
		A=0,55
		B=0,7
		MaxIt=49
		It=?	it=it+1=4
	X=0,6625 MaxIt-1	Result=?	0,634375
		A=0,625
		B=0,7
		MaxIt=48
		It=?	it=it+1=3
	X=0,64375 MaxIt-1	Result=?	0,634375
		A=0,625
		B=0,6625
		MaxIt=47
		It=?	it=it+1=2
	|A-B|<2*E Result=0,634375 It=1	Result=0,634375
		A=0,625
		B=0,64375
		MaxIt=46
		It=1

Линейная рекурсия. Глубина рекурсии = 5. Объем рекурсии = 4

Вычисление новых границ отрезка происходит ДО очередного рекурсивного вызова – прямой ход.

Результат вычисляется/передается ПОСЛЕ рекурсивного вызова – обратный ход.
Пример №3. Найти N-ый член ряда Фибоначчи, если известно, что 0-ой и 1-ый его члены равны 1, а каждый следующий – сумма двух предыдущих:

N	0	1	2	3	4	5	6	7	8	9	…
Fib(N)	1	1	2 = 1+1	3 = 1+2	5 = 2+3	8 = 3+5	13 = 5+8	21 = 8+13	34	55	…

Каскадная рекурсия	Линейная рекурсия
Function fib(N: byte): cardinal; Begin If N<2 then Result:=1 Else Result:=fib(N-1)+fib(N-2); End; Вызов Res:=fib(5);	Procedure fib(n1,n2, i, N: byte; var res: cardinal); Begin If i>=N then Res:=n2 Else fib(n2, n1+n2, i+1, N, res); End; Вызов fib(1, 1, 1, 5, res);
	Глубина рекурсии = 5 Объем рекурсии = 4

	Линейная рекурсия	Каскадная рекурсия
Достоинства	Меньший объем рекурсии  быстрее	Меньшая глубина рекурсии  меньший расход памяти
Недостатки	Большая глубина рекурсии  больший расход памяти	Больший объем рекурсии  медленнее Возможны повторения одних и тех же вычислений (как в методе Фибоначчи)  неэффективный расход ресурсов (проблема решается использованием динамической базы: один раз вычислив fib(3), запоминаем это решение  увеличение расхода памяти)