1 Рекурсивное программирование Рекурсия – это метод, сводящий общую задачу к некоторым задачам более узкого, простого типа Рекурсивный алгоритм – это алгоритм, который в процессе своей работы обращается сам к себе. Суть заключается в том, что при каждом вызове создается новая копия со своими переменными, но как только она заканчивает свою работу, то память, занятая этими локальными переменными, освобождается, а полученные результаты передаются в точку вызова. Рекурсивное программирование Рекурсивное программирование Recursio (лат.) - возврвщение

2 Рекурсия … послушать… «У попа была собака, Он ее любил. … посмотреть… встаньте между двумя зеркалами и смотрите… (не детали гардероба, нет. Отражение себя, там …) нарисовать… нарисуйте себя, где на полотне вы рисуете себя, где на полотне… Ее можно: Это примеры «бесконечной» рекурсии…

3 Задачи с рекурсивной формулировкой Пример: вычисление факториала натурального числа N! = 1, при N = 1 N * (N – 1)!, при N > 1 Function factorial(n: integer): longint; Begin If n = 1 then factorial:=1 else factorial:= n * factorial (n – 1); End; При использовании рекурсии необходимо обеспечить выход из подпрограммы в нужный момент, т.к. алгоритм должен быть конечным (одно из свойств).

4 Найдем 5! Первый вызов этой функции будет из основной программы. Например, α:= factorial(5) Function factorial Begin factorial:= 5 * factorial(4); End; Function factorial Begin factorial:= 4* factorial(3); End; Function factorial Begin factorial:= 2* factorial(1); End; Function factorial Begin factorial:= 3* factorial(2); End; Function factorial Begin factorial:= 1; End; 3 вызов (n=3) 2 вызов (n=4) 4 вызов (n=2) 5 вызов (n=1) 1 вызов (n=5) 2 *1 5 *24 4 *6 3 *2 factorial(5) = 120 α:= 120

5 Задание 1.Напишите рекурсивную программу определения суммы первых n натуральных чисел: S n = S n-1 + n; S 1 = Составить рекурсивную программу ввода с клавиатуры последовательность чисел (окончание ввода - 0) и вывода ее на экран в обратном порядке.

6 Пример: перевод натурального числа из десятичной системы счисления в двоичную = Procedure Rec(n: integer); begin If n > 1 then Rec(n Div 2); Write(n Mod 2); End;

7 Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; 1 вызов ( n = 39 ) Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Rec(n Div 2); Write(n Mod 2); End; Procedure Rec begin Write(n Mod 2); End; 2 вызов ( n = 19 ) 3 вызов ( n = 9 ) 4 вызов ( n = 4 ) 6 вызов ( n = 1 ) 5 вызов ( n = 2 )

8 Задание 1.Написать процедуру перевода числа из десятичной системы в N - ю, при условии, что 2 N 16 и его значение вводится с клавиатуры. Каким будет условие завершения входа в рекурсию?

9 Напишите программу: Найти первые N чисел Фибоначчи. Каждое число равно сумме двух предыдущих чисел при условии, что первые два равны 1 (1, 1, 2, 3, 5, 8, 13, 21, …). Рекурсивная постановка данной задачи: Ф(n) = 1, если n = 1 или n = 2; Ф(n – 1) + Ф(n – 2), при n > 2

10 Program chisla_Fibonachi; var i,n:integer; function fib(nf:integer):longint; begin if (nf=1) or (nf=2) then fib:=1 else fib:=fib(nf-1)+fib(nf-2); end; begin readln(n); for i:=1 to n do writeln(fib(i)); end. Данная программа раскрывает недостатки рекурсии: с увеличением n глубина рекурсии многократно (во сколько?) увеличивается и выполняемая программа потребует много памяти, что может привести к переполнению стека. Если при решении есть выбор между итерацией и рекурсией, то предпочтительным выбором является итерация.итерация

11 Итерация -повторное выполнение некоторых действий до тех пор, пока не будет удовлетворяться некоторое условие. Большинство алгоритмов можно реализовать двумя способами: function fibon(nf:integer):longint; begin f1:=1; f2:=1; for i:=3 to n do begin f:=f1+f2; f1:=f2; f2:=f; end; fibon:=f; end; function fib(nf:integer):longint; begin if (nf=1) or (nf=2) then fib:=1 else fib:=fib(nf-1)+fib(nf-2); end; Итерацией: Рекурсией:

12 Выводит цифры целого положительного числа в обратном порядке Program Perevertish; Var n: longint; Procedure reverse(n: longint); begin write (n mod 10); if n div then reverse (n div 10) end; Begin writeln(Введите натуральное число

13 Число-полиндром - число, которое имеет тот же вид при прочтении его справа налево. Например: 121, , 99 и т.п.

14 Решение задач 1.Даны первый член и разность арифметической прогрессии. Написать рекурсивную функцию для нахождения: a) n-го члена прогрессии; б) суммы n первых членов арифметической прогрессии. 2. Даны первый член и знаменатель геометрической прогрессии. Написать рекурсивную функцию для нахождения: a) ее n-го члена; б) суммы n первых членов прогрессии.

15 3. Написать рекурсивную функцию для вычисления: а) суммы цифр натурального числа; б) количества цифр натурального числа. 4. Написать рекурсивную процедуру для вывода на экран цифр натурального числа в обратном порядке. 5. Написать рекурсивную функцию, определяющую является ли заданное натуральное число простым.

16 Procedure Picture1(x,y,r,r1,n:integer); Var x1,y1:integer; i:integer; Begin if n > 0 then {заглушка} begin circle(x,y,r);r1:=trunc(r*k2); {рисование окружности} r1:=trunc(r*k2) {вычисление радиуса орбиты} For i:=1 to 4 do begin x1:=trunc(x+r1*cos(pi/2*i); { координаты центра } y1:=trunc(y+r1*sin(pi/2*i); { i-ой окружности } Picture1(x1,y1,trunc(r*k1),r1,n-1); end;

17 Uses Graph; Var x,y,n,r,r1,cd,gm:integer; k1,k2:real; Procedure Picture1(x,y,r,r1,n:integer); … End; Begin Writeln(Введите количество уровней n); Readln(n); x:=600 Div 2; y:=400 Div 2; Writeln(Введите радиус первой окружности r); readln(r); k1:=0.3; k2:=2; Cd:=detect; gm:=1; Initgraph(cd,gm,c:\tp7\bin); Picture1(x,y,r,r1,n); Readln; Closegraph; End.