РЕКУРСИЯ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ У попа была собака - он ее любил. Она съела кусок мяса - он ее убил. Вырыл ямку - закопал, Взял дощечку – написал: У. - презентация

1 РЕКУРСИЯ РЕКУРРЕНТНЫЕ СООТНОШЕНИЯ У попа была собака - он ее любил. Она съела кусок мяса - он ее убил. Вырыл ямку - закопал, Взял дощечку – написал: У попа была собака - он ее любил… Кулебякин В.В.

2 Рекуррентные соотношения В математике часто встречаются последовательности чисел, в которых каждый следующий член выражается через предыдущие. Арифметическая прогрессия Арифметическая прогрессия, где каждый следующий член равен предыдущему, увеличенному на разрядность прогрессии: Например: a i = a i-1 +d рекуррентными соотношениями. Формулы, выражающие очередной член последовательности через предыдущие, называют рекуррентными соотношениями.

3 n! Вычисление факториала n! Факториал можно определить двумя способами. Первый способ: n Произведение первых n членов натурального ряда n! = 1*2*3*…*n Второй способ: Используется рекуррентная формула: n! = n*(n-1)!

4 Рекурсивные подпрограммы рекурсивными Процедуры и функции производящие вызов самих себя называются рекурсивными

5 Var fact:longint; n,i:integer; Begin clrscr; write(Введите число); Readln(n); Fact:=1; For i:=1 to n do Fact:=Fact*i; Writeln(Факториал,n,!=,Fact); Readln; End. n! = 1*2*3*…*n Первый способ: n! = 1*2*3*…*n

6 Uses crt; Var n:integer; Begin clrscr; write(Введите число); Readln(n); Writeln(Факториал,n,!=,Fact(n)); Readln; End. Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; n! = n*(n-1)! Второй способ: n! = n*(n-1)! рекуррентного соотношения рекурсию Наличие рекуррентного соотношения в формуле позволяет использовать рекурсию в алгоритме программы. Рекурсивная функция При использовании рекурсии необходимо обеспечить выход из подпрограммы в нужный момент, т.к. алгоритм должен быть конечным (одно из свойств).

7 Что такое Стек?! Значения всех локальных переменных и параметров, помещаются в стек. Стеком называется структура, напоминающая трубку с запаянным концом. При заполнении стека действует принцип «последним пришел – первым ушел». Если стек заполняется 1-м, 2-м, 3-м элементами, то извлекаются эти элементы в обратном порядке – 3-й, 2-й, 1-й.

8 Трассировка программы Ввод (n=5); Fact(5); i=5; Fact(5):=5*Fact(4); i=4; Fact(4):=4*Fact(3); i=3; Fact(3):=3*Fact(2); i=2; Fact(2):=2*Fact(1); i=1; Fact(1):=1*Fact(0); i=0; Fact(0):=1; Вывод n!=120; Fact(5):=5*24; (120) Fact(4):=4*6; (24) Fact(3):=3*2; (6) Fact(2):=2*1; (2) Fact(1):=1*1; (1) Запись значений переменных на различных этапах выполнения программы Рекурсивный спуск Рекурсивный возврат

9 Трассировка программы Ввод (n=5); Fact(5); i=5; Fact(5):=5*Fact(4); i=4; Fact(4):=4*Fact(3); i=3; Fact(3):=3*Fact(2); i=2; Fact(2):=2*Fact(1); i=1; Fact(1):=1*Fact(0); i=0; Fact(0):=1; Запись значений переменных на различных этапах выполнения программы Рекурсивный спуск Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End; Function Fact(i:integer):longint; Begin if i=0 then fact:=1 else fact:=i*Fact(i-1); End;

10 Рекурсивный спуск и возврат рекурсивный спуск рекурсивный спуск рекурсивный возврат. Главное требование к рекурсивным подпрограммам заключается в том, что вызов рекурсивной подпрограммы (рекурсивный спуск) должен выполняться по условию, которое на каком то уровне рекурсии становится таким, что рекурсивный спуск прекращается и начинается рекурсивный возврат.

11 Формы рекурсивной процедуры процедура с выполнением действий на рекурсивном спуске: Procedure Рекурсия; Begin Действия на входе в рекурсию; If Условия then Рекурсия; End; процедура с выполнением действий на рекурсивном возврате: Procedure Рекурсия; Begin If Условия then Рекурсия; Действия на выходе из рекурсии; End; процедура с выполнением действий на рекурсивном спуске и возврате: Procedure Рекурсия; Begin Действия на входе в рекурсию; If Условия then Рекурсия; Действия на выходе из рекурсии; End;

12 12 Итерация - повторное выполнение некоторых действий до тех пор, пока не будет удовлетворяться некоторое условие. Большинство алгоритмов можно реализовать двумя способами: 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; Итерацией: Рекурсией:

13 Последовательность Фибоначчи последовательности Фибоначчи В качестве второго примера рассмотрим программу для вычисления последовательности Фибоначчи, для которого значение очередного члена последовательности равно сумме двух предыдущих, при этом первый и второй члены последовательности принимаются равными единице: F 1 = 1, F 2 =1, n>2 A для любого n>2 F n = F n-1 + F n-2

14 Uses crt; Var n:integer; Begin clrscr; Write(Введите число); Readln(n); Writeln(n,`-е число ряда Фибоначчи =`,Fib(n)); Readln; End. Function Fib(i:integer):longint; Begin if (i=1) or (i=2) then fib:=1 else fib:=Fib(i-1)+Fib(i-2); End; Рекурсивная функция

15 Домашнее задание Написать программу нахождения наибольшего общего делителя двух целых чисел. Пояснение: Для нахождения НОД (a, b) воспользуемся алгоритмом Евклида с вычитанием; будем уменьшать большее из чисел на величину меньшего из чисел до тех пор, пока одно из них не станет равным нулю. Для вычисления НОД (a, b) реализуем рекурсивную функцию.