Рекурсия Рекурсия происходит от английского слова, означающего возвращение, повторение. К процедуре или функции можно

При каждом рекурсивном вызове в стеке создается новая копия тела подпрограммы со своим новым множеством локальных переменных, в

Разработка рекурсивных алгоритмов является одной из самых сложных задач программирования. Пример: Вычислить факториал числа n.

1 function fact (n1: integer): integer; 2 var 3 i, k: integer; 4 begin 5 k:=1; 6 for i:=1 to n1 do 7 k:=k*i; 8 fact:=k 9 end;

2 способ n=3 n!=n*(n-1)! 3!=3*(3-1)!=3*2! =3*2=6 2!=2*1! =2*1=2 1!=1*0! =1*1=1 0!=1

для n>0 n! = n*(n-1)! для n = 0 n! = 0! = 1 - выход из рекурсивного алгоритма В рекурсивных процедурах и функциях должен быть

1 procedure TForm1.Button1Click( ); 2 var n: integer; 3 function fact (n1: integer): integer; 4 begin 5 If n1=0 then 6 fact:=1

Ручной просчет алгоритма при n1=3 3 function fact (n1: integer): integer; 4 begin 5 If n1=0 then 6 fact:=1 7 else 8 fact:=

1 function nod (n, m: integer):integer; 2 var h: integer; (*вспомогательная переменная*) 3 begin 4 if m>n then h:= nod (m, n)

387.42K

Похожие презентации:

Рекурсия в программировании. (Лекция 10)

Тема 6. Подпрограммы в языке Паскаль

Программирование на языке Паскаль. Простейшие программы

понятие подпрограмм. Механизм реализации подпрограмм с помощью процедур и функций

Модульное программирование. Глава 4

Модульное программирование

Процедуры и функции в С++

Переменные-указатели и операции над указателями. Лекция 6 по алгоритмизации и программированию

Программирование на языке Python

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

3_процедуры и функции часть 5

1. Процедуры и функции часть 5

2. Рекурсия Рекурсия происходит от английского слова, означающего возвращение, повторение. К процедуре или функции можно

обращаться:
1) из тела основной программы;
2) из тела другой процедуры (функции);
3) из тела самой процедуры (функции).
Обращение процедуры (функции) к самой себе
называется рекурсивным, а сама процедура или функция
называется в этом случае рекурсивной.
2

3. При каждом рекурсивном вызове в стеке создается новая копия тела подпрограммы со своим новым множеством локальных переменных, в

том числе формальных
параметров.
При завершении в стеке выполнения
очередной копии подпрограммы данная
копия завершается, удаляется из стека, и
управление передается в вызвавшую эту
копию подпрограмму.
3

4. Разработка рекурсивных алгоритмов является одной из самых сложных задач программирования. Пример: Вычислить факториал числа n.

1 способ
Пусть n=3
n!=1*2*3*…*n
3!=1*2*3=6
0!=1
1!=0!*1
2!=1!*2
3!=2!*3
4

5. 1 function fact (n1: integer): integer; 2 var 3 i, k: integer; 4 begin 5 k:=1; 6 for i:=1 to n1 do 7 k:=k*i; 8 fact:=k 9 end;

6. 2 способ n=3 n!=n(n-1)! 3!=3(3-1)!=32! =32=6 2!=21! =21=2 1!=10! =11=1 0!=1

2 способ
n=3
n!=n*(n-1)!
3!=3*(3-1)!=3*2!
2!=2*1!
1!=1*0!
=3*2=6
=2*1=2
=1*1=1
0!=1
6

7. для n>0 n! = n*(n-1)! для n = 0 n! = 0! = 1 - выход из рекурсивного алгоритма В рекурсивных процедурах и функциях должен быть

для n>0
n! = n*(n-1)!
для n = 0
n! = 0! = 1 - выход из рекурсивного алгоритма
В рекурсивных процедурах и функциях должен
быть предусмотрен выход без очередного вызова
(в нашем случае n=0). Если его нет, происходит
переполнение стека (выдается сообщение об
ошибке – недостаточно памяти).
7

8.

1
fact(n1)
2
n1=0
да
3
4
нет
fact=1
fact=n1*
fact(n1-1)
5
конец
8

9. 1 procedure TForm1.Button1Click( ); 2 var n: integer; 3 function fact (n1: integer): integer; 4 begin 5 If n1=0 then 6 fact:=1

7
else
8
fact:= n1*fact(n1-1)
9 end;
10 begin
11
n:=strtoint(edit1.text);
12
edit2.text:=inttostr(fact(n));
13 end;
Строка 8 – рекурсивный вызов функции
9

10. Ручной просчет алгоритма при n1=3 3 function fact (n1: integer): integer; 4 begin 5 If n1=0 then 6 fact:=1 7 else 8 fact:=

n1=3 – 1 вызов
подпрограммы-функции
fact (3)
3 function fact (n1: integer): integer; 5 3=0 - нет
8 fact=3*fact(3-1)=3*fact (2)
4 begin
Ручной просчет алгоритма
при n1=3
5
If n1=0 then
6
fact:=1
7
else
8
fact:= n1*fact(n1-1)
9 end;
Стек
n1=3
fact(3)-1 копия
10

11. Ручной просчет алгоритма при n1=3 3 function fact (n1: integer): integer; 4 begin 5 If n1=0 then 6 fact:=1 7 else 8 fact:=

n1=3 – 1 вызов
подпрограммы-функции
Ручной просчет алгоритма
fact (3)
при n1=3
5 3=0 - нет
3 function fact (n1: integer): integer; 8 fact=3*fact(3-2)=3*fact (2)
4 begin
n1=2– 2 вызов
5
If n1=0 then
подпрограммы-функции
6
fact:=1
fact (2)
7
else
5 2=0 - нет
8
fact:= n1*fact(n1-1) 8 fact=2*fact(2-1)=2*fact (1)
9 end;
fact(2)-2 копия
n1=2
Стек
fact(3)-1 копия
n1=3
11

12.

n1=3 – 1 вызов
подпрограммы-функции
Ручной просчет
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов
подпрограммы-функции
fact (2)
5 2=0 - нет
fact(1)-3 копия
8 fact=2*fact(2-1)=2*fact (1)
n1=1– 3 вызов
подпрограммы-функции
n1=1
fact (1)
fact(2)-2 копия
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
n1=2
Стек
fact(3)-1 копия
n1=3
12

13.

n1=3 – 1 вызов
Ручной просчет
подпрограммы-функции
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов
подпрограммы-функции
fact (2)
fact(0)-4 копия
5 2=0 - нет
fact(1)-3 копия
8 fact=2*fact(2-1)=2*fact (1)
n1=0
n1=1– 3 вызов
подпрограммы-функции
n1=1
fact(2)-2 копия
fact (1)
5 1=0 - нет
n1=2
8 fact=1*fact(1-1)=1*fact (0)
n1=0– 4 вызов
подпрограммы-функции
fact (0)
n1=3
5 0=0 - да
6 fact=1
fact(3)-1 копия
13
Стек

14.

n1=3 – 1 вызов
Ручной просчет
подпрограммы-функции
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов
подпрограммы-функции
fact(0)=1 -4
fact (2)
копия
5 2=0 - нет
fact(1)-3 копия
8 fact=2*fact(2-1)=2*fact (1)
n1=0
n1=1– 3 вызов
подпрограммы-функции
n1=1
fact(2)-2 копия
fact (1)
5 1=0 - нет
n1=2
8 fact=1*fact(1-1)=1*fact (0)
n1=0– 4 вызов
подпрограммы-функции
fact (0)
n1=3
5 0=0 - да
6 fact=1
fact(3)-1 копия
14
Стек

15.

n1=3 – 1 вызов
Ручной просчет
подпрограммы-функции
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов
подпрограммы-функции
Стек
fact (2)
5 2=0 - нет
fact(1)-3 копия
8 fact=2*fact(2-1)=2*fact (1)
n1=1– 3 вызов
подпрограммы-функции
n1=1
fact (1)
fact(2)-2 копия
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
n1=2
=1*1=1
n1=0– 4 вызов
подпрограммы-функции
fact (0)
n1=3
5 0=0 - да
fact(3)-1 копия
15
6 fact=1

16.

n1=3 – 1 вызов
Ручной просчет
подпрограммы-функции
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов
подпрограммы-функции
fact (2)
5 2=0 - нет
fact(1)=1 -3
8 fact=2*fact(2-1)=2*fact (1)
копия
n1=1– 3 вызов
подпрограммы-функции
n1=1
fact(2)-2
fact (1)
копия
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
n1=2
=1*1=1
n1=0– 4 вызов
подпрограммы-функции
fact (0)
n1=3
5 0=0 - да
fact(3)-1 копия
16
6 fact=1
Стек

17.

n1=3 – 1 вызов подпрограммыфункции
Ручной просчет
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов подпрограммыфункции
fact (2)
5 2=0 - нет
8 fact=2*fact(2-1)=2*fact (1) =
2*1=2
fact(2) -2 копия
n1=1– 3 вызов подпрограммыфункции
n1=2
fact (1)
n1=2
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
=1*1=1
n1=0– 4 вызов подпрограммыфункции
n1=3
fact (0)
5 0=0 - да
6 fact=1
fact(3)-1 копия
Стек
17

18.

n1=3 – 1 вызов подпрограммыфункции
Ручной просчет
fact (3)
алгоритма
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
n1=2– 2 вызов подпрограммыфункции
fact (2)
5 2=0 - нет
8 fact=2*fact(2-1)=2*fact (1) =
2*1=2
fact(2)=2 -2 копия
n1=1– 3 вызов подпрограммыфункции
n1=2
fact (1)
n1=2
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
=1*1=1
n1=0– 4 вызов подпрограммыфункции
n1=3
fact (0)
5 0=0 - да
6 fact=1
fact(3)-1 копия
Стек
18

19.

n1=3 – 1 вызов подпрограммыфункции
fact (3)
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
=3*2=6
9 n1=2– 2 вызов
подпрограммы-функции
fact (2)
5 2=0 - нет
8 fact=2*fact(2-1)=2*fact (1) =
2*1=2
n1=1– 3 вызов подпрограммыфункции
fact (1)
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
=1*1=1
n1=0– 4 вызов подпрограммыфункции
fact (0)
5 0=0 - да
6 fact=1
Ручной просчет
алгоритма
Стек
fact(3)-1 копия
n1=3
19

20.

21.

n1=3 – 1 вызов подпрограммыфункции
fact (3)
5 3=0 - нет
8 fact=3*fact(3-2)=3*fact (2)
=3*2=6
9 n1=2– 2 вызов
подпрограммы-функции
fact (2)
5 2=0 - нет
8 fact=2*fact(2-1)=2*fact (1) =
2*1=2
n1=1– 3 вызов подпрограммыфункции
fact (1)
5 1=0 - нет
8 fact=1*fact(1-1)=1*fact (0)
=1*1=1
n1=0– 4 вызов подпрограммыфункции
fact (0)
5 0=0 - да
6 fact=1
fact(3)=6 – возврат
в главную
программу
Ручной
просчет
алгоритма
Стек
21

22.

Рекурсивная функция
вычисляет НОД двух целых
чисел n и m.
1
nod(n,m)
2
m>n
h – вспомогательная переменная
да
3
4
нет
h=nod(m,n)
m<=0
да
5
нет
h=nod(m,
n mod m)
6
h=n
7
nod=h
8
конец
22

23. 1 function nod (n, m: integer):integer; 2 var h: integer; (вспомогательная переменная) 3 begin 4 if m>n then h:= nod (m, n)

1 function nod (n, m: integer):integer;
2 var h: integer; (*вспомогательная переменная*)
3 begin
4
if m>n then h:= nod (m, n) (*путь 1*)
5
else
6
if m<=0 then h:=n
(*путь 2*)
7
else h:=nod (m, n mod m) (*путь 3*)
8
nod:= h;
(*h – результат вычислений*)
9 end;
Cтроки 4 и 7 содержат рекурсивный вызов функции.
Строка 6 обеспечивает завершение подпрограммы, так как
не содержит очередного рекурсивного вызова функции.
Рекурсивный процесс шаг за шагом упрощает задачу.
23

24.

Ручной просчет алгоритма n=9 m=12
1 function nod (n, m: integer):integer;
2 var h: integer; (*вспомогательная переменная*)
3 begin
4 if m>n then h:= nod (m, n) (*путь 1*)
5 else
6 if m<=0 then h:=n (*путь 2*)
7 else h:=nod (m, n mod m) (*путь 3*)
8 nod:= h;
(*h – результат вычислений*)
9 end;
n=9 m=12
nod (9,12) 1 вызов
4 m>n 12>9 – да путь 1
h=nod(m,n) = nod (12,9) – 2 вызов
n=12 m=9
4 m>n 9>12 – нет
5-6-7 m<=0 9<=0 – нет – путь 3
7 h=nod (m, n mod m)= nod (9, 12 mod 9)= nod (9, 3) – 3 вызов
n=9 m=3
4 m>n 3>9 – нет
5-6-7 m<=0 3<=0 – нет – путь 3
7 h=nod (m, n mod m)= nod (3, 9 mod 3)= nod (3, 0) – 4 вызов
n=3 m=0
4 m>n 0>3 – нет
5-6 m<=0 0<=0 – да – h=n=3 путь 2
8 nod=nod(3,0)=3
24

25.

Ручной просчет алгоритма n=9 m=12
1 function nod (n, m: integer):integer;
2 var h: integer; (*вспомогательная переменная*)
3 begin
4 if m>n then h:= nod (m, n) (*путь 1*)
5 else
6 if m<=0 then h:=n (*путь 2*)
7 else h:=nod (m, n mod m) (*путь 3*)
8 nod:= h;
(*h – результат вычислений*)
9 end;
n=9 m=12
nod (9,12) 1 вызов
8 nod=nod
4 m>n 12>9 – да путь 1
(9,12)=3
h=nod(m,n) = nod (12,9) – 2 вызов
8 nod=nod
n=12 m=9
(12,9)=3
4 m>n 9>12 – нет
5-6-7 m<=0 9<=0 – нет – путь 3
7 h=nod (m, n mod m)= nod (9, 12 mod 9)= nod (9, 3) – 3 вызов
8 nod=nod
n=9 m=3
(9,3)=3
4 m>n 3>9 – нет
5-6-7 m<=0 3<=0 – нет – путь 3
7 h=nod (m, n mod m)= nod (3, 9 mod 3)= nod (3, 0) – 4 вызов
n=3 m=0
4 m>n 0>3 – нет
5-6 m<=0 0<=0 – да – h=n=3 путь 2
8 nod=nod(3,0)=3
25

English Русский Правила