Рекурсия в программировании

ГПОУ «Ленинск-Кузнецкий политехнический техникум»

Основы алгоритмизации

и программирования

Рекурсия

Преподаватель Щеглова Алена Александровна

Теоретическое занятие

для студентов II курса

Ленинск-Кузнецкий, 2023

Рекурсия вокруг нас

Рекурсия - определение, описание, изображение какого-либо объекта или процесса внутри самого этого объекта

Объект, который является частью самого себя

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

Рекурсия в литературе

"Мастер и Маргарита"

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

Рекурсия в литературе

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

Рекурсия вокруг нас

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

А. Блок

Рекурсия вокруг нас

Реки образуются из впадающих в них рек

Дерево состоит из веток

Ветка из маленьких веточек.

Каждая ветка повторяет дерево

Рекурсия в программировании

Рекурсия - это способ описания функций или процессов через самих себя

Рекурсия может быть:

• Прямая рекурсия - вызов функцией самой себя делается в этой же функции

public int Factorial (int x) {

if (x == 0) { return 1; }

else { return x * Factorial (x - 1);

} }

2. Косвенная рекурсия - вызова функции из другой функции, которая сама вызывалась из данной функции

public int A (int n){

public int B (int n){

if (n == 0) n = A (n - 1) + B (n - 2);

if (n == 0) n = B (n - 1) + A (n - 2);

else n= A (1);

else n = B (1);

return n;

return n;

}

}

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

Пример рекурсивной процедуры

Пока n 0 вызывается следующая процедура

public int F(int n)

{

if (n 0) n = F(n - 1);

return n;

}

Выводится 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

Написать рекуррентную формулу

=1 n=0 " width="640"

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

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=1

n=0

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

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

public int F(int n)

{ if (n = 1)

{ return n*F(n -1); }

else return 1;}

Вызов

static void Main(string[] args)

{ int s= new Program().F(5);

Console.WriteLine(s); }

• Если вводимое число не равно 0, то данное число умножается на результат этой же функции, в которую в качестве параметра передается число n-1
• Повторяется, пока не дойдет до того момента, когда значение параметра не будет равно единице

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Как изменяются числа? Определите шаг или закономерность изменения

Каждый элемент ряда Фибоначчи является суммой двух предшествующих элементов, начиная с третьей цифры:

1+2=3, 2+3=5, 3+5=8, …

Напишите формулу для вывода этих чисел и условие

Пусть

x 0 – это число 0

x 1 – это число 1

x 2 – это число 1 = 0+1 = x 0 + x 1

x 3 – это число 2 = 1+1 = x 1 + x 2

x 4 – это число 3 = 1+2 = x 2 + x 3

x 5 – это число 5 = 2+3 = x 3 + x 4

… .

Формула

0, если n=0

1, если n=1

(n - 2)+(n - 1), если n ≥ 2

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

2 (n-2)+(n-1), если n2 Ф(n) = 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}"); } " width="640"

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

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

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

0, если n=0

n, если n = 0 или n = 1

1, если n=1

Ф(n – 1) + Ф(n – 2), при n 2

(n-2)+(n-1), если n2

Ф(n) =

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+ …