Презентация по основам алгоритмизации на тему "Рекурсия в программировании"

Ленинск-Кузнецкий, 2023
ГПОУ «Ленинск-Кузнецкий политехнический техникум»
Преподаватель Щеглова Алена Александровна
Теоретическое занятие
для студентов II курса
Основы алгоритмизации
и программирования
Рекурсия

Рекурсия вокруг нас
Рекурсия - определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта
Объект, который является частью самого себя
Два зеркала поставлены друг против друга и объект между ними – множество изображений, каждое из которых содержит свое собственное - рекурсия

"Мастер и Маргарита"
Прием "книга в книге". Мастер пишет роман об Иешуа и Пилате, текст, которого сливается с текстом книги "Мастер и Маргарита"
Рекурсия в литературе

В романее Л. Толстого «Война и мир» рекурсия отражает прошлое в настоящем и будущем.
Рекурсия в литературе

Ночь, улица, фонарь, аптека.
Бессмысленный и тусклый свет.
Живи еще хоть четверть века – 
Все будет так. Исхода нет.
Умрешь – начнешь опять сначала,
И повторится все, как встарь:
Ночь, ледяная рябь канала,
Аптека, улица, фонарь.
А. Блок
Рекурсия вокруг нас

Рекурсия вокруг нас
Реки образуются из впадающих в них рек
Дерево состоит из веток
Ветка из маленьких веточек.
Каждая ветка повторяет дерево

Рекурсия в программировании
Рекурсия - это способ описания функций или процессов через самих себя
Рекурсия может быть:
Прямая рекурсия - вызов функцией самой себя делается в этой же функции
public int Factorial(int x) {
if (x == 0) { return 1; }
else { return x * Factorial(x - 1);
} }
2. Косвенная рекурсия - вызова функции из другой функции, которая сама вызывалась из данной функции

public int A(int n){
if (n == 0) n = A(n - 1) + B(n - 2);
else n=A(1);
return n;
}
public int B(int n){
if (n == 0) n = B(n - 1) + A(n - 2);
else n = B(1);
return n;
}

Пример рекурсивной процедуры
public int F(int n)
{
if (n > 0) n = F(n - 1);
return n;
}
Пока n >0 вызывается следующая процедура
Выводится n
Рекурсивные вызовы метода должны завершаться при достижении условия, иначе программа зависнет

Вычисление факториала
Рекурсия позволяет свести исходную задачу к одной или нескольким более простым того же типа
Чтобы определить рекурсию, нужно задать:
условие остановки рекурсии
рекуррентную формулу
Рекуррентная формула — формула вида 
𝒂 𝒏 =𝒇 𝒏, 𝒂 𝒏−𝟏 , 𝒂 𝒏−𝟐 ,…, 𝒂 𝒏−𝒑
выражающая каждый член последовательности  𝒂 𝒏  через p
предыдущих членов и номер члена последовательности n
Факториал натурального числа :


4! = 1 * 2 * 3 * 4 =24
5! = 1 * 2 * 3 * 4 * 5=120
0!=1
1!=1
Написать рекуррентную формулу


n! = (n-1!)* n
0!=1

Вычисление факториала
Факториал натурального числа :


4! = 1 * 2 * 3 * 4 =24
5! = 1 * 2 * 3 * 4 * 5=120
0!=1
1!=1
Определить условие:
n! = (n-1!)*n условие:
0!=1 условие:

Напишите формулу:

n! = (n-1!)*n
0!=1
n>=1
n=0

Вычисление факториала
public int F(int n)
{ if (n >= 1)
{ return n*F(n -1); }
else return 1;}
Если вводимое число не равно 0, то данное число умножается на результат этой же функции, в которую в качестве параметра передается число n-1
Повторяется, пока не дойдет до того момента, когда значение параметра не будет равно единице
Вызов
static void Main(string[] args)
{ int s= new Program().F(5);
Console.WriteLine(s); }

Числа Фибоначчи
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …
Как изменяются числа? Определите шаг или закономерность изменения
Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, начиная с третьей цифры:
1+2=3, 2+3=5, 3+5=8, …
Напишите формулу для вывода этих чисел и условие
Пусть
x0 – это число 0
x1 – это число 1
x2 – это число 1 = 0+1 = x0+x1
x3 – это число 2 = 1+1 = x1+x2
x4 – это число 3 = 1+2 = x2+x3
x5 – это число 5 = 2+3 = x3+x4
….






Какая закономерность происходит в формулах


Формула
0, если n=0
1, если n=1
(n - 2)+(n - 1), если n ≥ 2

Рекурсивная постановка данной задачи:



Написать рекурсивную функцию, которая выводит последовательность чисел

Ф(n) =
n, если n = 0 или n = 1

Ф(n – 1) + Ф(n – 2), при n > 2
Числа Фибоначчи
0, если n=0
1, если n=1
(n-2)+(n-1), если n>2
public int RF(int n) {
if ((n == 0) || (n == 1)) return n;
return RF(n - 1) + RF(n - 2); }
Вызов
static void Main(string[] args)
{ int s0 = new Program().RF(0); int s1 = new Program().RF(1);
int s2 = new Program().RF(2); int s3 = new Program().RF(3);
int s4 = new Program().RF(4); int s5 = new Program().RF(5);
Console.WriteLine($"{s0}, {s1}, {s2}, {s3}, {s4}, {s5}"); }

Разработать рекурсивную функцию вычисления суммы ряда
S = 6 + 12+ 18 + 24+ …

Задание