СОДЕРЖАНИЕ

Введение

1. Рекурсивные алгоритмы

1.1. Рекурсивные определения

1.2. Рекурсивные подпрограммы

1.3. Косвенная рекурсия и опережающее описание

1.4. Рекурсивные структуры

1.4.1. Список

1.4.2. Набор

1.4.3. Дерево

1.5. Примеры решения задач с помощью рекурсии

1.5.1. “Ханойская башня”.

1.5.2. Двумерное множество Кантора

1.5.3. “Индийский алгоритм” возведения в степень

1.5.4. Вычисление факториала

1.5.5. Числа Фибоначчи

2. Представление данных в памяти ЭВМ

3. Разработка программы

3.1. Программа роста банковского вклада по месяцам

3.2. Блок-схема к программе

Вывод

Список использованных источников

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ, СИМВОЛЫ, НЕСТАНДАРТНЫЕ СОКРАЩЕНИЯ

ПСЗ – полная скобочная запись

НОД – наибольший общий делитель

GCD – Greatest Common Divisor (англ. наибольший общий делитель)

ПОЛИЗ – польская инверсная запись

ВВЕДЕНИЕ

Система программирования Турбо Паскаль представляет собой единство двух в известной степени самостоятельных начал: компилятора с языка программирования Паскаль (язык назван в честь выдающегося французского математика и философа Блеза Паскаля (1623-1662)) и некоторой инструментальной программной оболочки, способствующей повышению эффективности создания программ.

Паскаль – замечательный язык программирования, который относительно прост в изучении, довольно ясен и логичен и, будучи первым изучаемым языком программирования, приучает к хорошему стилю. Паскаль воспитывает дисциплину структурного программирования и программирования вообще лучше, чем другие языки программирования, такие, как, например, БЕЙСИК.

Паскаль – гибкий и развитый в отношении типов данных язык. Привлекательны его рекурсивные возможности, а также поддержка технологии объектно-ориентированного программирования.

Изучение программирования на языке Паскаль может дать хороший старт в огромный и увлекательный мир программирования. Обучение языку программирования проходит намного более эффективно с изучением примеров.

Чаще всего (процедурное) программирование использует итерации, то есть циклы; однако рекурсия – описание объекта или вычисления в терминах самого себя – является более простым математическим понятием, а также мощной, но мало используемой техникой программирования.

Некоторые программисты считают (и не без оснований), что рекурсия – это сердце и душа языка Паскаль. В этой работе мы рассмотрим применение рекурсии в программах на Паскале. Здесь рассматриваются примеры рекурсивных алгоритмов и программирование комбинаторных вычислений.

Ко всему прочему мы научимся представлять данные в памяти ЭВМ и разрабатывать программы в среде Турбо Паскаль.

1. РЕКУРСИВНЫЕ АЛГОРИТМЫ

Я уверен, что всеобщее признание рекурсивных методов в конце концов

будет иметь такое же значительное влияние на программирование,

как и введение подпрограмм.

Д. Баррон

1.1. Рекурсивные определения

Часто говорят, что рекурсивные определения – это когда что-то определяется с его же помощью. Фраза эта не совсем точная, а вернее, совсем неточная. Каждое определение задаёт что-то, и этим чем-то являются, как правило, объекты, образующие некоторое множество. Определение называется рекурсивным, если оно задаёт элементы множества с помощью других элементов этого же множества. Объекты, заданные рекурсивным определением, также называются рекурсивными. И наконец, рекурсия – это использование рекурсивных определений.

Пример 1

Значение функции факториал задаются выражением: 0!=1, n=n*(n-1)!. Они образуют множество {1,2,6,…}: 0!=1, 1=1*0!, 2=2*1!, 6=3*2! и т.д. Все его элементы, кроме первого, определяются рекурсивно.

Как видим, функция факториал задаётся рекуррентным соотношением порядка 1 и начальным отрезком 0!=1. Вообще, любое рекуррентное соотношение порядка k вместе с заданием первых k элементов последовательности является примером рекурсивного определения.

Пример 2

Арифметические выражения с константами и знаком операции “+” в полной скобочной записи (ПСЗ) задаются таким определением:

1) константа является выражением в ПСЗ;

2) если Е и F являются выражениями в ПСЗ, то (Е)+(F) также является выражением в ПСЗ.

Такими выражениями являются, например, 1, 2, (1)+(2), ((1)+(2))+(1). Все они, кроме констант 1 и 2, определяются рекурсивно.

Объекты, определённые в примерах 1 и 2, т.е. значения функции факториал и скобочные записи выражений, являются рекурсивными.

В рекурсивном определении не должно быть “заколдованного круга”, когда объект определяется с помощью себя самого или с помощью других, но заданных через него же.

Пример 3

Изменим определение функции факториал на следующее: n!=n*(n-1)! При n>0, 0!=1!. Сначала значение функции от 1 выражается через её же значение от 0, которое, в свою очередь, – через значение от 1. По такому определению так и не узнать, чему же равно 1!.

Пример 4

“У попа была собака, поп её любил, она съела кусок мяса, поп её убил, в землю закопал и на камне написал, что у попа…” и т.д. Эта печальная история не имеет конца, и нельзя сказать, что же именно поп написал на камне.

Пример 5

“Где ты деньги берёшь?” – “В тумбочке”. – “А там они откуда?” – “Жена кладёт”. – “А у неё откуда?” – “Я даю”. – “А где ты берёшь?” – “В тумбочке…”

В этом старом анекдоте не называется настоящий источник хранения денег. Если через А, В, С обозначить мужа, его жену и тумбочку, то перемещение денег изображается так: АßСßВßАß…и настоящий источник денег остаётся неизвестным.

Чтобы подобная “дурная бесконечность” не возникала в рекурсивном определении, должны выполняться следующие условия:

1) множество определяемых объектов является частично упорядоченным;

2) каждая убывающая по этому упорядочению последовательность элементов заканчивается некоторым минимальным элементом;

3) минимальные элементы определяются нерекурсивно;

4) неминимальные элементы определяются с помощью элементов, которые меньше их по этому упорядочению.

Нетрудно прийти к убеждению, что определения из примеров 1 и 2 удовлетворяют этим условиям, а из примеров 3–5 – нет.

Для тех, кому не знакомы термины “частично упорядоченное множество” и “минимальный элемент”, дадим небольшое пояснение.

Любое множество пар, составленных из элементов некоторого множества, называется отношением на этом множестве. Например, множество пар {(1,1), (1,2), (2,1)} – на множестве {1,2}.

Отношение называется отношением частичного порядка, если оно имеет такие свойства:

1. Для каждого элемента a множества в отношении есть пара (a, a).

2. Если в отношении есть пара (a, b) с различными элементами a и b, то пары (b, a) там нет. При этом мы говорим, что а меньше b. Во множестве могут быть и несравнимые элементы, которые друг с другом пары не образуют.

3. Если а меньше b, а b меньше c, то a меньше c. Впрочем, элементов a, b, c таких, что a меньше b, а b меньше с, во множестве может и не быть – при выполнении свойств (1) и (2) отношение будет отношением частичного порядка.