Основы алгоритмизации и программирования Лекция 2. А.Ф.ОСЬКИН ПГУ, Полоцк

1. Понятие рекурсии 2. Примеры рекурсии 3. Общая схема рекурсии 4. Рекурсивная триада 5. Примеры рекурсивных алгоритмов и программ План

Рекурсия

Примеры рекурсии

Программа «У попа была собака…»

Общая схема рекурсии рекурсивный вызов If exit известный частный случай (база рекурсии) Else;

Модифицированная программа «У попа была собака…»

Рекурсивная триада

Пример 1. Ханойские башни

Пример 2. Поиск максимального элемента в массиве Задан одномерный массив, состоящий из n целых чисел. Написать рекурсивную функцию возвращающую значение максимального элемента.

Пример 3. Поиск максимального элемента в массиве

Пример 4. Вычисление суммы элементов массива Задан одномерный массив, состоящий из n целых чисел. Написать рекурсивную функцию возвращающую сумму элементов массива.

Пример 4. Вычисление суммы элементов массива

Ключевые термины

Задачи для самостоятельного решения 1. Задан одномерный массив, состоящий из n целых чисел. Написать рекурсивную функцию возвращающую наибольший элемент, расположенный на сегменте массива от p-того до q-того элемента. 2. Написать рекурсивную функцию возвращающую числа Стирлинга. Числа Стирлинга S(n, k) определены для 00; иначе S(n, k)=k*(n-1,k)+S(n-1,k-1)

Спасибо за внимание!