Технологии Программирования. 5 лекция
.pdfТема 3: Рекурсия
(продолжение)
2. Рекурсия изнутри. Стек
Самовызов подпрограммы ничем не отличается от вызова другой подпрограммы.
Что происходит, если одна подпрограмма
вызывает другую?
•В памяти компьютера размещаются
параметры, передаваемые подпрограмме.
•В другом месте памяти сохраняются внутренние переменные (локальные) вызывающей подпрограммы.
•Запоминается адрес возврата в вызывающую подпрограмму.
•Управление передается вызываемой
подпрограмме.
unsinged long fact (unsinged short N)
{ |
if (N==1) return 1; |
// a |
|
else |
|
} |
return N * fact (N - 1); |
// b |
|
|
В данной функции переменная N будет отведена (а
после и уничтожена) МНОГО РАЗ.
Так что переменная fact::N должна получить еще и НОМЕР вызова функции:
fact::N[уровень_вызова]
И на каждом новом уровне новая переменная скрывает все предыдущие.
Так для fact(4) будет |
|
|
| fact::N [ 0-ой раз ] |
есть 4 |
| |
| fact::N [ 1-ый раз ] |
есть 3 |
| |
| fact::N [ 2-ой раз ] |
есть 2 |
| |
| fact::N [ 3-ий раз ] |
есть 1 |
| |
__________________________________
Затем пойдут возвраты из функций:
| /* b */ return 4 * 6 |
= 24 |
| |
| /* b */ return 3 * 2 |
= 6 |
| |
| /* b */ return 2 * 1 |
= 2 |
| |
| /* a */ return 1; |
|
| |
Такая конструкция называется СТЕК (stack).
•Количество обращений подпрограммы и самой себе называется глубиной рекурсии.
Функция сложности рекурсивного алгоритма - выполняется за время порядка
O(log(N)).
•При использовании данных целого типа (2
байта), переполнение наступает для 8!,
поскольку 8! = 40 320, что больше, чем
наибольшее целое число 32 767.
•Для того чтобы программа могла вычислять
приближенные значения факториала
больших чисел, можно изменить функцию,
используя вместо целых чисел значения типа double. Тогда максимальное число, которое
сможет вычислить алгоритм, будет равно
170! = 7,257E+306.
Рекурсия изнутри.
5!
N=5 =fact(5)
n’ =5 (>0)
= fact(4) *5
n’’ =4
= fact(3) |
24 |
n’’’ =3
= fact(2)
n
= |
|
2 |
n’’’’’’ =0 (= 0) fact=1
В нашей рекурсивной функции переменная fact::N
ведет себя именно как стек (этот ящик-стек имеет имя N) - она имеет ОДНО имя, но разные значения в разных случаях.
Переменные, которые АВТОМАТИЧЕСКИ ведут себя как стек, встречаются только в (рекурсивных)
функциях.
Стек - это часто встречающаяся в программировании конструкция.
Если подобное поведение нужно программисту, он должен промоделировать стек при помощи
массива: см. далее
3. Рекурсивная функция «Дерево»
Можно представить дерево на рис. в виде «ствола», на котором находятся
два дерева меньших размеров. Тогда рекурсивная процедура для рисования деревьев:
Void DrawTree() { // в текстовом режиме
• Нарисовать «ствол» ( символ | ).
•Нарисовать дерево меньшего размера, повернутое на -45o. (\)
•Нарисовать дерево меньшего
размера, повернутое на 45o (/)
}
Хотя рекурсия и может упростить понимание некоторых проблем,
люди обычно не мыслят рекурсивно.
Они обычно стремятся разбить сложные задачи на задачи меньшего
объема, которые могут быть выполнены последовательно одна за другой
до полного завершения.
Например, чтобы покрасить изгородь, можно начать с ее левого края и продолжать двигаться вправо до завершения. Вероятно, во время выполнения подобной задачи вы не думаете о возможности рекурсивной окраски — вначале левой половины изгороди, а затем рекурсивно — правой.
Для того чтобы думать рекурсивно, нужно разбить задачу на подзадачи, которые затем можно разбить на подзадачи меньшего размера.
В какой-то момент подзадачи становятся настолько простыми, что могут быть выполнены непосредственно.
Когда завершится выполнение подзадач, большие подзадачи, которые из них составлены, также будут выполнены.
Исходная задача окажется выполнена, когда будут все выполнены
образующие ее подзадачи.