ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 30.11.2023
Просмотров: 42
Скачиваний: 2
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
СОДЕРЖАНИЕ
Рекурсия в широком смысле – это определение объекта посредством ссылки на себя.
Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.
В арифметической прогрессии найдите an, если известны а1 = -2.5, d=0.4,
не используя формулу n-го члена прогрессии.
По определению арифметической прогрессии, an=an-1+d, при этом
an-1=an-2+d, an-2=an-3+d,... a2=a1+d.
float arifm (int n, float a, float d)
if (n<1) return 0; // для неположительных номеров
if (n= =1) return a; // базовый случай: n=1
return arifm(n-1,a,d)+d; // общий случай
В программировании выделяют прямую и косвенную рекурсию.
Для хn можно определить рекурсивное выражение Rekursiooniline avaldis astelise funktsiooni xn on
Factorial (n) = 1 * 2 * 3 * …* (n-2) * (n-1) * n
Factorial (4) = 1 * 2 * 3 * 4 = 24
Factorial (6) = 1 * 2 * 3 * 4 * 5 * 6 = 720
Factorial (1) = 1 * Factorial (0) = 1
| 2 | ||
| 3 | ||
| 1 | 4 |
| 2 | ||
| 1 | 3 | 4 |
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
А В С
Пример с числами. Näidis arvudega.
Вычисление факториала числа
Factorial (n) = 1 * 2 * 3 * …* (n-2) * (n-1) * n
Factorial (4) = 1 * 2 * 3 * 4 = 24
Factorial (6) = 1 * 2 * 3 * 4 * 5 * 6 = 720
Factorial (1) = 1 * Factorial (0) = 1
Factorial (0) = 1
long Factorial (long n) //итерационная форма факториала
{ int prod =1, i;
//kui n=0 return prod=1, vastasel juhul arvutada prod=1*2*3*…*n
if (n>0) for (i=1; i<=n; i++) prod *= i; //korrutamine omistamisega
return prod;}
n!=
1, n=0 //условие останова Stopp
n * (n-1)!, n>1 //шаг рекурсии
//рекурсивная форма факториала
long Factorial (long n)
{ //kui n=0 stopp
if (n==0) return 1;
else //шаг рекурсии
return n * Factorial (n-1);}
Схема вызовов функции Factorial.
Параметр действие tehe возврат
0 вычислить 0!=1 1
Параметр действие tehe возврат
1 вычислить 1 * Factorial(0) 1
Параметр действие tehe возврат
2 вычислить 2 * Factorial(1) 2
Параметр действие tehe возврат
3 вычислить 3 * Factorial(2) 6
Параметр действие tehe возврат
4 вычислить 4 * Factorial(3) 24
Главная программа Pea programm
//Пример использования функции Factorial. long Factorial (long n) { if (n==0) return 1; else return n*Factorial (n-1); } void main(void) { int i, n; cin>>n; cout<
Ключевые термины
База рекурсии – это тривиальный случай, при котором решение задачи очевидно, то есть не требуется обращение функции к себе.
Декомпозиция – это выражение общего случая через более простые подзадачи с измененными параметрами.
Косвенная (взаимная) рекурсия – это последовательность взаимных вызовов нескольких функций, организованная в виде циклического замыкания на тело первоначальной функции, но с иным набором параметров.
Параметризация – это выделение из постановки задачи параметров, которые используются для описания условия задачи и решения.
Прямая рекурсия – это непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных.
Рекурсивная триада – это этапы решения задач рекурсивным методом.
Рекурсивная функция – это функция, которая в своем теле содержит обращение к самой себе с измененным набором параметров.
Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.
Рекурсивный стек – это область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении.
Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.
Рекурсия в широком смысле – это определение объекта посредством ссылки на себя.
Краткие итоги
- Свойством рекурсивности характеризуются объекты окружающего мира, обладающие самоподобием.
- Рекурсия в широком смысле характеризуется определением объекта посредством ссылки на себя.
- Рекурсивные функции содержат в своем теле обращение к самим себе с измененным набором параметров. При этом обращение к себе может быть организовано через цепочку взаимных обращений функций.
- Решение задач рекурсивными способами проводится посредством разработки рекурсивной триады.
5. Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче.
6. Область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении, образует рекурсивный стек.
7. Рекурсивные методы решения задач нашли широкое применение в процедурном программировании.
Контрольные вопросы
- Приведите примеры рекурсивных объектов и явлений. Обоснуйте проявление рекурсивности.
- Почему при правильной организации рекурсивные вызовы не зацикливаются?
- Почему не отождествляются совпадающие идентификаторы при многократных рекурсивных вызовах?
- Почему рекурсивные обращения завершаются в порядке, обратном вызовам этих обращений?
- Чем ограничено при выполнении программы количество рекурсивных вызовов?
- Какой из методов в программировании является более эффективным – рекурсивный или итерационный?
Задание
Числа Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …….
N
N-2
N-1
AN = AN-1 + AN-2
Kirjutage programmi, mis väljastab ekraanile Fibonacci arvud. N sisestatakse klaviatuurilt.
Ключевые термины
База рекурсии – это тривиальный случай, при котором решение задачи очевидно, то есть не требуется обращение функции к себе.
Декомпозиция – это выражение общего случая через более простые подзадачи с измененными параметрами.
Косвенная (взаимная) рекурсия – это последовательность взаимных вызовов нескольких функций, организованная в виде циклического замыкания на тело первоначальной функции, но с иным набором параметров.
Параметризация – это выделение из постановки задачи параметров, которые используются для описания условия задачи и решения.
Прямая рекурсия – это непосредственное обращение рекурсивной функции к себе, но с иным набором входных данных.
Рекурсивная триада – это этапы решения задач рекурсивным методом.
Рекурсивная функция – это функция, которая в своем теле содержит обращение к самой себе с измененным набором параметров.
Рекурсивный алгоритм – это алгоритм, в определении которого содержится прямой или косвенный вызов этого же алгоритма.
Рекурсивный стек – это область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении.
Рекурсия в программировании – это пошаговое разбиение задачи на подзадачи, подобные исходной.
Рекурсия в широком смысле – это определение объекта посредством ссылки на себя.
Краткие итоги
- Свойством рекурсивности характеризуются объекты окружающего мира, обладающие самоподобием.
- Рекурсия в широком смысле характеризуется определением объекта посредством ссылки на себя.
- Рекурсивные функции содержат в своем теле обращение к самим себе с измененным набором параметров. При этом обращение к себе может быть организовано через цепочку взаимных обращений функций.
- Решение задач рекурсивными способами проводится посредством разработки рекурсивной триады.
5. Целесообразность применения рекурсии в программировании обусловлена спецификой задач, в постановке которых явно или опосредовано указывается на возможность сведения задачи к подзадачам, аналогичным самой задаче.
6. Область памяти, предназначенная для хранения всех промежуточных значений локальных переменных при каждом следующем рекурсивном обращении, образует рекурсивный стек.
7. Рекурсивные методы решения задач нашли широкое применение в процедурном программировании.
Контрольные вопросы
- Приведите примеры рекурсивных объектов и явлений. Обоснуйте проявление рекурсивности.
- Почему при правильной организации рекурсивные вызовы не зацикливаются?
- Почему не отождествляются совпадающие идентификаторы при многократных рекурсивных вызовах?
- Почему рекурсивные обращения завершаются в порядке, обратном вызовам этих обращений?
- Чем ограничено при выполнении программы количество рекурсивных вызовов?
- Какой из методов в программировании является более эффективным – рекурсивный или итерационный?
Задание
Числа Фибоначчи:
1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …….
N
N-2
N-1
AN = AN-1 + AN-2
Kirjutage programmi, mis väljastab ekraanile Fibonacci arvud. N sisestatakse klaviatuurilt.