- •Предисловие
- •Основные навыки и умения
- •Логическая культура: знание логики, логическая интуиция.
- •Языковые знания и умения.
- •Поисковые знания и умения.
- •Алгоритмические навыки и умения.
- •Общие подходы к построению алгоритмов
- •Тестирование и сопровождение программ
- •Обязательный минимум содержания среднего (полного) общего образования
- •Технология обработки текстовой информации
- •Введение в информатику
- •Системы счисления
- •Перевод из десятичной системы счисления
- •Перевод в десятичную систему счисления
- •Перевод чисел из двоичной системы счисления в восьмеричную, шестнадцатеричную системы и обратно
- •Выполнение арифметических операций в позиционных системах счисления
- •Элементы математической логики
- •Логические законы
- •Алгоритм и его свойства
- •Исполнители. Компьютер - универсальный исполнитель
- •Работа компьютера
- •Turbo pascal - исполнитель паскаль-программ
- •Конструкции Паскаля
- •Типы данных
- •Целый тип данных
- •Вещественный тип данных
- •Символьный тип данных
- •Логический тип данных
- •Выражения
- •Операторы ввода-вывода
- •Оператор присваивания
- •Общий вид программы на Паскале
- •Условный оператор
- •If логическое_выражение then оператор1 else оператор2;
- •If логическое_выражение then оператор1;
- •Операторы цикла
- •Построение линейных алгоритмов
- •Построение ветвящихся алгоритмов
- •Построенние циклических алгоритмов
- •Нахождение суммы
- •Вложенные циклы
- •Переборный метод решения задач
- •Численные методы
- •Метод итераций
- •Метод половинного деления
- •Вычисление определенного интеграла методом трапеций
- •Случайные числа
- •Метод Монте-Карло (метод статистических испытаний)
- •Массивы Одномерные массивы
- •Перебор элементов массива
- •Перебор подмассивов
- •Классы задач по обработке массивов
- •Задачи первого класса
- •Задачи второго класса
- •Задачи третьего класса
- •Задачи четвертого класса
- •Сортировка массивов
- •Сортировка вставками
- •Сортировка пузырьком (обменом)
- •Сортировка выбором
- •Сортировка фон Неймана (слиянием)
- •Двумерные массивы
- •Обработка строк
- •Процедуры и функции
- •Рекурсия
- •Работа с графикой
- •Классы программного обеспечения
- •Компиляция и интерпретация
- •Текстовый редактор
- •Электронные таблицы
- •Системы управления базами данных (субд)
- •Пример решения экзаменационного билета
- •Контрольные работы
- •Контрольная работа №1
- •Контрольная работа № 2
- •Контрольная работа № 3
- •Контрольная работа № 4
- •Контрольная работа № 5
- •Библиографический список
Рекурсия
В Паскале есть возможность обращения процедуры или функции к самой себе. При этом получается интереснейший эффект: циклическую часть программы можно представить без операторов цикла.
Способ обращения процедуры или функции к самой себе называется рекурсией. Различают прямую рекурсию, когда процедура или функция содержит явное обращение к себе самой, и косвенную, когда процедура или функция вызывает процедуру или функцию , а та в свою очередь вызывает процедуру или функцию .
Понятно, что без конца такие вызовы продолжаться не могут, т.к. в противном случае процесс вычислений будет бесконечным. Поэтому при построении рекурсивного алгоритма предусматриваются случаи, когда результат вычисляется явно (непосредственно) без самовызова.
Таким образом, любая рекурсия обязательно должна содержать два условия:
1) условие окончания рекурсии (опорное условие рекурсии или “якорь”), в котором задается какое-то фиксированное значение, заведомо достигаемое в ходе рекурсивного вычисления и позволяющее организовать своевременную остановку вычислительного процесса. Выполнение этого условия не должно повлечь за собой нового рекурсивного вызова.
2) вычисление значения с помощью самовызова функции (рекурсивный вызов).
Задача 1. Напишите итерационную и рекурсивную функции вычисления факториала.
Решение. Итерационное вычисление факториала осуществляется следующим образом: n! = 1·2·3·...·n, что осуществляется путем умножения передыдущего значения факториала на i.
function factorial (n: integer): real;
var f: real;
i: integer;
begin
if (n = 0) or (n = 1) then factorial := 1
else
begin f := 1;
for i := 2 to n do
f := f * i;
factorial := f
end;
end;
Рекурсивное определение факториала:
В первой строке определения явно указано, как вычислить факториал, если аргумент равен нулю или единице. В любом другом случае для вычисления n! необходимо вычислить предыдущее значение (n-1)! и умножить его на n. Уменьшающееся значение гарантирует, что в конце концов возникнет необходимость найти 1! или 0!, которые вычисляются непосредственно.
function factorial (n: integer): real;
{рекурсивное вычисление факториала}
var f: real;
i: integer;
begin
if (n = 0) or (n = 1) then factorial := 1
else factorial := factorial (n - 1) * n;
end;
Чтобы понять, как будет выполняться эта программа, вспомним, что на время выполнения вспомогательного алгоритма основной алгоритм приостанавливается. При вызове новой копии рекурсивного алгоритма вновь выделяется место для всех переменных, объявляемых в нем, причем переменные других копий будут недоступны. При удалении копии рекурсивного алгоритма из памяти удаляются и все его переменные.
Активизируется предыдущая копия рекурсивного алгоритма, становятся доступными ее переменные. Пусть необходимо вычислить 4! Основной алгоритм: вводится n=4, вызов factоrial(4). Основной алгоритм приостанавливается, вызывается и работает factorial(4): 4<>1 и 4 <> 0, поэтому factorial:=factorial(3)*4. Работа функции приостанавливается, вызывается и работает factorial(3): 3<>1 и 3<>0, поэтому factorial:=factorial(2)*3. Заметьте, что в данный момент в памяти компьютера две копии функции factorial. Вызывается и работает factorial(2): 2<>1 и 2<>0, поэтому factorial:=factorial(1)*2. В памяти компьютера уже три копии функции factorial и вызывается четвертая. Вызывается и работает factorial(1): 1=1, поэтому factorial(1)=1.
Работа этой функции завершена, продолжает работу factorial(2). factorial(2):=factorial(1)*2 =1*2=2. Работа этой функции также завершена и продолжает работу функция factorial(3). factorial(3):=factorial(2)*3=2*3=6. Завершается работа и этой функции и продолжает работу функция factorial(4). factorial (4):=factorial(3)*4=6*4=24. Значение функции при n=4 равно 24.
Рекурсивная форма организации алгоритма обычно выглядит изящнее итерационной и дает более компактный текст программы, но при выполнении, как правило, медленнее и может вызвать переполнение стека (при каждом входе в рекурсивную процедуру или функцию ее локальные переменные размещаются в особым образом организованной области памяти - стек).
Упражнение. Напишите рекурсивную функцию вычисления n-ого числа Фибоначчи.